Quiz: Coloriamo le progressioni aritmetiche **/***
Una progressione aritmetica è una successione di numeri naturali tale che la differenza tra due termini successivi è costante.
Per esempio 7, 10, 13, 16 è una progressione aritmetica in cui la differenza tra due termini successivi è tre.
Consideriamo i numeri da 1 a 9:
1 2 3 4 5 6 7 8 9
Supponiamo che ciascuno dei numeri da 1 a 9 venga colorato di rosso o di blu(in qualsiasi modo possibile).
E' vero o falso che vi saranno sempre tre numeri rossi o tre numeri blu in progressione aritmetica?
Dimostrare come uno meglio crede. Questo quiz vi ricorda qualcosa?
7 commenti
Il massimo numero di elementi di due colori diversi che si possono disporre in sequenza senza generare una progressione aritmetica di tre termini di uguale colore è 8.
Dispongo una coppia rossa, poi una blu, ancora una rossa e infine una blu:
1. 2. 3. 4. 5. 6. 7. 8.
A questo punto. se il 9 fosse blu, avrei una sequenza blu 7 8 9 di ragione 1.
Se invece il nove fosse rosso, avrei una sequenza rossa 1 5 9 di ragione 4.
Vedo una analogia con il problema della colorazione con due colori di un grafo K6.
La disposizione dei primi 8 elementi può assumere anche altre configurazioni, come ad esempio, questa:
1. 2. 3. 4. 5. 6. 7. 8.
Anche in questo caso, fino a 8, non ci sono progressioni monocromatiche di tre elementi. Ma quando aggiungo il 9, se lo scrivo in rosso avrò la sequenza rossa: 1 5 9 di ragione 4. Se invece lo scrivo in blu avro la sequenza blu 3 6 9 di ragione 3.
Oppure, con altra simmetria speculare, questa:
1. 2. 3. 4. 5. 6. 7. 8.
Il 9 rosso crea 3 6 9. ragione 3
Il 9 blu crea 5 7 9. ragione 2.
In ogni caso con 8 elementi il sistema di colorazione ha raggiunto una sorta di "saturazione".
Per soddisfare compiutamente la richiesta occorre ovviamente pensare ad una generalizzazione formale.
quindi tu affermi che è vero. I tuoi esempi danno un risultato concreto. Ma al solito bisogna generalizzare.
Si, l'enunciato è proprio simile a quello dei triangoli in K6. D'altronde i problemi di Ramsey sono applicabili a qualsiasi insieme.
Aggiungo, solo per completezza, il ragionamento che ho seguito per arrivare alle conclusioni precedenti.
Ho analizzato le colorazioni dei primi 8 elementi che non producano già una serie (di ragione 1 o 2 o 3)
al fine di poter valutare facilmente le due alternative di colore per il 9° ed ultimo elemento.
Gli 8 elementi iniziali devono essere 4 di un colore e 4 dell'altro colore, perché se fossero sbilanciati, ossia
5 e 3 oppure 6 e 2 oppure 7 e 1, si sarebbe già creata una serie.
Le possibili colorazioni sui primi 4 numeri sono 16 ma 8 colorazioni sono la negazione delle altre 8.
Quindi basta studiare solo 8 casi.
Indico genericamente i colori con 0 e 1
1 2 3 4
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
Di queste 8 righe mantengo solo quelle che sono bilanciate, con uguale numero di 0 e di 1.
1 2 3 4
0 0 1 1
0 1 0 1
0 1 1 0
Completo ciascuna riga, affiancando alle colorazioni presenti (associate ai numeri da 1 a 4) le successive 4 ( associate numeri da 5 a 8 ) sempre bilanciando la presenza di 1 e 0.
1 2 3 4 5 6 7 8
0 0 1 1 0 0 1 1 citata nel commento 1
0 1 0 1 1 0 1 0 commento 2
0 1 1 0 0 1 1 0 commento 2
Come già visto nei commenti, per ciascuna di esse, l'aggiunta del 9° elemento genera una serie.
Ok Maurizio intanto grazie, mentre aspettiamo anche altre risposte.
Caso proposto nel quiz: serie di numeri da 1 a 9
Rappresento i numeri da 1 a 9 come vertici di un ennagono, un grafo di 9 nodi.
I colori dei collegamenti rappresentano le possibili serie aritmetiche di ragione 1, 2, 3 , 4.
neri = ragione 1,
rossi = ragione 2,
verdi = ragione 3
blu = ragione 4 (massimo)
Divido i 9 nodi in due sottogruppi : uno di 4 nodi e l'altro di 5 nodi .
Non è possibile collegare 5 nodi (del sottogruppo più numeroso) con un percorso in cui non vi siano mai due lati consecutivi dello stesso colore.
Quindi è vero che si crea sempre una serie di tre elementi.
Confronto con una serie di numeri più piccola
Considerando solo i numeri da 1 a 6: avremo il grafo a forma di esagono.
I colori dei collegamenti seguono le stesse regole di prima:
neri = ragione 1,
rossi = ragione 2 (massimo)
Questi 6 nodi vanno suddivisi in due gruppi, entrambi di 3 nodi.
E' possibile collegare i 3 nodi di un sottogruppo con un percorso in cui non ci sono
due lati consecutivi dello stesso colore.
Quindi non è vero che si crea sempre una serie di tre elementi.
si, comunque noi limitiamoci al caso del quiz; nove numeri da 1 a 9.