Griglia di punti colorati

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Griglia di punti colorati

Messaggio da Gianfranco »

Considerate una griglia rettangolare formata da 3 × 9 punti.
Ogni punto è colorato di bianco o di nero, in modo del tutto casuale.
Dimostrate che in tale griglia, comunque siano colorati i punti, esiste un rettangolo che ha i vertici dello stesso colore.
Si assume che i lati del rettangolo sono paralleli ai lati della griglia.

Quali sono le dimensioni minime, a × b, della griglia affinchè tale rettangolo esista?
Pace e bene a tutti.
Gianfranco

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

La dimensione minima è 3 x 7.
Per dimostrare la prima parte basta cambiare nome a questo sito: da 5 a 2.

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

Un'altra domanda:
con la condizione che la dimensione minima sia più di 2; qual è la griglia di dimensione massima, come area o perimetro, in cui sia possibile colorare i punti senza che esistano rettangoli con vertici del medesimo colore?

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Griglia di punti colorati

Messaggio da Gianfranco »

3 x 7 risposta esatta.

Gnugnu ha scritto:
Con la condizione che la dimensione minima sia più di 2; qual è la griglia di dimensione massima, come area o perimetro, in cui sia possibile colorare i punti senza che esistano rettangoli con vertici del medesimo colore?
Ho fatto un programmino che genera tutte le possibili griglie di dimensioni date e le valuta.
Per ora ho esaminato solo le griglie quadrate:
4x4 - è possibile
5x5 - non è possibile, cioè qualunque sia la colorazione (binaria) c'é sempre qualche (almeno 2?) rettangolo con i vertici dello stesso colore.

Quindi rimane da provare 4x5 e 4x6.
Pace e bene a tutti.
Gianfranco

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

Gianfranco ha scitto:
5x5 - non è possibile, cioè qualunque sia la colorazione (binaria) c'é sempre qualche (almeno 2?) rettangolo con i vertici dello stesso colore.
Sì. Si può dimostrare (anche senza computer) che ne esistono sempre almeno 2, costretti a condividere <modificato in:> se questi hanno in comune un vertice; eliminandolo si ottiene un reticolo 5 x 5 bucato, privo di rettangoli monocromatici che, a proposito di ordine nel disordine, può essere reso molto simmetrico.
reticolo.png
reticolo.png (22.06 KiB) Visto 22524 volte
Riporto la tua figura (fig. 2) con accanto una cosa (fig. 3), apparentemente molto diversa, ottenuta (dopo aver cancellato il punto centrale) scambiando la prima colonna con la quarta e la prima riga con la seconda. Queste operazioni non modificano il numero di rettangoli monocromatici.
Utilizzando queste manipolazioni (ed altre ammissibili quali rotazioni, simmetrie e scambio dei colori) si riducono drasticamente i casi possibili. Per la 5 x 5 bucata sono arrivato a due possibilità, con la speranza di ridurle ad una.

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

Ho finito di giocare coi punti colorati (veramente sono in bianco e nero).
reticolo2.png
reticolo2.png (11.57 KiB) Visto 22509 volte
In fig. 1 il reticolo 5 x 5, senza il punto centrale, privo di rettangoli monocromatici (ReMo). Aggiungendo il punto centrale si ottengono, qualunque sia il colore di questo, 2 ReMo aventi nel punto un vertice in comune.

In fig. 2 un reicolo 5 x 5 con 2 ReMo senza vertici comuni, indipendente dal colore del punto centrale X.
Le due figure differiscolo solo per l'inversione dei colori sulla diagonale principale.

A meno di trasformazioni che non modificano il numero di ReMo: scambio di due linee parallele (righe o colonne), simmetrie e rotazioni del quadrato, inversione del colori di tutti i punti; la soluzione di fig, 1 è unica. Credo lo sia anche quella di fig, 2, ma non l'ho accertato; sarei grato a chi ne trovasse una (con non più di 2 ReMo) non riconducibile a queste.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Griglia di punti colorati

Messaggio da Gianfranco »

Gnugnu, mi piacciono anche esteticamente i risultati delle tue ricerche.
Devo però ancora comprenderli meglio dal punto di vista matematico.
Non so se le seguenti figure rispondono alla tua ultima domanda.
reticoli_2col357.png
reticoli_2col357.png (16.78 KiB) Visto 22484 volte
Sono i primi reticoli che ha trovato il mio programmino, contenenti rispettivamente 3, 5, 7 rettangoli.
Tra parentesi, grazie alle tue indicazioni ho dimezzato i tempi di ricerca del programma.
Pace e bene a tutti.
Gianfranco

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

