3-Coloriamo i naturali!

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Il_Russo
Messaggi: 347
Iscritto il: 16 gen 2007, 16:04
Località: Pisa

3-Coloriamo i naturali!

Messaggio da Il_Russo » 16 ott 2012, 11:50

Sia $f$ una funzione da $\mathbb{N}$ a $\mathbb{N}$ senza punti fissi, ossia per ogni $n \in \mathbb{N}$ si ha $f(n) \neq n$.

Dimostrare che, dato un sottoinsieme finito $X$ dei naturali, `e possibile colorare i suoi elementi di 3 colori in modo che, ogni volta che sia $m$ che $f(m)$ appartengono a $X$, questi abbiano colori diversi.

More difficult (MNE, ma anche no): Dimostrare che `e possibile colorare TUTTI i naturali di 3 colori in modo che per ogni $m$ naturale $m$ ed $f(m)$ abbiano colori distinti.
Aderisci anche tu al progetto "Diamo a Nonciclopedia una sezione matematica indecente"

Presidente della commissione EATO per le IGO

Il_Russo
Messaggi: 347
Iscritto il: 16 gen 2007, 16:04
Località: Pisa

Re: 3-Coloriamo i naturali!

Messaggio da Il_Russo » 29 ott 2012, 15:42

Rispolvero e lascio un aiutino
Testo nascosto:
Induzione sul numero degli elementi dell´insieme da colorare
Aderisci anche tu al progetto "Diamo a Nonciclopedia una sezione matematica indecente"

Presidente della commissione EATO per le IGO

Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 3-Coloriamo i naturali!

Messaggio da kalu » 15 nov 2012, 15:27

Odio le colorazioni, odio i grafi e tutta la combinatoria.
Il_Russo ha scritto:Dimostrare che, dato un sottoinsieme finito $X$ dei naturali, `e possibile colorare i suoi elementi di 3 colori in modo che, ogni volta che sia $m$ che $f(m)$ appartengono a $X$, questi abbiano colori diversi.
Seguo il suggerimento in hint.
Il caso base è abbastanza banale.
Suppongo che per qualche $ t \in \mathbb{N} $, ogni insieme di cardinalità $ n-1 $ si possa felicemente colorare.
Prendo un insieme $ X \subset N $ di cardinalità $ n $, e considero il grafo orientato in cui i nodi sono gli elementi di $ X $ e esiste un arco che va da $ x $ a $ y $ se e solo se $ f(x)=y $. Sia $ d^{-}(x) $ il numero degli archi che arrivano a $ x $ e $ d^+(x) $ il numero degli archi che partono da $ x $ (quindi $ d(x) \in \{0, 1\} \ \forall x \in X $)
Voglio colorare i nodi in modo che se $ x, y $ sono connessi da un arco allora hanno diverso colore. Divido due casi.

$ \bullet $ $ \exists a \in X \ : \ d^-(a)=0 $
Considero $ X/\{a\} $. $ |X/\{a\}|=n-1 $, quindi posso colorarlo bene.
Se $ d^+(a)=0 $ coloro $ a $ di un qualsiasi colore e pace.
Se $ d^+(a)=1 $ coloro $ a $ di un colore diverso da quello di $ f(a) $ e pace di nuovo.

$ \bullet $ $ d^-(x)>0 \ \forall x \in X $
Si ha che $ n\leq\sum_{x\in X}{d^-(x)}=\sum_{x\in X}{d^+(x)}\leq n $, quindi $ d^-(x)=d^+(x)=1 \ \forall \ x \in X $.
E' immediato verificare che il grafo è costituito solo da cicli, ognuno dei quali può essere facilmente colorato alternando due colori se ha un numero pari di nodi o ricorrendo al terzo se ne ha un numero dispari.
Il_Russo ha scritto:More difficult (MNE, ma anche no): Dimostrare che `e possibile colorare TUTTI i naturali di 3 colori in modo che per ogni $m$ naturale $m$ ed $f(m)$ abbiano colori distinti.
Considero il grafo orientato avente per nodi i numeri naturali, in cui esiste un arco che va da $ x $ a $ y $ se e solo se $ f(x)=y $. Questa volta $ d^+(x)=1 \ \forall \ x \in \mathbb{N} $.
Prendo un sottoinsieme $ X \subseteq N $ tale che, per ogni $x \in X$, $x$ e $y$ siano connessi (senza tener conto delle orientazioni) se e solo se $ y \in X $, e dimostro che si può colorare (poi gli altri sottoinsiemi di $\mathbb{N}$ si coloreranno in modo analogo, fino a colorare tutto $ \mathbb{N} $).

OSSERVAZIONE 1. Un "ciclo" può esistere solo secondo la definizione di "ciclo" propria dei grafi orientati, nel senso che se esiste un cammino che da un nodo arriva a se stesso senza tener conto delle orientazioni, ma non esiste più tenendo conto delle orientazioni, significa che esiste un nodo dal quale escono almeno due archi, il chè è impossibile.
OSSERVAZIONE 2. $ X $ possiede al più un ciclo.
Supponiamo che ne esistano due. Se un nodo appartiene ad entrambi significa che da quel nodo escono almeno due archi: assurdo.
Prendiamo ora un nodo appartenente ad un ciclo e un nodo appartenente all'altro. Per definizione di $ X $ tali nodi sono connessi. Gli archi estremali della catena che li unisce devono entrare in essi, altrimenti da uno dei due dovrebbe partire più di un arco. Ma affinchè una siffatta catena esista da almeno un suo nodo dovrebbero uscire due archi, anche questo assurdo.

Se $ X $ è privo di cicli bastano due colori per colorarlo tutto: coloro un suo nodo qualsiasi, poi coloro diversamente tutti i nodi ad esso adiacenti, e poi per ogni nodo colorato coloro tutti i suoi adiacenti del colore diverso. Il fatto che non ci siano cicli mi assicura che per ogni nodo non troverò mai nodi adiacenti colorati in modo sbagliato.
Se $ X $ ha un ciclo, coloro quello (se il ciclo ha un numero dispari di nodi mi serviranno tre colori, altrimenti me ne bastano due) e poi vado avanti nella colorazione come prima, fino a terminare.
Pota gnari!

Il_Russo
Messaggi: 347
Iscritto il: 16 gen 2007, 16:04
Località: Pisa

Re: 3-Coloriamo i naturali!

Messaggio da Il_Russo » 18 nov 2012, 01:07

La soluzione è corretta. Naturalmente, per il secondo punto, ne esistono almeno due più avanzate che passano da tutt'altra parte. Lascio qui due one word spoiler
Testo nascosto:
ULTRAFILTRI
Testo nascosto:
COMPATTEZZA
Aderisci anche tu al progetto "Diamo a Nonciclopedia una sezione matematica indecente"

Presidente della commissione EATO per le IGO

Rispondi