Sempre tre

[Bruno]

...

Abbiamo la rassicurante sequenza:

$1,\,2,\,3,\,4,\,5,\,6,\,7,\,8,\,9$

e due pennarelli di colore diverso.

Qualunque sia il criterio scelto per colorare
ciascuna di queste cifre, troveremo sempre
(ma proprio sempre) tre numeri di ugual
colore in progressione aritmetica.


Bruno

[mathmum]

Mi sono armata di pennarelli giallo e verde, ho iniziato a colorare, al momento la vedo così, da un punto di vista algebrico: devo trovare il modo di dividere l'insieme costituito da 1,2...9 in due sottoinsiemi, di cui almeno uno contenga tre numeri in progressione aritmetica.
1, 5, 9 giallo! -> progressione aritmetica

e mi fermo qui, perchè
1. è tardi (per me!)
2. il figliuol prodigo si sta prodigando a rompere
3. sta arrivando il MrMath dal lavoro

ciao!

[Gianfranco]

Dimostrazione banale.
Considero 8 numeri così colorati (G=giallo, V=verde):
1 2 3 4 5 6 7 8
G V V G G V V G

Gialli: 1, 4, 5, 8
Verdi: 2, 3, 6, 7
Lo schema dimostra che si possono colorare 8 numeri in modo da non averne 3 dello stesso colore in successione aritmetica.

Ma se aggiungo il numero 9, in qualunque modo lo coloro, avrò sempre una successione.

a) se lo coloro di giallo ho:
Gialli: 1, 4, 5, 8, 9; (1, 5, 9 in successione)

b) se lo coloro di verde ho:
Verdi: 2, 3, 6, 7, 9 (3, 6, 9 in successione)

Dimostrazione più divertente e aperta a possibili generalizzazioni.

Ho costruito questa tabella e mi sono divertito a fare un po' di tiro a segno.
Sono tutte le possibili terne (16) di numeri in progressione aritmetica.
Supponiamo che siano tutti gialli. Allora ho 16 progressioni GIALLE.

[VEDI FIGURA]

Il gioco consiste nel tentare di demolirle tutte sparando del colore verde ad alcuni numeri.
Ad esempio se sparo al numero 5 demolisco ben 8 progressioni.
Se poi sparo anche al 4 ne demolisco in tutto 12.
Ma 4 sopravvivono INTEGRE!
Attenzione: se nei miei colpi ce ne sono 3 in progressione aritmetica, sono fregato! Infatti così si formano 3 numeri verdi in progressione aritmetica.

Allora, vediamo come si può fare.

1) Se ho 1 solo colpo, divido la sequenza 1, 2, 3, 4, 5, 6, 7, 8, 9 in due parti di cui una è certamente formata da ALMENO 4 termini in progressione. Un solo colpo non basta.

2) Se ho 2 colpi, divido la sequenza in 3 parti di cui una è certamente formata da ALMENO 3 termini in progressione. Due colpi non bastano.

----------------------------------------------------
La parte viola è errata: non leggere.
3) Se ho 3 colpi e sto attento a non spararli in progressione aritmetica VI GARANTISCO che ALMENO una di quelle progressioni gialle sopravvive intera perché se non sopravvivesse vorrebbe dire che ho sparato il verde proprio su quei tre numeri e perciò non sono stato abbastanza attento e ora mi ritrovo con tre numeri verdi in successione aritmetica.

4) Se ho 4 colpi a disposizione, vale esattamente il discorso precedente.
-----------------------------------------------------

5) Da 5 colpi in avanti, per simmetria, la situazione si inverte. E' come se i numeri fossero tutti verdi e io sparassi il giallo.
Infatti:
9 = 1+8 = 2+7 = 3+6 = 4+5 = 5+4 = 6+3 = 7+2 = 8+1

Ora che ci penso, i casi sono 2: o che ho fatto un errore o che ho trovato una dimostrazione scema del teorema di Van der Waerden.
Per favore, trovate l'errore!

Gianfranco

[Gianfranco]

Come c'era da aspettarsi, la cosa è più complicata di quanto sembra a prima vista.

Per i punti 3) e 4) le cose cambiano così: devo dimostrare che cambiando colore (da giallo a verde) a 3 o a 4 numeri (che non siano in progressione) non riesco a demolire TUTTE le 16 terne gialle in progressione. Ne rimane sempre almeno una integra.
Bisogna esaminare diversi sottocasi.

