Griglia colorata.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Consideriamo una griglia di \(4n \times 4n \), e coloriamola con quattro colori in modo tale che ogni sotto griglia \(2 \times 2 \) sia colorata con tutti e quattro i colori (ovvero non c'è un colore che si ripete). Dimostra che i quattro angoli sono colorati con tutti e quattro i colori (ovvero i quattro angoli hanno colori differenti a due a due).

[Folpo13]

Dimostro innanzitutto dimostro il caso base $n=1$.

Supponiamo di avere
axxa
?xx?
????
????

a non potrebbe stare dove ci sono le x, il che è impossibile (si può fare un discorso analogo nel caso di a anche in basso a sinistra). Quindi se un colore è in un angolo, questo non può essere anche nell'angolo adiacente.

Supponiamo invece
a?1?
??23
45??
?6?a

I numeri sono i posti in cui a potrebbe essere messo. Se lo metto in 1 però:
a?a?
??xx
??xx
???a
che è impossibile (discorso analogo se lo metto in 6).

Quindi:
a???
??23
45??
???a

Ma se lo metto in 2 (discorso analogo con 5):
a???
??a3
4xx?
?xxa

E in 3 (o 4):
axx?
?xxa
45??
???a

-------
Quindi è stato dimostrato che in un 4x4 gli angoli devono essere tutti diversi:
a??b
????
????
c??d

può essere trattato come un 2x2 di cui considero solo gli angoli.:
ab
cd

Anche considerando il fatto che:
aa
??
??
??

non può verificarsi per ovvie ragioni, come
a?
??
??
?a

perché
a?
xx
xx
?a

Quindi:
Se posso fare una costruzione 8x8 con questi 4x4 completi allora posso farlo anche con la sua versione "ridotta" di 4x4 formato da 2x2. Ma noi abbiamo visto che un 4x4 basato su quelle caratteristiche degli elementi 2x2 ha sempre gli angoli diversi tra loro, quindi un 8x8 a sua volta ha gli angoli diversi tra loro. Ora posso ridurre gli 8x8 a 2x2 e avere la stessa dimostrazione per i 16x16 e così via...

L'ho dimostrato solo per $n$ potenza di $2$ ma ci ho perso troppo tempo per non mandare almeno questo

Per ora non mi viene in mente nessuna dimostrazione generalizzata per ogni $n$, ma potrei tornarci. Forse basta quello che ho fatto fin'ora per dimostrarlo ma vedrò

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Per il resto sono d'accordo con quello che dici, invece rispetto a quello qui sotto

"Folpo13":
Quindi:
Se posso fare una costruzione 8x8 con questi 4x4 completi allora posso farlo anche con la sua versione "ridotta" di 4x4 formato da 2x2. Ma noi abbiamo visto che un 4x4 basato su quelle caratteristiche degli elementi 2x2 ha sempre gli angoli diversi tra loro, quindi un 8x8 a sua volta ha gli angoli diversi tra loro. Ora posso ridurre gli 8x8 a 2x2 e avere la stessa dimostrazione per i 16x16 e così via...

Non mi è chiaro cosa dici e perché. In particolare come fai a dire che se puoi fare una costruzione 8x8 con alcuni angoli che hanno colori uguali allora puoi farlo anche per un 4x4 ?

[Folpo13]

Non so esprimermi meglio, ma se abbiamo
a??bc??d
????????
????????
c??da??b
a??bc??d
????????
????????
c??da??b

per esempio è equivalente a
abcd
cdab
abcd
cdab

Perché tratto un 4x4 come un 2x2. E posso farlo perché hanno le stesse proprietà: 4 angoli diversi tra loro e un

ab
cd

non può essere seguito da un

b?
d?

o un

d?
b?

quindi solo da

a?
b?

oppure

b?
a?

E questo l'ho dimostrato quando ho detto:

"Folpo13":
considerando il fatto che:
aa
??
??
??

non può verificarsi per ovvie ragioni, come
a?
??
??
?a

perché
a?
xx
xx
?a

Comunque la mia è lontana da essere una dimostrazione chiara e definitiva, forse mi sono capito solo io

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"Folpo13":Non so esprimermi meglio, ma se abbiamo
a??bc??d
????????
????????
c??da??b
a??bc??d
????????
????????
c??da??b

per esempio è equivalente a
abcd
cdab
abcd
cdab

Perché tratto un 4x4 come un 2x2. E posso farlo perché hanno le stesse proprietà: 4 angoli diversi tra loro e un

ab
cd

Non penso sia vero quello che dici! Senza usare altro a priori puoi benissimo dire che la tua griglia 8x8 è formata così
a?-?-b-c-?-?-a
?-?-?-?-?-?-?-?
?-?-?-?-?-?-?-?
d-?-?-c-b-?-?-d
b-?-?-d-a-?-?-c
?-?-?-?-?-?-?-?
?-?-?-?-?-?-?-?
a-?-?-c-b-?-?-d

come puoi vedere ogni sottogriglia 4x4 che ho fatto ha gli angoli tutti differenti, e non c'è nessuna contraddizione solo con queste informazioni sulla griglia al problema, ma tre angoli della griglia 8x8 sono uguali.
Chiaramente non è possibile questa configurazione ma non per il motivo che dici te.

Ciò magari è anche vero quello che dici io non lo so, ma non mi appare così scontata come cosa. Dimostralo.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Okay penso di aver capito cosa intendi, e credo sia vero effettivamente. Ma ti sei spiegato maluccio eh..
Comunque appunto questo dimostra la cosa solo per le griglia \( 2^n \times 2^n \) con \(n \geq 2 \).