Giu 8

Un problema insoluto, ma molto divertente **

E' piuttosto strano che a un quiz con tanti asterischi si possa rispondere con due soli asterischi. Il motivo è, però, semplice: il quiz non ha ancora una soluzione!

Lo scopo del quiz era proprio quello di portare alla luce uno dei tanti problemi matematici che non hanno ancora avuto una risposta, nemmeno con l'ausilio dei super computer. Ci ricordiamo il volo del "bombo" e come questo simpatico insetto riesca a seguire perfettamente la minima traiettoria che collega un certo numero di fiori, toccandoli tutti e senza mai ripassare dallo stesso. I computer riescono a risolverlo con la forza bruta, il bombo con una dote naturale. Esistono, però, problemi che non hanno ancora trovato il modo di farsi aiutare dal computer, dato che la forza bruta sarebbe troppo bruta e non riuscirebbe a coprire tutte le possibilità. E' questo il caso dei numeri di Schur.

Vale la pena ricordare la vita di questo grande matematico ebreo, nato in Russia nel 1875 e trasferitosi in Germania dove divenne professore universitario nel 1919. Purtroppo la sua origine ebrea lo fece presto allontanare da ogni carica accademica e rimase sempre più solo ed emarginato dai colleghi e da molti allievi. Passò una vita estremamente infelice, ossessionato dall'idea del suicidio. Con l'inasprimento delle leggi razziali non poté nemmeno cercare rifugio all'estero in quanto non aveva la somma sufficiente per ottenere il permesso di essere "cacciato". Ci riuscì solo nel 1939 e si trasferì in Palestina dove però mori per un attacco di cuore nel 1941.

Malgrado la sofferenza fisica e morale e l'allontanamento quasi totale dall'ambito accademico, i suoi contributi alla matematica superiore sono stati molto rilevanti. Quello di cui ci vogliamo occupare è forse uno minore, ma di facile comprensione. Tutto parte dall'enunciato di un suo teorema. Vale la pena, però,  di fare una premessa esplicativa: si dice che un insieme è libero da somme, quando NON contiene al suo interno dei numeri x, y e z, tali che

x + y = z

In parole povere, non possono esserci numeri come 1 e 2 (o 4 e 5) insieme al numero 3 (o 9), dato che 1+ 2 = 3 (4 + 5 = 9). La versione più dura per un insieme libero da somme è quella in cui i tre numeri potrebbero anche essere non distinti. In poche parole, basta che all'interno del mio insieme io abbia, ad esempio, il numero 1 ed ecco che non posso inserirgli nemmeno il numero 2, dato che 1 + 1 = 2.

Esiste però anche la versione "debole", ossia quella in cui i numeri che si sommano per escludere l'ingresso di un nuovo compagno devono essere diversi tra loro. E, questa versione è quella che abbiamo trattato noi nel nostro "quiz".

In entrambe le versioni si vogliono costruire dei sottoinsiemi dei numeri naturali positivi (escluso lo 0) tali che  risultino "liberi da somme".

Si chiama numero di Schur forte il più alto tra quelli che possono essere inseriti all'interno di uno, due, tre, quattro, ecc. sottoinsiemi, considerando anche elementi NON distinti. Numero di Schur debole quello in cui gli elementi della somma siano anche distinti.

La rappresentazione del problema sembra proprio quella di un gioco.

Immaginiamo di avere un "club" molto esclusivo dove per potere entrare vigono regole molto ferree. I soci fondatori sono stati il numero 1 e il numero 2. Essi hanno ovviamente libera entrata. Però, la regola che è stata data blocca subito l'entrata di un terzo, dato che il 3 può essere ottenuto dalla somma di 1 + 2. Accidenti, veramente un club troppo esclusivo. Si decide allora di aprirne un altro, dello stesso livello sociale, che potrebbe ospitare il numero 3 che sarebbe un vero peccato escludere. E così aggiungiamo il secondo club, dove fa subito il suo ingresso il numero 3. Poi si presenta il 4. bene, lui ha una doppia possibilità... potrebbe entrare sia nel primo che nel secondo club. Cominciamo a scrivere per bene la situazione

Club A              Club  B

1, 2                        3

Proviamo ad accettare 4 nel primo club e si ottiene:

Club A               Club B

1, 2, 4                    3

Arriva il 5 , ma per lui sono chiuse le porte del club A (4 + 1 = 5). Può solo entrare in B

Club A               Club B

1, 2, 4                    3, 5

E' la volta del 6.

Anche per lui è vietato l'ingresso in A (4 + 2 = 6) e non può che entrare in B

Club A               Club B

1, 2, 4                 3, 5, 6

Toc...toc... è in arrivo il 7. Nessun problema per il club A

Club A               Club B

1, 2, 4, 7             3, 5 ,6

Tempi duri per il numero 8... Lui deve essere escluso da entrambi i club! Nel primo 7 + 1 = 8, nel secondo  5 + 3 = 8. Entrambi i club devono  vietare l'ingresso a nuovi membri. Il numero di Schur debole sembrerebbe essere il 7. Ma ne siamo sicuri? Ricordiamoci che il 7 poteva anche essere ammesso nel club B... Proviamo a inserirlo nel secondo club (sveltiamo la scrittura tanto ormai abbiamo capito come funzionano le cose...)