@Gianfranco:
Gnugnu, mi piacciono anche esteticamente i risultati delle tue ricerche.
Non ne so il motivo, forse perché gli umani, e buona parte di quel che li accompagna nal loro viaggio, presentano (grosso modo) simmetrie, forse perchè il cervello risparmia spazio di memoria per ricordarle, ma le figure simmetriche risultano gradevoli. Al punto che di fronte a cose, esempio molte cattedrali, che presentano tanti particolari asimmetrici in un contesto solo grossolanamente simmetrico, per cogliere i primi dobbiamo ricercarli con attenzione.
Non so se le seguenti figure rispondono alla tua ultima domanda.
Come la maggior parte di coloro che amano divertirsi con la matematica, sei un po' distratto: avevo chiesto soluzioni con non più di due rettangoli monocromatici. :)
Tra parentesi, grazie alle tue indicazioni ho dimezzato i tempi di ricerca del programma.
Felice di esserti stato, anche se di poco, utile, Non conosco come hai impostato la ricerca, ma già il solo scambio delle righe, permette di esaminare solo le cinquine ordinate (in una qualche maniera) e dovrebbe ridurre il tempo di un fattore superiore a 100. Se ne hai voglia dammi qualche indicazione sul procedimento seguito. Aspetto ancora qualche giorno, per dare modo ad altri di intervenire, poi posto il percorso completo senza l'uso del computer.
Ciao

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Griglia di punti colorati

Messaggio da Gianfranco »

@Bruno
Come passa veloce il tempo! Avevo letto e apprezzato la tua mail il 30 settembre e mi ero proposto di risponderti dopo aver inserito il link nella pagina dei 4 4. E siamo già all'11 ottobre! Chiedo scusa e ti risponderò privatamente. A presto.

@Gnugnu
Dannazione! Mi era sfuggito il "non".
Procederò con l'esame delle griglie a 2 ReMo. Però devo prima aggiungere al programmino il test per verificare se si tratta di uno dei due casi da te proposti.
Per evitare altri errori, i due casi sono:
a) tolto il punto centrale, spariscono i 2 ReMo;
b) con il punto centrale i due ReMo non hanno vertici comuni.
La domanda è: esistono casi a 2 ReMo non riconducibili a questi 2?
Giusto?
Pace e bene a tutti.
Gianfranco

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

@Gianfranco:
... i due casi sono:
a) tolto il punto centrale, spariscono i 2 ReMo;
b) con il punto centrale i due ReMo non hanno vertici comuni.
La domanda è: esistono casi a 2 ReMo non riconducibili a questi 2?
Giusto?
Si, ma nel frattempo mi sono tolto il dubbio: (Se&o) non esistono.
Ciao

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Griglia di punti colorati

Messaggio da Gianfranco »

Sono contento che tu abbia risolto la questione e anch'io tiro un sospiro di sollievo.
L'impresa informatica, anche limitandosi alla brute force, non era proprio semplicissima.
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Griglia di punti colorati

Messaggio da Gianfranco »

Gnugnu, ti pongo una domanda per capire meglio cosa intendi con i due esempi che hai portato.
Dunque, esistono 2^25=33 554 432 griglie diverse 5x5 con i punti colorati in bianco o nero.
Di queste, ce ne sono circa 24 000 che contengono esattamente due ReMo.
La domanda è: questi 24 000 casi si possono ricondurre alle due tipologie che hai presentato?
Pace e bene a tutti.
Gianfranco

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

Gianfranco, se non ho sbagliato qualcosa - contro gli errori non sono vaccinato - direi proprio di sì.
Con i numeri direi che ci stiamo comodamente.
Tutte due hanno un punto speciale che può essere colorato in due modi, perciò diventano 4 invertendo i colori.
Con la rotazione di 90° (le altre simmetrie e rotazioni del quadrato si possono ottenere dallo scambio di linee) saliamo ad 8.
Le cinque linee si possono disordinare in 5!=120 modi diversi e lo si può fare con le righe e con le colonne.
In tutto 8*120^2=115200 rimescolamenti. Se le soluzioni sono solo 24000 vorrà dire che, mediamente, circa 5 casi finiscono per coincidere; cioè i punti colorati cambiano posizione ma ogni nero finisce in un nero e ogni bianco in un bianco.
Domani posto la dimostrazione.

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

