La sequenza di colori BRRBBRRB (dove B è blu e R è rosso) non ha una sotto-sequenza a spaziatura uniforme di lunghezza 3 che sono dello stesso colore. Tuttavia, se aggiungi una B alla fine, ottieni BRRBBRRBB, che ha lo stesso colore B nelle posizioni 1,5 e 9 che sono equamente distanziate di 4. Se aggiungi una R alla fine, ottieni BRRBBRRBR, che ha R in posizione 3, 6 e 9. In effetti, con solo due colori, non esiste una sequenza di lunghezza 9 di B e R che non abbia una sotto-sequenza di 3 equidistanti dello stesso colore.
Il Teorema di Van der Waerden afferma che per qualsiasi numero di colori r e lunghezza k, una sequenza sufficientemente lunga ha sempre una sotto-sequenza equidistante dello stesso colore. La lunghezza minima garantita per avere una sotto-sequenza equidistante è chiamata numero di Van Der Waerden ed è scritta W (k, r). Ad esempio, W (3,2) = 9. Questo progetto è trovare limiti inferiori migliori per i numeri di Van Der Waerden trovando sequenze come BRRBBRRB. Vedi una tabella dei risultati finora sotto.
Ecco come funziona il programma. Prendi un numero primo n (mostrato tra parentesi sulla tabella) e una radice primitiva di quel numero. Ad esempio, sia n uguale a 11: si vede che W (4,2) -lunghezza 4, 2 colori ha 11 tra parentesi. Si usi adesso la radice primitiva 2: 2 è una radice primitiva di 11 perché le sue potenze fino a 2 ^ 10 [2,4,8,16,32,64,128,256,512,1024] modulo 11 (il resto quando si divide per 11) sono tutte distinte e uguali [2,4,8,5,10,9,7,3,6,1] che coloriamo di rosso, blu, rosso, blu. Ora tutto quello che dobbiamo fare è riordinare questa sequenza, ottenendo [1,2,3,4,5,6,7,8,9,10]. Possiamo aggiungere il colore 11, che dovrebbe essere blu.
Rabung ha dimostrato che in determinate condizioni possiamo concatenare altre 3 copie di questa sequenza di 11 termini evitando 4 equidistanti dello stesso colore. Possiamo aggiungere un 34simo termine, quindi lo faremo. L'esistenza di questa sequenza di 34 dimostra che W (4,2) è maggiore di 34. È un problema aperto determinare i valori di W (r, k) per la maggior parte dei valori di r e k. La dimostrazione del teorema fornisce solo un limite superiore. Per il caso di r = 2 e k = 3, ad esempio, l'argomento fornito di seguito mostra che è sufficiente colorare gli interi {1, ..., 325} con due colori per garantire che ci sarà un'aritmetica progressione (monocolore) della lunghezza 3. Ma in realtà, il limite del 325 è molto “lento”; il numero minimo richiesto di interi è solo 9. Qualsiasi colorazione degli interi {1, ..., 9} avrà tre interi equidistanti di un colore.
Per r = 3 e k = 3, il limite dato dal teorema è 7(2·37 + 1)(2·37·(2·37 + 1) + 1), o approssimativamente 4.22·1014616. Ma in realtà, non sono necessari così tanti numeri interi per garantire una progressione monocolore di lunghezza 3; ne hai bisogno solo 27. (Ed è possibile colorare {1, ..., 26} con tre colori in modo che non vi sia alcuna progressione aritmetica monocolore di lunghezza 3; per esempio:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
|
R |
R |
G |
G |
R |
R |
G |
B |
G |
B |
B |
R |
B |
R |
R |
G |
R |
G |
G |
B |
R |
B |
B |
G |
B |
G |