Teorema di van der Waerden

[MindFlyer]

Teorema di van der Waerden
Siano k e n interi positivi fissati. Allora esiste un intero N tale che, colorando con k colori gli interi da 1 a N, esiste al loro interno una progressione aritmetica monocromatica lunga n.

Dimostrare...

[MindFlyer]

Piccolo hint:
Dati k e n, definiamo W(k,n) il minimo N per cui vale il teorema. Provare la tesi per induzione su n, trovando un bound per W(k,n) rispetto a W(f(k,n),n-1), per un'opportuna funzione f.

[hydro]

colorando con k colori gli interi da 1 a N

ma colorando a piacimento? cioè, abbinando colori e numeri arbitrariamente?

perchè se è così (se ho ben capito l'enunciato del teorema), basta scegliere $ N=k*n $ e colorando gli interi da 1 a k con i k colori diversi, poi da k+1 a 2k ripetendo la sequenza e così via fino a $ k*n $ si ottengono k progressioni aritmetiche lunghe n monocromatiche di ragione k

[MindFlyer]

Per ogni possibile colorazione, non per una scelta opportunamente (e grazie al c...).

[enomis_costa88]

Visto che a quanto pare nei prossimi almeno 3 anni avrò molto molto tempo libero (colpa di fisica ovviamente) ..dedichiamoci a ciò che più mi piace.

Induzione su n.

Passo base: se n=1 cosa vogliamo dimostrare hem?!?!?

Supponiamo non esista w(n+1,c).
In w(n,c) ho una progressione aritmetica lunga n di numeri wlog rossi.
Considero la posizione (che chiamo A) in cui dovrebbe trovarsi l’n+1 esimo termine della progressione palesemente esso potrà essere di c-1 colori (altrimenti ho trovato la progressione).
Chiamo giallo il colore di A.
A è minore di 2w(n,c).
Considero ora ogni possibile colorazione della stringa 1,2w(n,c) come un colore.
Siano f(1,n,c) i nuovi colori.
Considero una stringa lunga 2w(n,f(1,n,c)) (2w(n,c)) come divisa in 2w(n,f(1,n,c)) gropponi (numeroni colorati) da (2w(n,c)). Avrò quindi n gropponi identici ed equidistanti.
In ogni groppone ho inoltre una progressione aritmetica di numeri rossi e un termine in posizione A (e A traslato per gli altri gropponi) di colore giallo.
Ho quindi n termini gialli che formano una progressione aritmetica.
Considero la posizione in cui dovrebbe trovarsi l’n+1 esimo termine della progressione gialla, la chiamo B.
Il termine in posizione B non potrà essere giallo ma neanche rosso (infatti se considero il primo termine della prima progressione rossa, il secondo della seconda ecc fino all’n esimo della n esima + il termine in posizione B formano una progressione aritmetica) e potrà essere quindi di c-2 colori.

Ora non ci vuole di sicuro un genio per capire che è sufficiente reiterare per perdere ogni volta un colore ed arrivare ad un assurdo.