Matematica e informatica nel problema delle noci di cocco. Martin Gardner lo espone così in Enigmi e giochi matematici, 2:
Cinque marinai ed una scimmia fecero naufragio su un’isola deserta e passarono il primo giorno a raccogliere noci di cocco per cibo. Poi le ammucchiarono tutte insieme e andarono a dormire. Mentre tutti dormivano uno di essi si svegliò e pensando che il mattino dopo vi sarebbero stati dei litigi alla spartizione, decise di prendersi la sua parte. Perciò divise le noci in cinque mucchi. Rimaneva una noce, che egli dette alla scimmia, poi nascose la sua parte e mise tutto il resto assieme. Subito dopo un secondo uomo si svegliò e fece la stessa cosa. Anch’egli dette una noce residua alla scimmia. Uno dopo l’altro tutti e cinque gli uomini fecero la stessa cosa, ognuno prendendo un quinto del mucchio che trovava svegliandosi e dando una noce alla scimmia.Alla mattina essi divisero le noci rimaste ed ognuno ottenne lo stesso numero. Naturalmente ognuno sapeva che mancavano delle noci, ma ognuno era colpevole come gli altri e così nessuno parlò. Quante noci c’erano all’inizio?”
Martin Gardner, di cui il 22 maggio scorso è ricorso il decennale della morte, il problema delle noci di cocco lo riprese dal The Saturday Evening Post dell’ottobre 1926.
Il poblema era incluso in un racconto di Ben Ames Williams, che però aveva dimenticato di pubblicarne la soluzione. Per questo motivo al giornale arrivarono circa 2000 lettere di lettori che chiedevano la soluzione.
Per circa 20 anni WIlliams continuò a ricevere lettere con la richiesta della soluzione o con proposte di soluzione.
Insomma è stato un problema che ha appassionato molte persone nel tempo.
In realtà l’origine del problema – e di altri dello stesso tipo – risale a molti anni prima che Williams lo pubblicasse sulla rivista statunitense. Problemi con i resti delle divisioni sono stati affrontati sin dall’antichità da Diofanto di Alessandria che per primo studiò le divisioni per i numeri interi nel III secolo dopo Cristo. Anche Sun-tzu, matematico cinese, se ne occupò in una sua opera riportando un risultato noto come Teorema cinese del resto.
Una soluzione al problema viene fornita anche da Euclide negli Elementi con il famoso algoritmo euclideo che permette di risolvere equazioni razionali che richiedono soluzioni intere.
Il problema delle noci di cocco si può dunque annoverare tra i rompicapi diofantini e tra questi è uno di quelli più studiati. Diofanto è generalmente noto come il padre dell’algebra, tra i primi a studiare in profondità le equazioni razionali. [Si vedano nel sito Antonino Giambò e Silvio Maracchia]
La prima descrizione del problema che si avvicina a quella proposta da Williams è comunque apparsa nei diari di Lewis Carrol pseudonimo di Charles Dodgson e autore del famosissimo Alice nel paese delle meraviglie [si veda: The_monkey_and_the_coconuts]
Da allora, il problema è stato riproposto in varie versioni.
Lo stesso Williams che evidentemente non ne è il creatore , è partito da una formulazione antecedente in cui nell’ultima suddivisione rimaneva ancora una noce di cocco per la scimmia. Nella versione di Williams l’ultima divisione è invece esatta.
Entrambi i problemi hanno infinite soluzioni.
La soluzione che ci interessa è il numero minimo di noci che soddisfa il problema. Nel libro di Gardner è riportata solo la soluzione al problema più antico.
Considerando le sei successive suddivisioni, la versione più vecchia del problema può essere espressa dalle seguenti equazioni:
N = 5A + 1
4A = 5B + 1
4B = 5C + 1
4C = 5D + 1
4D = 5E + 1
4E = 5F + 1
“Dove N è il numero originale; F il numero ricevuto da ogni marinaio nella divisione finale. Gli 1 a destra sono le noci date alla scimmia. Ogni lettera rappresenta un intero positivo incognito. Non è difficile ridurre queste equazioni, mediante noti metodi algebrici, alla seguente unica equazione diofantina con due incognite: 1024 N = 15625 F + 11529”.
Gardner propone come soluzione quella di Paul A. M. Dirac che nella risoluzione usa il concetto di noci negative.
Un metodo risolutivo, visto che disponiamo di macchine con elevato potere di calcolo, è anche il metodo algoritmico. Non è molto complicato e potrebbe essere un simpatico esercizio per le scuole superiori.
Si costruisce un algoritmo che verifica se un numero intero soddisfa le condizioni poste e poi partendo da 1 e iterando sui numeri interi si trova il minimo intero che verifica le ipotesi. Così facendo si perviene alla soluzione richiesta.
In particolare l’algoritmo test compie sei iterazioni, nelle prime 5 verifica che il resto del numero N in input sia uguale a 1 e sottrae al totale il quoziente + 1 (la noce di cocco per la scimmia). Nella sesta iterazione verifica che la divisione per 5 non dia resto, N viene scartato se in una delle iterazioni non soddisfa le condizioni sul resto.
Di seguito il diagramma di flusso che rappresenta l’algoritmo:
Di seguito il codice Java che traduce l’algoritmo risolutivo:
public static void main(String args[]) {
int numeroMassimo = Integer.parseInt(args[0]);
for (int i = 1; i <= numeroMassimo; i++ ) {
if (testNumeroNociDiCocco(i)) {
}
}
}
public static boolean testNumeroNociDiCocco(int numeroNoci) {
int[] num = new int[5];
for (int i = 0; i < 5; i++) {
if (numeroNoci%5!=1) {
return false;
}
numeroNoci = numeroNoci – numeroNoci/5 -1;
num[i]=numeroNoci;
}
if (numeroNoci%5==0) {
for (int inter:num) {
}
return true;
}
return false;
}
Il codice estrae il minimo intero che è soluzione del problema delle noci di cocco.
Non è di difficile risoluzione quindi sarebbe un simpatico esercizio per studenti delle scuole superiori o gli appassionati che si vogliono cimentare con gli algoritmi.
COMMENTS