Per il punto 3), tento questo abbozzo di ragionamento che si basa sulle DIFFERENZE fra i numeri a cui cambio colore.

a) devo cambiare colore a 3 numeri;

b) la DIFFERENZA fra 2 di essi può essere 1, 2, 3, 4, 5, 6, 7, 8

---------------------------
Ci risiamo: la parte viola contiene degli errori, non leggere.

c) se è 1, qualunque sia il terzo numero, si salva almeno una delle terne numerate da 1 a 7 nel disegno (1,2,3 - 2,3,4 - 3,4,5 - etc.)

d) se è 2, (e la differenza fra ciascuno di essi e il terzo è diversa da 1 perché altrimenti cadiamo nel caso precedente) qualunque sia il terzo numero, si salva almeno una delle terne numerate da 8 a 12 nel disegno (post precedente)

e) se è 3, (e le altre differenze sono diverse da 1 e a 2), si salva almeno una delle terne numerate da 13 a 15 nel disegno
---------------------------------

f) se è >=4 dobbiamo per forza ricadere in uno dei casi precedenti, per simmetria.


Per il punto 4) ...???

Gianfranco

[delfo52]

espongo l'inizio del mio modo di procedere:
prendiamo in esame il colore più rappresentato (sappiamo che esiste perchè 9 è dispari)
assumiamo per buona la congettura che la suddivisione 5-4 sia la migliore.
i cinque punti Gialli (ho deciso che i gialli siano 5) possono essere raggruppati in uno-due-tre-quattro o cinque sottogruppi
uno: non va bene
due: uno dei due sottogruppi è lungo almeno tre: non va
cinque: sono equi-intervallati: non va
tre: se sono composti di 3-1-1 : non va
se sono composti 2-2-1 i quattro punti da colorare diversamente, e che devono riempire gli intervalli, non possono essere fatti da 3-1, ma nemmeno da 2-2
resta la divisione dei cinque gialli in quattro sottogruppi: l'unico modo è 2-1-1-1
eccetera eccetera

[Bruno]

...

Devo rileggermi meglio la soluzione di Enrico,
perché non l'ho capita ancora bene.
L'esplorazione di Gianfranco mi sembra molto
interessante, in effetti, ma dovrò stamparmi il
post per rileggerlo attentamente.
A Gianfranco farà piacere, spero, se ritorno su
una parte della sua prima proposta, quella
cosiddetta "banale" (in realtà, faccio sempre
molta fatica a ritenere qualcosa banale, e
infatti poi non ci riesco...)
Propongo queste precisazioni.
La configurazione GVVGGVVG è equivalente a
quelle che si ottengono da essa ciclicamente,
come per esempio questa: VVGGVVGG.
Le considerazioni fatte su GVVGGVVG possono
pure essere ripetute su VVGGVVGG.
Si può poi dimostrare facilmente che qualunque
configurazione che comprenda il gruppo ...VGV...
(giusto per fare un esempio) porta sempre a
una terna di cifre in progressione aritmetica.

Solo questo.

Stampo e vi leggo


Bruno

[Gianfranco]

Salvo e medito anch'io.
Bruno, i miei due post precedenti contengono parti errate che ho messo in evidenza, perciò è inutile leggerli.

A prima vista concordo con un'idea di Enrico: questo problema può essere ricondotto al caso 4,5.

Speravo di trovare una soluzione semplice, basata sull'esame di pochi casi o del principio del pigeonhole, ma credo che sia necessaria un'analisi precisa di diverse famiglie di casi possibili.

Gianfranco

[Bruno]

Salvo e medito anch'io.
Bruno, i miei due post precedenti contengono parti errate che ho messo in evidenza, perciò è inutile leggerli (...)

Sì, mi sono appena accorto di altre parti
evidenziate. Ok, Gianfranco. Attendo che tu
completi.

D'altra parte, in quanto a ripensamenti, non sei
solo.
Nel tentativo di seguire il tuo primo approccio,
più sopra ho scritto che si poteva dimostrare
facilmente che la presenza del gruppo VGV
(o GVG, che è lo stesso) porti comunque a
una terna di cifre in progressione aritmetica.
E' vero. In realtà, però, ho dovuto considerare
diversi casi, infilandomi in una strada che di
eleganza ed efficacia non sembra avere nemmeno
l'ombra...

Oggi è stata una giornataccia e in questo momento
non ho tempo per riordinare (o scrivere) le mie idee.

