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.
3-Coloriamo i naturali!
3-Coloriamo i naturali!
Presidente della commissione EATO per le IGO
Re: 3-Coloriamo i naturali!
Rispolvero e lascio un aiutino
Testo nascosto:
Presidente della commissione EATO per le IGO
Re: 3-Coloriamo i naturali!
Odio le colorazioni, odio i grafi e tutta la combinatoria.
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.
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.
Seguo il suggerimento in hint.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.
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.
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} $.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.
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!
Re: 3-Coloriamo i naturali!
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:
Testo nascosto:
Presidente della commissione EATO per le IGO