Valutazione attuale: 3 / 5

Stella attivaStella attivaStella attivaStella inattivaStella inattiva
 
Van Der Waerden Numbers

 

AMBITO: Matematica
STATO: ATTIVO

 

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.


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 


Van Der Waerden Numbers




Stato del progetto: progetto attivo

 

Applicazioni e WU disponibili: vedi scheda "Link"

Cliccare sulle icone relative alle "Applicazioni" ico32_applicazioni e allo "Stato del server" ico32_server.

 

Sistemi operativi supportati: vedi scheda "Info tecniche"

 

Dati specifici sull'elaborazione: vedi scheda "Info tecniche"
Per ottenere dati sulla durata media dell'elaborazione, la RAM necessaria e la dead line, consultare la scheda "Info tecniche" qui a destra. Per informazioni particolareggiate (specifiche per applicazione e sistema operativo, intervallo di backup e crediti assegnati) rifarsi alla pagina dei risultati del progetto WUprop@home.

 

Problemi comuni: nessuno
Non si riscontrano problemi significativi.
 
Supporto al progetto: supportato
Per unirsi al team BOINC.Italy consultare la scheda "Link" qui sotto cliccando sull'icona relativa al "JOIN" ico32_bi.

Van Der Waerden Numbers

 

 

Link utili
Join al Team ico32_bi
Applicazioni ico32_applicazioni
Stato del server ico32_server

Statistiche interne

del progetto

ico32_stats

Classifica interna utenti

ico32_classutenti

Pagina dei

risultati

Pagina dei risultati
 
 
 
 
Statistiche BOINC.Stats

Statistica del Team sul

progetto

ico32_boincstats
Classifica dei team italiani ico32_statita
Statistiche del Team Team Stats
Classifica Utenti ico32_classutenti
Classifica mondiale del Team ico32_stats
 

 

Posizione del team nelle classifiche modiali:
Posizione del Team nelle classifiche mondiali

 



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...