In qualunque maniera si colorino (con due soli colori diversi) i punti di un reticolo 9 x 3, esisterà almeno un ReMo (rettangolo con vertici del medesimo colore e lati paralleli a quelli del reticolo).
Per dimostrarlo può essere comodo rappresentare i due colori con i simboli 0 e 1 e pensare le 9 terne di punti come scritture binarie di numeri.
I numeri che si possono scrivere con tre sole cifre sono 8 (da 0 a 7), per il principio dei cassetti, si avranno perciò almeno due numeri coincidenti. In un numero binario di tre cifre almeno due di queste devono essere uguali e costituiscono, nei due numeri uguali trovati, i vertici di un ReMo.
Per trovare il più grande reticolo n x 3 colorabile senza ReMo osserviamo che i numeri 0 e 7, sono scritti (in base 2) con tre cifre uguali e, perciò, formano ReMo con qualunque altro numero che contenga due di tali cifre. Eliminandoli, i restanti 6 numeri (da 1 a 6) non formano alcun ReMo,
Questo reticolo 6 x 3 privo di ReMo può essere facilmente trasformato in un 6 x 4 aggiungendo ad ogni numero una quarta cifra uguale a quella presente una sola volta.
Per poter lavorare in modo testo rappresento i colori (le cifre binarie) con i simboli O e X che hanno la stessa larghezza.
O O X . . . . . O O X X
O X O . . . . . O X O X
X O O . . . . . X O O X
O X X . . . . . O X X O
X O X . . . . . X O X O
X X O . . . . . X X O O

Il reticolo 6 x 4 è il più grande colorabile senza ReMo; per dimostrarlo occorre studiare il 5 x 5 e verificare che compare sempre almeno un ReMo, anzi due.

Il numero dei casi da esaminare si può ridurre drasticamente utilizzando le trasformazioni di un reticolo che non modificano, qualunque sia la colorazione, il numero dei ReMo presenti.
Queste sono: permutazione di linee parallele (righe o colonne), inversione dei colori e tutte le isometrie del piano che non modificano il rettangolo che delimita il reticolo.
Due o più reticoli colorati riconducibili, mediante una sequenza delle trasformazioni precedenti, alla medesima configurazione saranno equivalenti. Solo quando la trasformazione risulta impossibile abbiamo due colorazioni distinte.
La parte seguente scritta in blu può apparire come un noioso esercizio di pignoleria, con un minimo di fiducia può essere saltata.

Ad esempio le colorazioni prive di ReMo di un reticolo 6 x 4 sono tutte equivalenti, lo stesso succede per un reticolo 5 x 4, sono invece distinte le seguenti colorazioni del reticolo 4 x 4:
O O X X . . . . . O O X X
O X O X . . . . . O X O X
X O O X . . . . . X O O X
X X X O . . . . . O X X O
nella seconda troviamo il medesimo numero di O e X, nella prima no.
Mostrare che tutti le colorazioni 6 x 4 prive di ReMo sono equivalenti è facile. Le possibili quaterne equilibrate (con 2 O e 2 N) sono solo quelle e l'eventuale presenza di una o più quaterne non equilibrate comporta l'impossibilità di una colorazione priva di ReMo, perché, togliendo un'opportuna colonna resterebbe un reticolo 6 x 3 con tre segni uguali in una riga.
Qualsiasi trasformazione ammissibile produrrà sempre solo un cambiamento dell'ordine delle righe che può essere ripristinato modificando la disposizione di queste. Abbiamo 6!=720 colorazioni equivalenti.
Eliminando una riga dal 6 x 4 (si può assumere come base quello del primo disegno) otteniamo 6 reticoli 5 x 4, che possono essere ricondotti a quello ottenuto dalla cancellazione della prima riga. Di seguito i passaggi relativi alla cancellazione della quarta.
Invertendo i colori si ottiene nella quarta colonna il 'giusto' numero di X e O; scambiano la prima colonna con la terza si fanno comparire le opportune quaterne terminanti con X; a questo punto tutte le quaterne sono quelle volute e basta riordinarle scambiando le righe.
O O X X . . . . . X X O O . . . . . O X X O . . . . . O X O X
O X O X . . . . . X O X O . . . . . X O X O . . . . . X O O X
X O O X . . . . . O X X O . . . . . X X O O . . . . . O X X O
X O X O . . . . . O X O X . . . . . O X O X . . . . . X O X O
X X O O . . . . . O O X X . . . . . X O O X . . . . . X X O O
L'inversione dei colori non è indispensabile: analogo risultato può ottenersi scambiando l'ultima colonna con una di quelle in cui compaiono due X.


(segue)

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Griglia di punti colorati

Messaggio da gnugnu »