Vedremo nei prossimi giorni.


Bruno

[Bruno]

...

Ieri sera, nonostante venissi da una giornata dove
l'incudine e il martello eran furenti... ho buttato giù
una soluzione (spero, almeno, che risulti tale)
basandomi sul primo procedimento di Gianfranco.

La mia proposta è diversa dalla soluzione "ufficiale"
che conosco (ovviamente non mia) e meno spedita.
La tattica, tuttavia, è simile (anche perché vien quasi
naturale, dopo averci pensato un po' sopra, ragionare
in un certo modo). Credo comunque, salvo errori, che
il risultato sia interessante.

Non ho raffinato i vari passaggi e non escludo
che mi sia sfuggito qualcosa. Il tempo è questo,
purtroppo, e non ci posso far niente!

L'idea base è quella di vedere cosa succede se
2 e 4 hanno lo stesso colore oppure se il loro
colore è diverso. L'approccio avrebbe potuto
interessare indifferentemente, per ragioni di
simmetria, anche la coppia 6 e 8.

Tabella

Naturalmente, 2 e 4 (o 6 e 8) non sono le uniche
coppie di numeri da cui si può partire con questi
ragionamenti. Ho voluto considerare una delle
più impegnative (diciamo così), proprio per lasciare
a voi il gusto di trovarne una più semplice

- Se&o



Bruno

[giobimbo]

Come hanno tutti capito, in ogni bipartizione di 9 elementi c'è sempre un sottoinsieme di 5 elementi, che possiamo indicare come X = {A, B, C, D, E}, dove A8. Dimostriamo dunque l'esistenza di una progressione aritmetica in modo puramente combinatorio, esaminando tutte le possibili differenze rimanenti.

Se tutte le differenze sono uguali, o se lo sono tre di esse, sicuramente esiste una progressione aritmetica. Se sono uguali a due a due avremo:
1) (a a b b)
2) (a b b a)
3) (b a a b)
4) (b b a a)
5) (a b a b)
6) (b a b a)
Nei primi quattro casi abbiamo sempre una coppia di differenze uguali consecutive per cui esiste una progressione aritmetica. Negli ultimi due casi abbiamo C-A=E-C=a+b per cui gli elementi ACE formano una progressione aritmetica.

Rimangono da controllare i casi in cui solo due differenze sono uguali. Inoltre, data l'intercambiabilità delle lettere a, b e c, e trascurando le quadruple speculari per cui vale lo stesso ragionamento, per esser brevi, le davvero diverse possibilità da esaminare sarebbero:
1) (a a b c)
2) (a b a c)
3) (a b c a)
4) (b a a c)
da cui escludiamo con facilità la prima e l'ultima perché ricadono nelle condizioni già viste.

Prima di analizzare 2) e 3) notiamo che il valore della differenza a può essere solo 1 o 2, perché se a=3 la somma delle differenze come minimo vale (3+3+1+2)=9>8. Allora:

(a b a c)
Se a=1 b=2 c=3 allora BD=1+2 = DE=3 e BDE è una progressione aritmetica
Se a=1 b=3 c=2 allora BC=3 = CE=1+2 e BCE è una progressione aritmetica
Se a=2 b=1 c=3 allora BD=2+1 = DE=3 e BDE è una progressione aritmetica
Se a=2 b=3 c=1 allora BC=3 = CE=2+1 e BCE è una progressione aritmetica

(a b c a)
Se a=1 b=2 c=3 allora AC=1+2 = CD=3 e ACD è una progressione aritmetica
Se a=1 b=3 c=2 allora BC=3 = CE=2+1 e BCE è una progressione aritmetica
Se a=2 b=1 c=3 allora AC=2+1 = CD=3 e ACD è una progressione aritmetica
Se a=2 b=3 c=1 allora BC=3 = CE=1+2 e BCE è una progressione aritmetica

[giobimbo]

Stanotte, ripensando a quanto avevo scritto mi sono accorto che si può anche avere b=4 (oppure c=4), nel qual caso obbligatoriamente a=1, A=1 ed E=9; se C-B=4 (oppure se D-C=4) allora X non contiene tre termini in progressione aritmetica, p.es:
X={1, 2, 6, 7, 9} e differenze (1 4 1 2)
Se però C-B=4 allora l'insieme Y, complementare di X, contiene i termini B+1, B+2 e B+3 che formano una progressione aritmetica di ragione 1. Lo stesso, se D-C=4 allora l'insieme Y contiene i termini C+1, C+2 e C+3.

