Nazionali peruviane 2006
Tutte le caselle di una scacchiera (n+1)(n-1) sono colrati in rosso, in blu o in verde, in modo che, per ogni 2 colonne distinte e ogni 2 file distinte, le 4 caselle d'intersezione non hanno tutte lo stesso colore. Trovare il massimo valore che può assumere n.
Ciao!
Edo
Variopinte scacchiere peruviane
Mi hanno chiesto tramite m.p. uno sketch di dimostrazione di questo problema. Vediamo un po'...
Cominciamo con qualche esempio di riscaldamento:
Sia n un qualunque intero. Dimostrare che è possibile colorare la scacchiera 3 x n, per qualunque n. [facile]
Trovare il massimo n tale per cui è possibile colorare una scacchiera 4 x n. (l'esercizio è fatto da due metà: colorare una certa scacchiera e far vedere che una scacchiera più grande non è colorabile...). Sol:n=18.
Cominciamo con qualche esempio di riscaldamento:
Sia n un qualunque intero. Dimostrare che è possibile colorare la scacchiera 3 x n, per qualunque n. [facile]
Trovare il massimo n tale per cui è possibile colorare una scacchiera 4 x n. (l'esercizio è fatto da due metà: colorare una certa scacchiera e far vedere che una scacchiera più grande non è colorabile...). Sol:n=18.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Step 1: In una tabella 4*8 (4 righe e 8 colonne) non posso colorare 15 caselle di rosso rispettando le ipotesi.
Sia $ t_i $ il numero di caselle colorate di rosso nella riga i-esima ($ R_i $).
Sia $ g(R_i;R_j) $ il numero di colonne t.c. abbiano tra le righe due $ R_i $ e $ R_j $ almeno una casella rossa.
Sia $ p(R_i;R_j) $ il numero di colonne t.c. abbiano una casella rossa sia nella riga i-esima che nella riga j-esima.
Sia $ f(R_i;R_j;R_k) $ il numero di colonne t.c abbiano una casella rossa nella riga i-esima ma abbiano nessuna casella rossa nelle righe j-esima e k-esima.
Per ipotesi $ p(R_i;R_j) \leq 1 $.
Per la definizione di p,g,f e $ t_i $ ottengo le seguenti (e considerando che le colonne sono 8):
1) $ 8\ge g(R_i;R_j)=t_i+t_j-p(R_i;R_j) $ $ \ge t_i+t_j-1 $
2) $ t_i \leq f(R_i;R_j;R_k) + p(R_i;R_j)+p(R_i;R_k) $ $ \leq 2+ f(R_i;R_j;R_k) $
3) $ f(R_i;R_j;R_k)\leq 8-g(R_j;R_k) $
4) $ 9\ge t_i+t_j $
Essendo $ t_1+t_2+t_3+t_4=15 $ sicuramente esistono $ t_i;t_j $ tali che $ t_i+t_j \ge8 $.
Wlog $ 9 \ge t_1+t_2 \ge 8 $
Per la 1: $ g(R_1;R_2)\ge 7 $.
Per la 3: $ f(R_3;R_2;R_1) $ $ \leq 8-g(R_1;R_2)\leq 1 $
Per la 2: $ t_3\leq 2+1 $
Analogamente $ t_4 \leq 3 $.
Sommando i valori ottengo : $ 9+3+3=15 $ $ \ge t_1+t_2+t_3+t_4=15 $
Quindi effettivamente posso supporre $ 9 =t_1+t_2; 3=t_4=t_3 $.
Per la 1: $ 8\ge g(R_1;R_2) $ $ =t_1+t_2-p(R_1;R_2) $ $ \ge t_1+t_2-1=8 $
per cui vale sempre l’uguaglianza.
$ 8= g(R_1;R_2) $
$ 1=p(R_1;R_2) $
Per la 3: $ f(R_3;R_1;R_2) $ $ \leq 8-g(R_1;R_2)=0 $
Per la 2: $ 3 = t_3 $ $ \leq 2+ f(R_3;R_1;R_2)=2 $
Ma ciò è assurdo, quindi in una tabella 4*8 non posso colorare 15 caselle di rosso rispettando le ipotesi.
Step 2: In una tabella (4-k)*8 (con $ k \ge 0 $) non posso colorare $ 15-k $ caselle di rosso rispettando le ipotesi.
Ipotizzo di poter colorare di rosso 15-k caselle di una tabella (4-k)8.
Allora posso aggiungere k righe e in ciascuna riga colorare una sola casella di rosso.
Così facendo non modifico il rispetto (o il non rispetto) delle ipotesi.
Ottengo una tabella con 4*8 righe con 15 caselle rosse che non è colorabile rispettando le ipotesi per lo step 1.
Quindi nella tabella da cui ero partito ovvero la (4-k)*8 non posso colorare di rosso 15-k caselle rispettando le ipotesi.
Posso inoltre facilmente dimostrare che in una tabella (4-k-r)*8 non posso colorare $ 15-k+s $ (con $ k,r,s \ge 0 $) caselle di rosso rispettando le ipotesi.
Infatti in una tabella (4-k-r)*8 il numero massimo di caselle colorabili di rosso rispettando le ipotesi è $ Z < 15-k-r $ $ \leq 15-k+s $
Step 3: Le tabelle 12*10 nelle quali non valgono tutti gli uguali della 5 non sono colorabili.
Considero ora una tabella 12*10.
Mantengo tutte le definizioni dello step 1 applicate ora ad una tabella con 10 righe e 12 colonne.
Posso supporre Wlog che le caselle colorate di rosso siano $ \ge 40 $.
Considero $ t_1,t_2,..t_{10} $.
Wlog $ t_1 \ge t_2 \ge ..\ge t_{10} $
Ovvero:
5) $ \frac{t_1+t_2}{2} \ge \frac{t_1+..+t_{10}}{10}\ge 4 $
Quindi se non valgono tutti gli uguali $ t_1+t_2 \ge 9 $.
Sia $ S=12- g(R_1;R_2) \leq 13-t_1-t_2 $
Esistono S colonne nelle quali né $ R_1 $ ne $ R_2 $ abbiano caselle rosse.
Le chiamo colonne fighe.
Le altre colonne le chiamo colonne normali.
Essendo $ 2 \ge p(R_1;R_i)+p(R_2;R_i) $ ciascuna riga può avere al massimo 2 caselle rosse nelle colonne normali.
Il numero massimo di caselle nelle colonne normali colorate di rosso risulta quindi:
$ 2*8+t_1+t_2 $.
Il numero minimo di caselle colorate di rosso nelle colonne fighe risulta quindi:
$ 40-16-t_1-t_2=24-t_1-t_2 $
So inoltre che le righe in cui ci possono essere delle caselle colorate di rosso in una delle colonne fighe sono tutte tranne $ R_1 $ e $ R_2 $ ovvero 10-2=8.
Sia $ 0 \ge -M = 9-t_1-t_2 $.
Il numero minimo di caselle colorate di rosso nelle colonne fighe risulta quindi:
$ 15-M $.
Il numero massimo di colonne fighe è $ 4-M $.
Ma una configurazione di questo tipo non è colorabile per lo step 2.
Step 4: Le tabelle 12*10 nelle quali valgono tutti gli uguali della 5 non sono colorabili.
Suppongo ora valgano tutti gli uguali nella 5. Ottengo:
$ \frac{t_1+t_2}{2} $ $ =\frac{t_1+..+t_{10}}{10}= 4 $ e:
$ t_1= t_2 = ..= t_{10}=4 $
Sia $ s(R_i,R_j,R_k) $ il numero di colonne t.c. abbiano una casella rossa sia nella riga i-esima sia nella riga j-esima sia nella riga k-esima.
Sia $ m(R_i,R_j,R_k,R_o) $ il numero di colonne t.c. abbiano una casella rossa sia nella riga i-esima sia nella riga j-esima sia nella riga k-esima sia nella riga o-esima.
Per ipotesi: $ s(R_i,R_j,R_k)\leq 1 $
$ m(R_i,R_j,R_k,R_o)\leq 1 $
Sia $ l_i $ il numero di caselle colorate di rosso nella colonna i-esima ($ C_i $).
Wlog $ l_1 \ge l_2 \ge .. \ge l_{12} $ quindi:
$ \frac{l_1+..+l_{12}}{12} $ $ =\frac{40}{12} $
Quindi $ l_1 \ge 4 $.
Quindi esistono almeno 4 righe t.c. la loro intersezione con $ C_1 $ sia colorata di rosso.
Considero 4 di queste righe $ (R_1,R_2,R_3,R_4) $.
Per il PIE ho che il numero di colonne t.c. abbiano tra le 4 righe $ R_1, R_2,R_3,R_4 $ almeno una casella rossa è:
$ t_1+t_2+t_3+t_4-p(R_1;R_2)- $ $ p(R_1,R_3)-p(R_1,R_4)-p(R_2,R_3)-p(R_2,R_4)-p(R_4,R_5)+ $ $ s(R_1,R_2,_R_3)+s(R_1,R_2,R_4)+s(R_1,R_3,R_4)+s(R_2,R_3,R_4) $ $ -m(R_1,R_2,R_3,R_4)=16-6+4-1=13 $
Ma ciò è assurdo perché il numero di colonne totale è 12.
Ora non resta che esibire una colorazione della tabella 11*9 (in realtà è colorabile anche la 12*9) per dimostrare che il massimo n t.c. si possa colorare una tabella (n+1)(n-1) come richiesto è 10.
Se qualcosa non è ben chiaro o ho scritto cavolate chiedete pure..
Sia $ t_i $ il numero di caselle colorate di rosso nella riga i-esima ($ R_i $).
Sia $ g(R_i;R_j) $ il numero di colonne t.c. abbiano tra le righe due $ R_i $ e $ R_j $ almeno una casella rossa.
Sia $ p(R_i;R_j) $ il numero di colonne t.c. abbiano una casella rossa sia nella riga i-esima che nella riga j-esima.
Sia $ f(R_i;R_j;R_k) $ il numero di colonne t.c abbiano una casella rossa nella riga i-esima ma abbiano nessuna casella rossa nelle righe j-esima e k-esima.
Per ipotesi $ p(R_i;R_j) \leq 1 $.
Per la definizione di p,g,f e $ t_i $ ottengo le seguenti (e considerando che le colonne sono 8):
1) $ 8\ge g(R_i;R_j)=t_i+t_j-p(R_i;R_j) $ $ \ge t_i+t_j-1 $
2) $ t_i \leq f(R_i;R_j;R_k) + p(R_i;R_j)+p(R_i;R_k) $ $ \leq 2+ f(R_i;R_j;R_k) $
3) $ f(R_i;R_j;R_k)\leq 8-g(R_j;R_k) $
4) $ 9\ge t_i+t_j $
Essendo $ t_1+t_2+t_3+t_4=15 $ sicuramente esistono $ t_i;t_j $ tali che $ t_i+t_j \ge8 $.
Wlog $ 9 \ge t_1+t_2 \ge 8 $
Per la 1: $ g(R_1;R_2)\ge 7 $.
Per la 3: $ f(R_3;R_2;R_1) $ $ \leq 8-g(R_1;R_2)\leq 1 $
Per la 2: $ t_3\leq 2+1 $
Analogamente $ t_4 \leq 3 $.
Sommando i valori ottengo : $ 9+3+3=15 $ $ \ge t_1+t_2+t_3+t_4=15 $
Quindi effettivamente posso supporre $ 9 =t_1+t_2; 3=t_4=t_3 $.
Per la 1: $ 8\ge g(R_1;R_2) $ $ =t_1+t_2-p(R_1;R_2) $ $ \ge t_1+t_2-1=8 $
per cui vale sempre l’uguaglianza.
$ 8= g(R_1;R_2) $
$ 1=p(R_1;R_2) $
Per la 3: $ f(R_3;R_1;R_2) $ $ \leq 8-g(R_1;R_2)=0 $
Per la 2: $ 3 = t_3 $ $ \leq 2+ f(R_3;R_1;R_2)=2 $
Ma ciò è assurdo, quindi in una tabella 4*8 non posso colorare 15 caselle di rosso rispettando le ipotesi.
Step 2: In una tabella (4-k)*8 (con $ k \ge 0 $) non posso colorare $ 15-k $ caselle di rosso rispettando le ipotesi.
Ipotizzo di poter colorare di rosso 15-k caselle di una tabella (4-k)8.
Allora posso aggiungere k righe e in ciascuna riga colorare una sola casella di rosso.
Così facendo non modifico il rispetto (o il non rispetto) delle ipotesi.
Ottengo una tabella con 4*8 righe con 15 caselle rosse che non è colorabile rispettando le ipotesi per lo step 1.
Quindi nella tabella da cui ero partito ovvero la (4-k)*8 non posso colorare di rosso 15-k caselle rispettando le ipotesi.
Posso inoltre facilmente dimostrare che in una tabella (4-k-r)*8 non posso colorare $ 15-k+s $ (con $ k,r,s \ge 0 $) caselle di rosso rispettando le ipotesi.
Infatti in una tabella (4-k-r)*8 il numero massimo di caselle colorabili di rosso rispettando le ipotesi è $ Z < 15-k-r $ $ \leq 15-k+s $
Step 3: Le tabelle 12*10 nelle quali non valgono tutti gli uguali della 5 non sono colorabili.
Considero ora una tabella 12*10.
Mantengo tutte le definizioni dello step 1 applicate ora ad una tabella con 10 righe e 12 colonne.
Posso supporre Wlog che le caselle colorate di rosso siano $ \ge 40 $.
Considero $ t_1,t_2,..t_{10} $.
Wlog $ t_1 \ge t_2 \ge ..\ge t_{10} $
Ovvero:
5) $ \frac{t_1+t_2}{2} \ge \frac{t_1+..+t_{10}}{10}\ge 4 $
Quindi se non valgono tutti gli uguali $ t_1+t_2 \ge 9 $.
Sia $ S=12- g(R_1;R_2) \leq 13-t_1-t_2 $
Esistono S colonne nelle quali né $ R_1 $ ne $ R_2 $ abbiano caselle rosse.
Le chiamo colonne fighe.
Le altre colonne le chiamo colonne normali.
Essendo $ 2 \ge p(R_1;R_i)+p(R_2;R_i) $ ciascuna riga può avere al massimo 2 caselle rosse nelle colonne normali.
Il numero massimo di caselle nelle colonne normali colorate di rosso risulta quindi:
$ 2*8+t_1+t_2 $.
Il numero minimo di caselle colorate di rosso nelle colonne fighe risulta quindi:
$ 40-16-t_1-t_2=24-t_1-t_2 $
So inoltre che le righe in cui ci possono essere delle caselle colorate di rosso in una delle colonne fighe sono tutte tranne $ R_1 $ e $ R_2 $ ovvero 10-2=8.
Sia $ 0 \ge -M = 9-t_1-t_2 $.
Il numero minimo di caselle colorate di rosso nelle colonne fighe risulta quindi:
$ 15-M $.
Il numero massimo di colonne fighe è $ 4-M $.
Ma una configurazione di questo tipo non è colorabile per lo step 2.
Step 4: Le tabelle 12*10 nelle quali valgono tutti gli uguali della 5 non sono colorabili.
Suppongo ora valgano tutti gli uguali nella 5. Ottengo:
$ \frac{t_1+t_2}{2} $ $ =\frac{t_1+..+t_{10}}{10}= 4 $ e:
$ t_1= t_2 = ..= t_{10}=4 $
Sia $ s(R_i,R_j,R_k) $ il numero di colonne t.c. abbiano una casella rossa sia nella riga i-esima sia nella riga j-esima sia nella riga k-esima.
Sia $ m(R_i,R_j,R_k,R_o) $ il numero di colonne t.c. abbiano una casella rossa sia nella riga i-esima sia nella riga j-esima sia nella riga k-esima sia nella riga o-esima.
Per ipotesi: $ s(R_i,R_j,R_k)\leq 1 $
$ m(R_i,R_j,R_k,R_o)\leq 1 $
Sia $ l_i $ il numero di caselle colorate di rosso nella colonna i-esima ($ C_i $).
Wlog $ l_1 \ge l_2 \ge .. \ge l_{12} $ quindi:
$ \frac{l_1+..+l_{12}}{12} $ $ =\frac{40}{12} $
Quindi $ l_1 \ge 4 $.
Quindi esistono almeno 4 righe t.c. la loro intersezione con $ C_1 $ sia colorata di rosso.
Considero 4 di queste righe $ (R_1,R_2,R_3,R_4) $.
Per il PIE ho che il numero di colonne t.c. abbiano tra le 4 righe $ R_1, R_2,R_3,R_4 $ almeno una casella rossa è:
$ t_1+t_2+t_3+t_4-p(R_1;R_2)- $ $ p(R_1,R_3)-p(R_1,R_4)-p(R_2,R_3)-p(R_2,R_4)-p(R_4,R_5)+ $ $ s(R_1,R_2,_R_3)+s(R_1,R_2,R_4)+s(R_1,R_3,R_4)+s(R_2,R_3,R_4) $ $ -m(R_1,R_2,R_3,R_4)=16-6+4-1=13 $
Ma ciò è assurdo perché il numero di colonne totale è 12.
Ora non resta che esibire una colorazione della tabella 11*9 (in realtà è colorabile anche la 12*9) per dimostrare che il massimo n t.c. si possa colorare una tabella (n+1)(n-1) come richiesto è 10.
Se qualcosa non è ben chiaro o ho scritto cavolate chiedete pure..
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
E bravo Enomis. E' sempre un piacere leggerti (un piacere un po' esoterico, con lati di sano masochismo, se vogliamo... Comunque, ok.
La mia soluzione è più compatta, ma prima di postarla sarei curioso di sapere se il tuo metodo si può riadattare a i casi 11x11 e 10x11 (che sono i casi "tosti" non colorabili).
La mia soluzione è più compatta, ma prima di postarla sarei curioso di sapere se il tuo metodo si può riadattare a i casi 11x11 e 10x11 (che sono i casi "tosti" non colorabili).
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Marco ha scritto: un piacere un po' esoterico, con lati di sano masochismo, se vogliamo...
Questo l'ho letto solo oggi (sono stato un po' in giro per l'Europa
) e sono tentato di mettermelo in firma 
Dunque ad occhio e croce direi di si (ho appena buttato giù 2 paginette di brutta lavorando con la 10*11) ma preferirei formalizzare bene e con calma (se riesco a trovare il tempoMarco ha scritto:sarei curioso di sapere se il tuo metodo si può riadattare a i casi 11x11 e 10x11 (che sono i casi "tosti" non colorabili).
) prima di postare.Buona serata, Simone.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Ciao. Ho un sacco di roba su questo problema, che è un peccato che rimanga solo sul mio taccuino...
L'idea è contare le coppie di caselle dello stesso colore sulla medesima riga.
Diciamo che se due caselle sono sulla stessa riga, segnamo un punto. Qundo si segna un punto, restano individuati: il colore, la riga e la coppia di colonne.
La scacchiera 10x12 non si colora.
Prendiamo una scacchiera 10x12 (12 righe da 10).
Qual è il numero minimo di punti che nascono su una stessa riga? E' facile vedere che la distribuzione più favorevole è quella più omogenea possibile: 4 di un colore, 3 degli altri. Il numero di punti è $ \binom 4 2 + \binom 3 2 + \binom 3 2 = 12 $. Ci sono 12 righe, quindi il punteggio totale è almeno 144.
Vediamo ora i punti sui singoli colori. Ci sono 3 colori, quindi c'è un colore C con almeno 48 punti. Le coppie di colonne sono $ \binom{10}{2} = 45 $, quindi c'è una coppia di colonne con almeno 2 punti in quel colore. Consideriamo le due righe e le due colonne su cui sono segnati quei due punti: le quattro case alle intersezioni sono tutte del colore C. []
Con la stessa idea si dimostra l'impossibilità dei casi 4x19 (almeno 19 punti, contro un massimo possibile di 18), 5x16 (32 contro 30), 7x13 (65 contro 63) oltre al 10x12.
Inoltre è possibile provare che si riescono a colorare i casi: 3xn, 4x18, 6x15, 9x12. Questo dice tutto sulle possibili scacchiere, eccetto tre casi 10x10, 10x11 e 11x11, che il criterio dei punti non risolve.
Vediamo il caso 11x11. Il criterio nudo e crudo non permette di escluderlo, ma una sua piccola raffinazione sì.
La scacchiera 11x11 non si colora.
Una riga dà almeno 15 punti, quindi i punti totali sono 165, con un massimo possibile di 165 punti. Un semplice conteggio non permette di dire che il caso sia impossibile, ma i punti vanno sfruttati fino all'ultimo, senza sprecare nulla. Ogni colore deve perciò avere esattamente 55 punti e ogni riga deve dare esattamente 15 punti.
Ma per dare 15 punti, l'unica possibilità è che i colori siano distribuiti sulla riga 4+4+3 (ogni altra spartizione meno omogenea dà più di 15 punti). Ma allora i colori ricevono rispettivamente 6, 6 e 3 punti. Perciò la somma dei punti sul colore deve essere multipla di 3, e non può essere 55. 11x11 non può essere colorata. []
Vediamo ora il caso tosto.
La scacchiera 10x11 non si colora.
La scacchiera ha un punteggio minimo di 132, mentre il punteggio massimo possibile è 135 (infatti ogni colore può avere al massimo 45 punti).
Step 1. Le distribuzioni possibili su una riga sono 4+3+3 (12 p.ti); 4+4+2 (13 p.ti); 5+3+2 (14 p.ti). Inoltre, c'è al massima una riga distribuita come 5+3+2.
Infatti ci sono al massimo 3 punti da scialare. Tutte le altre distribuzioni hanno più di 15 punti, facendo sballare il totale. Per l'"inoltre": ogni riga 5+3+2 sciala due punti. Se ce ne fossero due, i punti scialati sarebbero 4: troppi.
Step 2. C'è un colore a 45 punti.
Se la scacchiera ha almeno 133 p.ti, è vero per il Principio dei Cassetti. Se invece ha esattamente 132 p.ti, tutte le righe devono essere 4+3+3, quindi i punti per colore su ogni riga sono multipli di 3, quindi tutti i colori hanno punteggio multiplo di 3 e l'unico modo per sommare 132 con tre multipli di 3, senza che nessuno superi 45 è 42+45+45.
Definizione. Un colore A è un 4-colore se esistono almeno 4 righe con almeno 4 A. Le righe in questione sono dette A-righe.
Passo chiave: Sia A un 4-colore. Allora le A-righe sono al massimo 5, e contengono ognuna esattamente 4 A. Inoltre, la disposizione deve essere necessariamente la seguente (modulo scambi di righe/colonne):
A***A**AA*
*A**AA***A
**A**AA*A*
***A**AA*A
con eventualmente la quinta A-riga
AAAA******
Da qui e fino alla fine della dimostrazione del passo chiave, A è un 4-colore.
Step 3. Consideriamo 3 A-righe. Allora esiste almeno una colonna senza A sulle A-righe.
Supponiamo il contrario. Chiamiamo R1, R2, R3 le A-righe dell'enunciato. Data una colonna C, è possibile scegliere una tra R1, R2 e R3 in modo che l'intersezione tra essa e C contenga A.
Dato che A è un 4-colore, esiste almeno un'altra A-riga che chiamo R. Scelgo 4 colonne di R che contengono A. Per l'osservazione precedente posso scegliere per ognuna una riga tra R1, R2 e R3 con una A nell'intersezione. C'è una riga (diciamo R1) che è scelta due volte, in corrispondenza delle colonne C1 e C2. Allora le case alle intersezioni di C1, C2 con R e R1 sono tutte A.
Step 4. Non esiste nessuna colonna che contenga 3 A sulle A-righe.
Supponiamo che esista. Chiamo C la colonna e R1, R2, R3 le tre A righe su cui ci sono le A. Le altre A su R1, R2, R3 sono almeno 9 e devono essere su colonne distinte (altrimenti si forma un rettangolo all'intersezione con le righe incriminate). Ma allora ci devono essere A su tutte le colonne, in contraddizione con lo step 3.
Step 5. Se ci sono 5 A-righe, allora il passo chiave è vero.
Infatti, devono esserci almeno 20 A sulle A-righe. Ma ogni colonna ne contiene al massimo 2 [step 4], quindi sono esattamente 20 e ogni colonna ne contiene esattamente due. Ma allora ogni colonna individua una coppia di A-righe. Le coppie così individuate devono essere distinte (o si forma un rettangolo di A), e quindi, data una coppia di A-righe deve esistere una ed una sola colonna che contiene due A in corrispondenza delle due righe in questione. Ne segue che la disposizione è esattamente quella descritta dal passo chiave.
Step 6. Se ci sono 4 A-righe, allora il passo chiave è vero.
Chiamo R1, R2, R3, R4 le 4 A-righe. Per lo step 3, esiste C1 una colonna senza A su R2, R3, R4. Analogamente trovo C2, C3, C4. Su Ci ci può essere al massimo una A in Ri e nessun altra sulle A-righe. Ne segue che all'intersezione di C1..C4 con R1..R4 ci sono al massimo 4 A. Allora sulle 6 colonne restanti dobbiamo piazzare almeno 12 altre A (3 per riga). Per lo step 4, ci devono essere esattamente 12 A, esattamente 2 per colonna. Quindi ogni colonna individua una coppia di A-righe (necessariamente distinte). Le coppie possibili sono 6 e devono comparire esattamente una volta. Inoltre, per completare le A-righe, anche l'intersezione tra C1 con R1,..C4 con R4 devono contenere A. Ne segue che, anche in questo caso, la disposizione è esattamente quella descritta dal passo chiave.
Per completare la dimostrazione del passo chiave, basta osservare che non ci possono essere più di 5 A-righe, altrimenti ci sono troppe A, in contraddizione con lo step 4.
Sia A un colore a 45 punti. Sia $ r_k $ il numero di righe con esattamente $ k $ A. Per lo step 1, su una riga possono comparire un numero di A compreso tra 2 e 5.
Step 7. Valgono le seguenti relazioni:
$ r_5 + r_4 + r_3 + r_2 = 11 $
$ 10 r_5 + 6 r_4 + 3 r_3 + r_2 = 45 $.
La prima è il conteggio del numero di righe. La seconda è il conteggio dei punti sul colore A.
Step 8. $ r_5 + r_4 $ è pari.
Basta vedere mod. 2.
Step 9. Non esiste una soluzione accettabile con $ r_5 > 0 $.
Il passo chiave implica che se A fosse un 4-colore, allora tutte le sue A-righe contengono esattamente 4 A. Ma A ha una A-riga con 5 A, quindi non può essere un 4-colore. Ne segue che $ r_5 + r_4 < 4 $; del resto, per ipotesi non può essere 0, e per lo step 8 deve essere pari. Deve essere $ r_5 + r_4 = 2 $.
Del resto, $ r_5 $ non può essere 2 o più [step 1, parte "inoltre"]. L'unica possibilità è che $ r_5 = r_4 = 1 $. Ma allora $ r_3 + r_2 = 9 $. Dalla seconda si ha
$ 45 = 10 r_5 + 6 r_4 + 3 r_3 + r_2 \leqslant 16 + 3 ( r_3 + r_2 ) = 16 + 27 = 43 $. Assurdo.
Step 10. L'unica soluzione accettabile è $ r_2 = 0, r_3 = 7, r_4 = 4, r_5 = 0 $. Come corollario, ogni riga contiene o 3, oppure 4 A.
Per il passo chiave, $ r_4 \leqslant 5 $. Per gli step 8 e 9, $ r_4 $ è pari. Cioè, $ r_4 \leqslant 4 $.
Dalla seconda: $ 45 = 0 + 6 r_4 + 3 r_3 + r_2 = 3 (r_4 + r_3 + r_2) + 3 r_4 - 2 r_2 = $$ 33 + 3 r_4 - 2 r_2 \leqslant 33 + 12 = 45 $. Ne segue che vale l'uguaglianza, e che $ r_2 = 0, r_4 = 4 $. Di conseguenza, anche $ r_3 = 7 $.
Step 11. La soluzione precedente non è realizzabile.
Infatti: Dato che A ha 45 punti, ossia il massimo possibile, tutte le colonne devono realizzare 9 punti, che è il massimo su una colonna.
A è un 4-colore, con 4 A righe. Per il lemma chiave, esistono 6 colonne che contengono due A sulle A-righe. Diciamo che C è una di tali colonne. Ogni A su C fornisce un numero di punti pari al numero di A restanti sulla stessa riga, quindi 3 punti se siamo su una riga con 4 A, 2 punti se con 3 A. Diciamo che C ha k A. Allora, contando i punti su C, 9 = 3*2 + 2(k-2), che è pari. Contraddizione.
Ne segue che non è possibile colorare la 10x11. []
------------------------
Per finire, il caso 10x10.
Mostrerò una colorazione per la scacchiera, sfruttando le idee del passo chiave (si noti che resta valido anche su una scacchiera 10x10).
Intanto, per il PdC, ogni riga ha una colore con almeno 4 case, e, sempre per PdC, almeno 4 righe hanno il medesimo colore di maggioranza, ossia esiste almeno un 4-colore, che chiamo A.
Ne segue che posso supporre le A disposte nelle A-righe come da passo chiave:
A*** A**AA*
*A** AA***A
**A* *AA*A*
***A **AA*A
Chiamo le A-righe R1..R4. Chiamo le colonne indicando l'indice della riga [o delle righe] in cui compaiono le A sulle A-righe. In pratica le colonne si chiameranno C1, C2, C3, C4, C12, C23, C34, C14, C13, C24.
Cerchiamo ora di completare le altre righe con 3 A ognuna. Chiaramente non ci possono essere 2 A sulla stessa riga sulla parte destra (altrimenti si forma un rettangolo di A). Ne segue che ci deve essere al massimo una A a destra e almeno 2 A a sinistra. Se la A a destra compare nella colonna Cij, allora le A a sinistra non possono comparire nelle colonne Ci e Cj.
Questo porta all'idea di creare uno schema del tipo:
A*** A**AA*
*A** AA***A
**A* *AA*A*
***A **AA*A
**AA A*****
A**A *A****
AA** **A***
*AA* ***A**
*A*A ****A*
A*A* *****A
Posso chiamare le righe sfruttando la stessa idea. Le righe si chiameranno, nell'ordine, R1, R2, R3, R4, R34, R14, R12, R23, R24, R13.
Ora cambiamo colore. Vogliamo piazzare le B. Avendo un passo chiave così simpatico, sarebbe bello sfruttarlo di nuovo, dato che prescrive con precisione dove vanno messe le B.
Scelgo altre 4 righe e colonne per ripetere lo schema. Dopo qualche tentativo si trova che lo schema seguente funziona.
A**B ABBA A*
BA** AABB *A
*BA* BAAB A*
**BA BBAA *A
BBAA AB** B*
ABBA *AB* *B
AABB **AB B*
BAAB B**A *B
*A*A *B*B AB
A*A* B*B* BA
Per verificare che è lo stesso schema, numero le colonne e le righe con lo stesso criterio, appoggiandomi alle B: C14, C12, C23, C34, C4, C1, C2, C3, C13, C24; R12, R23, R34, R14, R1, R2, R3, R4, R13, R24.
Si noti che ruotando i quattro quadranti in alto a sinistra, si riottengono gli stessi quadranti, con le A e le B scambiate. Il quadrante in basso a destra è simmetrico, mentre trasponendo i restanti blocchi si scambiano gli * con A o B, a seconda della zona.
Ciao. M.
L'idea è contare le coppie di caselle dello stesso colore sulla medesima riga.
Diciamo che se due caselle sono sulla stessa riga, segnamo un punto. Qundo si segna un punto, restano individuati: il colore, la riga e la coppia di colonne.
La scacchiera 10x12 non si colora.
Prendiamo una scacchiera 10x12 (12 righe da 10).
Qual è il numero minimo di punti che nascono su una stessa riga? E' facile vedere che la distribuzione più favorevole è quella più omogenea possibile: 4 di un colore, 3 degli altri. Il numero di punti è $ \binom 4 2 + \binom 3 2 + \binom 3 2 = 12 $. Ci sono 12 righe, quindi il punteggio totale è almeno 144.
Vediamo ora i punti sui singoli colori. Ci sono 3 colori, quindi c'è un colore C con almeno 48 punti. Le coppie di colonne sono $ \binom{10}{2} = 45 $, quindi c'è una coppia di colonne con almeno 2 punti in quel colore. Consideriamo le due righe e le due colonne su cui sono segnati quei due punti: le quattro case alle intersezioni sono tutte del colore C. []
Con la stessa idea si dimostra l'impossibilità dei casi 4x19 (almeno 19 punti, contro un massimo possibile di 18), 5x16 (32 contro 30), 7x13 (65 contro 63) oltre al 10x12.
Inoltre è possibile provare che si riescono a colorare i casi: 3xn, 4x18, 6x15, 9x12. Questo dice tutto sulle possibili scacchiere, eccetto tre casi 10x10, 10x11 e 11x11, che il criterio dei punti non risolve.
Vediamo il caso 11x11. Il criterio nudo e crudo non permette di escluderlo, ma una sua piccola raffinazione sì.
La scacchiera 11x11 non si colora.
Una riga dà almeno 15 punti, quindi i punti totali sono 165, con un massimo possibile di 165 punti. Un semplice conteggio non permette di dire che il caso sia impossibile, ma i punti vanno sfruttati fino all'ultimo, senza sprecare nulla. Ogni colore deve perciò avere esattamente 55 punti e ogni riga deve dare esattamente 15 punti.
Ma per dare 15 punti, l'unica possibilità è che i colori siano distribuiti sulla riga 4+4+3 (ogni altra spartizione meno omogenea dà più di 15 punti). Ma allora i colori ricevono rispettivamente 6, 6 e 3 punti. Perciò la somma dei punti sul colore deve essere multipla di 3, e non può essere 55. 11x11 non può essere colorata. []
Vediamo ora il caso tosto.
La scacchiera 10x11 non si colora.
La scacchiera ha un punteggio minimo di 132, mentre il punteggio massimo possibile è 135 (infatti ogni colore può avere al massimo 45 punti).
Step 1. Le distribuzioni possibili su una riga sono 4+3+3 (12 p.ti); 4+4+2 (13 p.ti); 5+3+2 (14 p.ti). Inoltre, c'è al massima una riga distribuita come 5+3+2.
Infatti ci sono al massimo 3 punti da scialare. Tutte le altre distribuzioni hanno più di 15 punti, facendo sballare il totale. Per l'"inoltre": ogni riga 5+3+2 sciala due punti. Se ce ne fossero due, i punti scialati sarebbero 4: troppi.
Step 2. C'è un colore a 45 punti.
Se la scacchiera ha almeno 133 p.ti, è vero per il Principio dei Cassetti. Se invece ha esattamente 132 p.ti, tutte le righe devono essere 4+3+3, quindi i punti per colore su ogni riga sono multipli di 3, quindi tutti i colori hanno punteggio multiplo di 3 e l'unico modo per sommare 132 con tre multipli di 3, senza che nessuno superi 45 è 42+45+45.
Definizione. Un colore A è un 4-colore se esistono almeno 4 righe con almeno 4 A. Le righe in questione sono dette A-righe.
Passo chiave: Sia A un 4-colore. Allora le A-righe sono al massimo 5, e contengono ognuna esattamente 4 A. Inoltre, la disposizione deve essere necessariamente la seguente (modulo scambi di righe/colonne):
A***A**AA*
*A**AA***A
**A**AA*A*
***A**AA*A
con eventualmente la quinta A-riga
AAAA******
Da qui e fino alla fine della dimostrazione del passo chiave, A è un 4-colore.
Step 3. Consideriamo 3 A-righe. Allora esiste almeno una colonna senza A sulle A-righe.
Supponiamo il contrario. Chiamiamo R1, R2, R3 le A-righe dell'enunciato. Data una colonna C, è possibile scegliere una tra R1, R2 e R3 in modo che l'intersezione tra essa e C contenga A.
Dato che A è un 4-colore, esiste almeno un'altra A-riga che chiamo R. Scelgo 4 colonne di R che contengono A. Per l'osservazione precedente posso scegliere per ognuna una riga tra R1, R2 e R3 con una A nell'intersezione. C'è una riga (diciamo R1) che è scelta due volte, in corrispondenza delle colonne C1 e C2. Allora le case alle intersezioni di C1, C2 con R e R1 sono tutte A.
Step 4. Non esiste nessuna colonna che contenga 3 A sulle A-righe.
Supponiamo che esista. Chiamo C la colonna e R1, R2, R3 le tre A righe su cui ci sono le A. Le altre A su R1, R2, R3 sono almeno 9 e devono essere su colonne distinte (altrimenti si forma un rettangolo all'intersezione con le righe incriminate). Ma allora ci devono essere A su tutte le colonne, in contraddizione con lo step 3.
Step 5. Se ci sono 5 A-righe, allora il passo chiave è vero.
Infatti, devono esserci almeno 20 A sulle A-righe. Ma ogni colonna ne contiene al massimo 2 [step 4], quindi sono esattamente 20 e ogni colonna ne contiene esattamente due. Ma allora ogni colonna individua una coppia di A-righe. Le coppie così individuate devono essere distinte (o si forma un rettangolo di A), e quindi, data una coppia di A-righe deve esistere una ed una sola colonna che contiene due A in corrispondenza delle due righe in questione. Ne segue che la disposizione è esattamente quella descritta dal passo chiave.
Step 6. Se ci sono 4 A-righe, allora il passo chiave è vero.
Chiamo R1, R2, R3, R4 le 4 A-righe. Per lo step 3, esiste C1 una colonna senza A su R2, R3, R4. Analogamente trovo C2, C3, C4. Su Ci ci può essere al massimo una A in Ri e nessun altra sulle A-righe. Ne segue che all'intersezione di C1..C4 con R1..R4 ci sono al massimo 4 A. Allora sulle 6 colonne restanti dobbiamo piazzare almeno 12 altre A (3 per riga). Per lo step 4, ci devono essere esattamente 12 A, esattamente 2 per colonna. Quindi ogni colonna individua una coppia di A-righe (necessariamente distinte). Le coppie possibili sono 6 e devono comparire esattamente una volta. Inoltre, per completare le A-righe, anche l'intersezione tra C1 con R1,..C4 con R4 devono contenere A. Ne segue che, anche in questo caso, la disposizione è esattamente quella descritta dal passo chiave.
Per completare la dimostrazione del passo chiave, basta osservare che non ci possono essere più di 5 A-righe, altrimenti ci sono troppe A, in contraddizione con lo step 4.
Sia A un colore a 45 punti. Sia $ r_k $ il numero di righe con esattamente $ k $ A. Per lo step 1, su una riga possono comparire un numero di A compreso tra 2 e 5.
Step 7. Valgono le seguenti relazioni:
$ r_5 + r_4 + r_3 + r_2 = 11 $
$ 10 r_5 + 6 r_4 + 3 r_3 + r_2 = 45 $.
La prima è il conteggio del numero di righe. La seconda è il conteggio dei punti sul colore A.
Step 8. $ r_5 + r_4 $ è pari.
Basta vedere mod. 2.
Step 9. Non esiste una soluzione accettabile con $ r_5 > 0 $.
Il passo chiave implica che se A fosse un 4-colore, allora tutte le sue A-righe contengono esattamente 4 A. Ma A ha una A-riga con 5 A, quindi non può essere un 4-colore. Ne segue che $ r_5 + r_4 < 4 $; del resto, per ipotesi non può essere 0, e per lo step 8 deve essere pari. Deve essere $ r_5 + r_4 = 2 $.
Del resto, $ r_5 $ non può essere 2 o più [step 1, parte "inoltre"]. L'unica possibilità è che $ r_5 = r_4 = 1 $. Ma allora $ r_3 + r_2 = 9 $. Dalla seconda si ha
$ 45 = 10 r_5 + 6 r_4 + 3 r_3 + r_2 \leqslant 16 + 3 ( r_3 + r_2 ) = 16 + 27 = 43 $. Assurdo.
Step 10. L'unica soluzione accettabile è $ r_2 = 0, r_3 = 7, r_4 = 4, r_5 = 0 $. Come corollario, ogni riga contiene o 3, oppure 4 A.
Per il passo chiave, $ r_4 \leqslant 5 $. Per gli step 8 e 9, $ r_4 $ è pari. Cioè, $ r_4 \leqslant 4 $.
Dalla seconda: $ 45 = 0 + 6 r_4 + 3 r_3 + r_2 = 3 (r_4 + r_3 + r_2) + 3 r_4 - 2 r_2 = $$ 33 + 3 r_4 - 2 r_2 \leqslant 33 + 12 = 45 $. Ne segue che vale l'uguaglianza, e che $ r_2 = 0, r_4 = 4 $. Di conseguenza, anche $ r_3 = 7 $.
Step 11. La soluzione precedente non è realizzabile.
Infatti: Dato che A ha 45 punti, ossia il massimo possibile, tutte le colonne devono realizzare 9 punti, che è il massimo su una colonna.
A è un 4-colore, con 4 A righe. Per il lemma chiave, esistono 6 colonne che contengono due A sulle A-righe. Diciamo che C è una di tali colonne. Ogni A su C fornisce un numero di punti pari al numero di A restanti sulla stessa riga, quindi 3 punti se siamo su una riga con 4 A, 2 punti se con 3 A. Diciamo che C ha k A. Allora, contando i punti su C, 9 = 3*2 + 2(k-2), che è pari. Contraddizione.
Ne segue che non è possibile colorare la 10x11. []
------------------------
Per finire, il caso 10x10.
Mostrerò una colorazione per la scacchiera, sfruttando le idee del passo chiave (si noti che resta valido anche su una scacchiera 10x10).
Intanto, per il PdC, ogni riga ha una colore con almeno 4 case, e, sempre per PdC, almeno 4 righe hanno il medesimo colore di maggioranza, ossia esiste almeno un 4-colore, che chiamo A.
Ne segue che posso supporre le A disposte nelle A-righe come da passo chiave:
A*** A**AA*
*A** AA***A
**A* *AA*A*
***A **AA*A
Chiamo le A-righe R1..R4. Chiamo le colonne indicando l'indice della riga [o delle righe] in cui compaiono le A sulle A-righe. In pratica le colonne si chiameranno C1, C2, C3, C4, C12, C23, C34, C14, C13, C24.
Cerchiamo ora di completare le altre righe con 3 A ognuna. Chiaramente non ci possono essere 2 A sulla stessa riga sulla parte destra (altrimenti si forma un rettangolo di A). Ne segue che ci deve essere al massimo una A a destra e almeno 2 A a sinistra. Se la A a destra compare nella colonna Cij, allora le A a sinistra non possono comparire nelle colonne Ci e Cj.
Questo porta all'idea di creare uno schema del tipo:
A*** A**AA*
*A** AA***A
**A* *AA*A*
***A **AA*A
**AA A*****
A**A *A****
AA** **A***
*AA* ***A**
*A*A ****A*
A*A* *****A
Posso chiamare le righe sfruttando la stessa idea. Le righe si chiameranno, nell'ordine, R1, R2, R3, R4, R34, R14, R12, R23, R24, R13.
Ora cambiamo colore. Vogliamo piazzare le B. Avendo un passo chiave così simpatico, sarebbe bello sfruttarlo di nuovo, dato che prescrive con precisione dove vanno messe le B.
Scelgo altre 4 righe e colonne per ripetere lo schema. Dopo qualche tentativo si trova che lo schema seguente funziona.
A**B ABBA A*
BA** AABB *A
*BA* BAAB A*
**BA BBAA *A
BBAA AB** B*
ABBA *AB* *B
AABB **AB B*
BAAB B**A *B
*A*A *B*B AB
A*A* B*B* BA
Per verificare che è lo stesso schema, numero le colonne e le righe con lo stesso criterio, appoggiandomi alle B: C14, C12, C23, C34, C4, C1, C2, C3, C13, C24; R12, R23, R34, R14, R1, R2, R3, R4, R13, R24.
Si noti che ruotando i quattro quadranti in alto a sinistra, si riottengono gli stessi quadranti, con le A e le B scambiate. Il quadrante in basso a destra è simmetrico, mentre trasponendo i restanti blocchi si scambiano gli * con A o B, a seconda della zona.
Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Scusate se riesumo questo post ormai chiuso ed archiviato, ma la soluzione mi pare troppo intricata... (il che mi tormenta la notte, della serie "now are thoughts thou shalt not banish, now are visions ne'er to vanish, from thy spirit shall they pass no more...")... Non si riesce a trovarne una piu' semplice? Adesso provo a cercarne una piu' semplice anch'io.
Boh... se lo dici tu... La mia soluzione sono solo sette righe. Tutto il resto è generalizzazione. Comunque, ogni suggerimento è più che ben accetto.Catraga ha scritto:ma la soluzione mi pare troppo intricata...
Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."