Il teorema dimostrato da Bartel Leendert van der Waerden nel 1927 riguarda la presenza di progressioni aritmetiche contenute in insiemi di interi. Dati due interi r e k, può essere espresso in varie forme equivalenti:
- data una successione infinita e crescente di interi tali che la differenza tra termini successivi sia minore di r, la successione contiene una progressione aritmetica di lunghezza k;
- esiste un intero g(k, r), tale che una successione crescente di g(k, r) interi con differenza tra termini successivi non superiore a r contiene una progressione aritmetica di lunghezza k;
- se l’unione di r insiemi contiene tutti gli interi positivi, almeno uno degli insiemi contiene una progressione aritmetica di lunghezza k (congettura di Baudet);
- esiste un intero W(r, k), tale che se l’unione di r insiemi contiene tutti gli interi da 1 a W(r, k), almeno un insieme contiene una progressione aritmetica di lunghezza k
Nel caso dell’ultima formulazione il teorema dice che se suddividiamo gli interi da 1 a W(r, k) in r insiemi (non necessariamente disgiunti), almeno un insieme contiene una progressione aritmetica di lunghezza k. I numeri W(r, k) sono noti come “numeri di van der Waerden”. Sebbene Saharon Shelah abbia mostrato che sono computabili tramite una funzione primitiva ricorsiva, non si conosce una formula generale per calcolarli e i loro valori sono noti in pochissimi casi.
Per ulteriori informazioni visitate il thread ufficiale presente nel nostro forum.
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 |
Applicazioni e WU disponibili: vedi scheda "Link"
e allo "Stato del server" 
.
.
| Join al Team | |
| Applicazioni | |
| Stato del server | |
|
Statistiche interne del progetto |
 |
|
Classifica interna utenti |
 |
|
Pagina dei risultati |
 |
|
Statistica del Team sul progetto |
 |
| Classifica dei team italiani |  |
| Statistiche del Team |  |
| Classifica Utenti | |
| Classifica mondiale del Team |  |