Questo salva la dimostrazione ma rende invalido il presupposto che bastasse dimostrare la partizione 4+5, bisogna dimostrare anche 3+6 e 2+7 e 1+8, ma ora devo andare a dormire.

[delfo52]

comunque un colore deve essere presente almeno 5 volte.
concentriamo su di questo.
i cinque potrebbero essere tutti attaccati ( 5-0), oppure divisi in due gruppi (4-1 o 3-2) e questi possiamo eliminarli subito.
Oppure potrebbero essere divisi in cinque singoli (1-1-1-1-1) e anche questo caso è banale.
Restano da considerare i casi in cui abbiamo tre gruppetti (2-2-1 o 3-1-1) o quattro (2-1-1-1), anzi la 3-1-1-1 possiamo eliminarla.
rimangono la 2-2-1 in tutte le sue combinazioni (2-2-1 ; 1-2-2 ; 2-1-2)
e la 2-1-1-1 (2-1-1-1 ; 1-2-1-1; 1-1-2-1 e 1-1-1-2)per simmetria possiamo limitarci a esaminare i casi in neretto
prendiamo la 2-1-1-1 : osservo che se i quattro intervalli fossero unitari, come sarebbe se il primo o l'ultimo termine fossero del colore complementare, il caso sarebbe escluso; quindi i quttro complementari devono riempire i tre intervalli, divisi in due gruppetti da uno e uno da due; se il gruppetto da due lo mettiamo nel primo o nel terzo intervallo, restano due intervalli da uno in fila; se mettiamo il gruppetto da due nell'intervallo di mezzo, abbiamo 1,2,4,7,9 che non va bene
resta da fare analoga analisi per gli altri tre casi

[Bruno]

...

Comincio a capire molto bene il pensiero di
Enrico! C'è qualche punto che devo approfondire,
ma ora lo seguo.

Appena mi libero leggo la versione di Giobimbo,
che intanto saluto


Bruno

[giobimbo]

Dovendo controllare tutte le partizioni la cosa si allunga, se pur di poco, perdendo in eleganza.
Partizione 6 + 3, X = {A, B, C, D, E, F} con A<B<C<D<E<F; le differenze da d1 a d4 sono come prima e d5=F-E.
Se ci sono cinque o quattro differenze uguali è impossibile evitare che due di esse siano consecutive, quindi esiste una progressione aritmetica. Se solo tre sono uguali abbiamo due casi possibili:
1) (a b a b a)
2) (a b a c a)

Nel primo caso abbiamo due progressioni aritmetiche, ACE e BDF, entrambe di ragione a+b.

Nel secondo caso ci sono due possibilità.
(1 2 1 3 1) con BDE progressione aritmetica di ragione 3,
(1 3 1 2 1) con BCE progressione aritmetica di ragione 3.

Partizione 7+2, le differenze associate all'insieme X sono 6, di cui possono essercene 4, 5, oppure 6 uguali, di valore 1: impossibile evitare di averne due di seguito.

Partizione 8+1, le differenze associate all'insieme X sono 7, di cui possono essercene 6 o 7 uguali, di valore 1: di nuovo, impossibile evitare di averne due di seguito.


@Delfo52:

comunque un colore deve essere presente almeno 5 volte

ma non si può dimostrare che ciò basti, difatti se coloriamo con lo stesso colore gli elementi 1, 2, 6, 7 e 9, tre qualsiasi di questi elementi non formano mai una progressione aritmetica.

[Bruno]

@Delfo52:

comunque un colore deve essere presente almeno 5 volte

ma non si può dimostrare che ciò basti, difatti se coloriamo con lo stesso colore gli elementi 1, 2, 6, 7 e 9, tre qualsiasi di questi elementi non formano mai una progressione aritmetica.

Sì, è giusto, Giobimbo, però non credo che
Enrico pensasse che questo basti.
E' chiaro che bisogna poi passare all'esame
delle varie possibilità significative, che è poi
quello che sta cercando di fare.
D'altra parte, se 1, 2, 3, 7 e 9 hanno lo stesso
colore, fra i numeri rimanenti c'è senz'altro
una terna in progressione aritmetica.
Anche questo potrebbe essere un aspetto da
considerare.
Forse sbaglio?
Mah... ho scritto di getto: ci penso meglio.


Bruno