A                       B

1, 2 ,4         3, 5, 6, 7

Magnifico! Questa nuova sistemazione offre la possibilità di entrare nel club A anche al numero 8

1, 2, 4, 8     3, 5, 6, 7

Il numero di Schur è diventato 8 !

Si potrebbe fare di meglio? No. Potete pure provare quanto volete ma il numero 8 è il massimo per DUE club. Non solo, ma la sistemazione che abbiamo trovato è anche l'unica possibile!

Invece di descrivere tutto in bianco e nero, possiamo anche dare un gagliardetto colorato ai membri dei due club: il rosso e il blu, ad esempio. Nell'insieme dei numeri naturali (neri) si possono costruire due sottoinsieme colorati, uno rosso e l'altro blu, tali che siano liberi da somme! L'uso dei colori ci riporta in qualche modo ai teoremi di Ramsey che ha illustrato con tutti i particolari il nostro Umberto.

Potremmo, così, colorare i nostri numeri e dare la sequenza degli ingressi ai due club

1 2 3 4 5 6 7 8 9 10 11 12 13 ....

Dal 9 in poi fuori dai due club esclusivi!!

Le cose cambierebbero di molto se aprissimo un terzo club. Chiaramente il numero di membri ammessi crescerebbe... ma crescerebbe anche il numero delle possibili combinazioni.

Non voglio rovinarvi il piacere di "giocare" da soli o in compagnia. Vi dico soltanto che il numero di Schur per TRE club diventa 23 e esistono, questa volta, tre possibili sistemazioni diverse...

Beh... con un po' di impegno e con tanta pazienza (ma penso anche divertimento) si può  cercare di trovare il numero di Schur per QUATTRO club. Tuttavia, state molto attenti perché la faccenda comincia ad essere difficile e laboriosa. Il numero massimo è 66, tuttavia -non ci crederete- ma le possibili combinazioni che portano a 66 sono ben 29 931! Un numero che sembra davvero incredibile e che fa capire come comincino ad entrare in difficoltà anche i computer con la loro forza bruta. Pensate che il 66 è stato dimostrato essere il numero di Schur per 4 sottoinsiemi solo nel 2004.

Prima di andare avanti enunciamo il teorema di Schur:

Se si suddividono i numeri naturali in un numero finito di sottoinsiemi, questi non possono essere tutti liberi da somme.

Vale però una importante modifica:

Se si suddividono gli interi da 1 a k in numero finito di sottoinsiemi, è possibile fare in modo che siano tutti liberi da somme.

Il secondo enunciato è quello che dimostra come sia possibile determinare il numero massimo di numeri naturali da inserire nei sottoinsiemi e quindi determinare il numero di Schur, sia forte che debole.

Il problema vero di tutto ciò è che non è ancora stato trovato un algoritmo matematico che permetta di ricavare questo numero per un numero di sottoinsiemi qualsiasi... E senza algoritmo già considerare solo CINQUE sottoinsiemi diventa impossibile anche per la forza bruta. Tutto quello che si è riusciti a fare, finora, è trovare il valore minimo per il numero di Schur sia per 5 che per 6 club. Ossia possiamo dire con certezza che il numero di Schur debole per 5 sottoinsiemi deve essere maggiore o uguale a 196. Mentre per 6 si ha una stima  ancora più incerta: il numero deve essere maggiore o uguale a 575.

In realtà c'è polemica attorno al numero relativo a 5 sottoinsiemi. Qualcuno dice di avere dimostrato anche che deve essere minore o uguale a 196, ossia aver dimostrato che il numero è proprio 196. Tuttavia, i metodi e i teoremi applicati per cercare di ottenere queste valutazioni sono ben al di fuori dei nostri scopi. Sul 196, per chi è particolarmente interessato, posso suggerire questo articolo (buona fortuna!).

Un problema matematico insoluto e siamo solo al numero CINQUE. Questa è, ovviamente, la ragione dei moltissimi asterischi... Tuttavia, ci si può divertire lo stesso cercando di ottenere il numero più alto possibile anche con SEI, SETTE o più ... club esclusivi, pur sapendo che non si riuscirà (ma chissà mai?) a ottenere il numero di Schur debole.  Tuttavia, il divertimento è assicurato già a partire da tre scatole.

In certe scuole americane fanno giocare i bambini della prima elementare con due scatole e i risultati sono veramente interessanti (ecco il motivo di un solo asterisco). Se poi volete fare partite più impegnative, sfidate pure i vostri amici con 4 o 5 scatole. Se poi qualcuno dovesse trovare l'algoritmo risolutore generale ancora meglio! Penso che sia ancora attivo il premio di parecchie migliaia di dollari che era stato messo in palio al risolutore del caso di 6 scatole... Tentar non nuoce.

Un bravo a Maurizio che è riuscito ad avvicinarsi di molto al valore  di 4 scatole (ma in via privata anche di 5) e a Fabrizio che con il suo 185 non è poi così lontano dalla meta!

Insomma buon divertimento con le scatole e i numeri di Schur.

 

 

 

 

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.