[L04] Colori!

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

[L04] Colori!

Messaggioda Gerald Lambeau » 07/03/2016, 22:06

Sia $n$ un intero positivo, una tabella $2n \times 2n$ di $4n^2$ quadrati unitari è colorata con quattro colori in modo che ogni quadrato $1 \times 1$ sia di esattamente un colore e ogni quadrato $2 \times 2$ contenga esattamente tutti e quattro i colori diversi.
Dimostrare che i quattro quadrati d'angolo hanno tutti colori diversi l'uno dagli altri.
Testo nascosto:
Boh, forse qualcuno lo troverà più facile
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L04] Colori!

Messaggioda carlotheboss » 08/03/2016, 15:41

Carino il problema, un po' meno la mia soluzione D:
Testo nascosto:
Consideriamo la matrice [tex]2n \times 2n[/tex] avente le righe e le colonne indicizzate da [tex]1[/tex] a [tex]2n[/tex]. Ora consideriamo, WLOG, l'angolo in alto a sinistra $(1, 1)$ di colore $A$. Se considero il quadrato avente $(1, 1)$ e $(2, 2)$ come vertici noto che, per ipotesi, non posso avere nelle prime due colonne della riga $2$ una casella di colore $A$. Considerando poi il quadrato con vertici $(2, 1)$ e $(3, 2)$, dato che deve avere tutti e quattro i colori, una delle prime due caselle di riga $3$ deve essere di colore $A$. Iterando questo ragionamento trovo che se $A$ si trova in $(1, 1)$ allora per ogni riga di indice dispari deve esserci una $A$ in una delle prime due colonne, mentre non può esserci nelle colonne pari (sennò ci sarebbe almeno un quadratino [tex]2 \times 2[/tex] che non avrebbe tutti i colori). Idem con le colonne (basta invertire i due termini nel ragionamento). Dunque ho dimostrato che un angolo deve essere di colore diverso da quello nella stessa riga e da quello nella stessa colonna.
Rimane da dimostrare il caso in cui due angoli sulla stessa diagonale siano dello stesso colore $A$.
Dimostriamolo per induzione: la tabella [tex]2 \times 2[/tex], per ipotesi, ha sempre gli angoli diagonalmente opposti diversi. Ora se la matrice $(2n, 2n)$ ha sempre gli angoli diagonalmente opposti diversi allora anche quella $(2(n+1), 2(n+1))$. Infatti se per assurdo quest'ultima matrice avesse due angoli diagonalmente opposti entrambi di colore $A$ (siano essi WLOG $(2(n+1), 1)$ e $(1, 2(n+1))$, applicando da entrambi gli angoli il ragionamento sopra si trova che si possono avere $A$ solo in righe e colonne dispari (considerando sempre un quadratino [tex]2 \times 2[/tex] ovviamente) dunque si trova che le caselle $(2n, 2n)$ e $(2, 2)$ devono essere di colore $A$, ma questo è assurdo perché avrei una matrice $(2n, 2n)$ con angoli diagonalmente opposti uguali, dunque la tesi è dimostrata.
N.B: ogni sottomatrice di dimensioni pari ha le stesse proprietà della matrice iniziale (ogni quadratino in essa è anche contenuto nella matrice iniziale quindi ha tutti i colori diversi ecc).
Quindi per ogni angolo, gli altri tre devono essere diversi, il che implica che devono essere tutti e quattro diversi.
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: [L04] Colori!

Messaggioda Gerald Lambeau » 08/03/2016, 16:16

carlotheboss ha scritto:si possono avere $A$ solo in righe e colonne dispari [...] dunque si trova che le caselle $(2n, 2n)$ e $(2, 2)$ devono essere di colore $A$, ma questo è assurdo perché avrei una matrice $(2n, 2n)$ con angoli diagonalmente opposti uguali, dunque la tesi è dimostrata.

Buona la prima parte, quest'affermazione inesatta invece fa vacillare la seconda; sapresti aggiustare?
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L04] Colori!

Messaggioda carlotheboss » 08/03/2016, 16:51

Gerald Lambeau ha scritto:
carlotheboss ha scritto:si possono avere $A$ solo in righe e colonne dispari [...] dunque si trova che le caselle $(2n, 2n)$ e $(2, 2)$ devono essere di colore $A$, ma questo è assurdo perché avrei una matrice $(2n, 2n)$ con angoli diagonalmente opposti uguali, dunque la tesi è dimostrata.

Buona la prima parte, quest'affermazione inesatta invece fa vacillare la seconda; sapresti aggiustare?


Probabilmente mi sono spiegato male, oltre ad aver scritto le coordinate errate .-., ecco cosa intendevo:
Testo nascosto:
Considero due angoli opposti a $(2(n+1), 1)$ e $(1, 2(n+1))$ di colore $A$: partendo dal primo di essi vedo (in modo identico a prima) che in $(2(n+1), 3)$ o in $(2(n+1)-1, 3)$ ci deve essere per forza una (e una sola) casella di colore $A$, sennò avrei il quadrato $(2(n+1)-1, 2)$ $(2(n+1), 3)$ non contiene $A$, da qui, nello stesso modo trovo che in $(2(n+1), 5)$ o in $(2(n+1)-1, 5)$ devo avere una e una sola $A$, e in generale se considero le righe $2(n+1)-1$ e $2(n+1)$ posso avere $A$ solo in colonne di indice dispari (se fosse in una colonna di indice pari avrei un quadratino con o nessuna $A$ o due o più $A$). Quindi una delle due caselle tra $(2(n+1)-1, 2(n+1)-1)$ e $(2(n+1), 2(n+1)-1)$ è di colore $A$.
Applico lo stesso ragionamento partendo da $(1, 2(n+1))$ e scendendo (lungo le righe) ho che anche qui se considero le colonne $2(n+1)-1$ e $2(n+1)$ posso avere $A$ solo in righe di indice dispari. Quindi una delle due caselle tra $(2(n+1)-1, 2(n+1)-1)$ e $(2(n+1)-1, 2(n+1))$ è una $A$.
Da qui vedo l'unica scelta possibile è avere una $A$ in $(2(n+1)-1, 2(n+1)-1)$ (e non posso non averla sennò avrei un quadratino [tex]2 \times 2[/tex] senza $A$).

Tutto questo discorso lo riapplico andando in direzioni "diverse", ovvero verso l'angolo in alto a sinistra e ottengo che la casella $(2, 2)$ ha colore $A$.

Ora la matrice avente $(2, 2)$ e $(2(n+1)-1, 2(n+1)-1)$ come vertici è una matrice di dimensioni $2n \times 2n$ che ha gli angoli opposti uguali, assurdo.
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: [L04] Colori!

Messaggioda Gerald Lambeau » 08/03/2016, 16:58

Ora va bene! :D
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L04] Colori!

Messaggioda carlotheboss » 08/03/2016, 17:25

Gerald Lambeau ha scritto:Ora va bene! :D

Perfetto! Si alla fine la soluzione che avevo pensato era quella da subito, ma, come al solito, ero stato troppo sintetico/superficiale (anche perché sono quegli esercizi che sono facili col disegno e difficili senza D:)
carlotheboss
 
Messaggi: 65
Iscritto il: 17/02/2016, 16:12


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite