Colorazioni e partizioni

[giulylanza06]

00

[kobeilprofeta]

Se $n $ è pari basta metterli a coppie. In ogni coppia (a,b) avrò f (a)=b e f (b)=a ; con a nero e b bianco

Se n è dispari posso formare un terzetto (a,b,c) dove
$f (a)=b $, $f (b)=c $, $f (c)=a $; con $a $ nero, $b $ bianco, $c $ rosso
Con gli n-3 elementi rimasti mi riconducono al caso $n $ pari

[Vincent46]

Induzione: se $|X| = 2$, ok. Passo induttivo: sia $|X| = n$ e supponiamo che l'asserto valga quando $|X|=n-1$ Allora, abbiamo due casi:
$1$ $f$ è una permutazione. Allora ne consideriamo la decomposizione in cicli disgiunti. Colorando alternamente gli elementi di ogni ciclo utilizzando i primi due colori, eventualmente colorando l'ultimo elemento di ogni ciclo del terzo colore, la tesi in questo caso è provata.
$2$ $f$ non è una permutazione, cioé esiste un elemento $x \in X$ che non è immagine di nessun altro elemento di $X$. Allora consideriamo la restrizione di $f$ dall'insieme $X \\ \{x}$ in se stesso. Tale insieme quale consta di $n-1$ elementi, per cui ne esiste una colorazione adeguata per ipotesi induttiva. Ora basta colorare l'elemento $x$ di un colore diverso da quello di $f(x)$ per concludere.