Un reticolo 5 x 5 senza ReMo privato della sua ultima colonna deve diventare un reticolo 5 x 4 altrettanto ReMo-free. Partendo, allora, da uno qualsiasi di questi ultimi (sono tutti equivalenti) si può provare a colorare un'ulteriore colonna senza creare un ReMo: operazione impossibile.
Partendo, ad esempio da quello privato della prima riga (l'ultimo nel disegno precedente), notiamo che la prima e quarta riga sono complementari, così come la seconda e la terza, solo l'ultima è speciale: era nel 6 x 4 complementare della prima che è stata tolta.
Una coppia di righe complementari non crea alcun problema: possiamo aggiungere in quinta posizione il simbolo che preferiamo e non nasce alcun ReMo. Al contrario, due righe che non lo siano hanno sempre due coincidenze di simboli: in una posizione appare O in entrambe, in un'altra X. L'unico modo per impedire la formazione di un ReMo è scrivere in quinta colonna due simboli diversi: O in una e X nell'altra.
Pertanto le sole colorazioni della quinta colonna che non producono ReMo nelle prime 4 righe sono le due indicate in figure, purtroppo, qualunque sia il simbolo posto nella posizione Q, nasceranno due ReMo aventi in Q un vertice in comune.

O X O X . . O . . X . | . O . . O . . X . . X
X O O X . . X . . O . | . X . . X . . O . . O
O X X O . . X . . O . | . X . . X . . O . . O
X O X O . . O . . X . | . O . . O . . X . . X
X X O O . . Q . . Q . | . O . . X . . O . . X

Abbiamo quattro colorazioni diverse di un 5 x 5 (le 4 colonne di partenze giustapposte ad una delle 4 disegnate dopo la barra verticale) che comportano due ReMo, le restanti $2^5-4=28$ ne presentano almeno tre. Le colonne con 4 o 5 simboli uguali si scartano immediatamente, ne restano 16 con tre simboli di un tipo e due dell'altro: se non siete convinti, basta provare!
Dunque un reticolo 5 x 5 presenta sempre almeno due ReMo. Notando che, nel caso ne presentasse uno solo, cancellando la colonna cui appartiene un lato del medesimo si otterrebbe comunque un 5 x 4 ReMo-free, mi ero convinto che quelli trovati fossero gli unici possibili e che pertanto i due ReMo dovessero presentare sempre un vertice in comune.
Bella cantonata che ha portato alla correzione di un mio precedente intervento [a proposito! Qualcuno sa dirmi come si può ottenere il carattere barrato? Ho provato con i tag <strike> </strike> dell'HTML, ma non funziona].
Dimostrare che le quattro colorazioni trovate sono equivalenti alla fig. 1, che riporto è poco più di un gioco. Possiamo fare una gara a chi ci riesce in meno mosse.
reticolo2.png
reticolo2.png (11.57 KiB) Visto 22403 volte
Resta da esaminare il caso di due ReMo coni lati appartenenti a linee tutte diverse, se così non fosse, cancellando la linea in comune si ricadrebbe, magari dopo una lecita rotazione di 90°, nel caso precedente .
Cacellando le due colonne su cui si trovano i lati dei due ReMo (una per ciascuno) residua un 5 x 3 ReMo-free. Questa volta, tanto per non annoiarci, partiamo da quello mancante della quarta riga. Restano due colonne da colorare, 32^2=1024 maniere possibili, tantine per essere affrontate a mano, ma fortunatamente sono possibili semplificazioni.
La riga che difetta della sua complementare è adesso la terza. La prima è complementare dell'ultima e la seconda della quarta.
O O X . . . . . O . . O . . X . . X
O X O . . . . . X . . X . . O . . O
X O O . . . . . X . . X . . X . . X
X O X . . . . . O . . X . . O . . O
X X O . . . . . O . . O . . O . . X

Dobbiamo colorare la quarta colonna in modo da formare uno ed un solo ReMo.
Mettendo una O in terza riga, qualunque colorazione delle restanti quattro porterebbe a più di un ReMo (mettendo quattro X se ne trovano 3, mettendo tre X e una O un ReMo in corrispondenza della O ed almeno un altro fra le X, mettendo due o più O almeno uno in corrispondenza di ciascuna O).
Siamo costretti a mettere X e restano 16 possibilità fra cui solo le quattro indicate sul disegno sono accettabili. Ma anche per la quinta colonna abbiamo le stesse condizioni ed otteniamo le stesse possibili colorazioni.
Resta da abbinare la quarta colonna con la quinta, due colonne uguali sono da escludere e lo scambio dei posti è ininfluente, quindi sei sole possibilità quattro delle quali non sono accettabili.
La prima può essere abbinata solo con l'ultima: negli altri due casi nasce fra le due un ReMo di troppo. La seconda solo con la terza: nell'altro caso i due ReMo avrebbero un vertice in comune nella terza riga. La terza non può essere abbinata con la quarta, perché si forma fra loro un ReMo in seconda e quarta riga, Due sole soluzioni: quelle disegnate sotto.

O O X O X . . . . . O O X O X
O X O X O . . . . . O X O X O
X O O X X . . . . . X O O X X
X O X O O . . . . . X O X X O
X X O O X . . . . . X X O O O

Che sono equivalenti, molto 'vicine': differiscono solo per lo scambio degli elementi in posizione 4,4 e 5,5. Eppure, stranamente, servono ben quattro passaggi elementari per trasformarne una nell'altra: lo scambio delle colonne 2 con 3 e 4 con 5; lo scambio delle righe 1 con 2 e 4 con 5.

Rispondi