Valutazione attuale: 3 / 5

Stella attivaStella attivaStella attivaStella inattivaStella inattiva
 
Van Der Waerden Numbers




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 



Per commentare questo post nel forum devi effettuare il login

Articoli

Guida WSL

Updated
Written on 26/02/2021, 18:14 by boboviz
guida-wslGuida a Boinc su WSL   Su stimolo di un nostro volontario abbiamo provato a far funzionare il client boinc in una macchina virtuale linux (ci sono...

Ultime dal Blog

Written on 19/06/2017, 14:38 by boboviz
addio-lugano-bellaCari sodali scaccolatori,come alcuni di voi sanno, il sottoscritto, oltre ad essere appassionato di Boinc, è anche "appassionato" di HPC e, visto che il...