[HOME - BASE Cinque - Appunti di Matematica ricreativa]
Soluzione completa del famoso problema di Ben Ames
Williams
pubblicato in The Saturday Evening Post nel 1926
Ricordo che il problema è stato proposto a BASE Cinque da Alessandro89
Cinque marinai naufragano su un'isola semideserta (semi-,
perché c'è una scimmia).
Durante la giornata raccolgono un mucchio di noci di cocco, per dividersele
tra di loro il giorno dopo.
Durante la notte, però, uno si sveglia e decide di prendersi la sua parte in
anticipo: fa cinque mucchi uguali, vede che avanza una noce, la dà alla
scimmia e nasconde la sua parte.
Il secondo marinaio si sveglia poco dopo, va al mucchio (più piccolo) e fa
esattamente la stessa cosa: anche stavolta rimane una noce per la scimmia.
Lo stesso fanno a turno gli altri tre: tutte le volte avanza una noce per la
scimmia.
Il mattino dopo, tutti vedono che il mucchio è più piccolo, ma avendo la
coscienza sporca stanno zitti. Fanno la divisione, e di nuovo avanza una noce
data alla scimmia.
Qual è il numero minimo di noci che i marinai avevano raccolto?
Nota storica.
Questo problema è stato pubblicato (per la prima volta?) da Ben Ames Williams
in The Saturday Evening Post nel 1926 e più
recentemente ripreso da Martin Gardner nel libro Enigmi e giochi matematici
2°.
Riccardo
Innazitutto sono partito dal presupposto che il numero iniziale debba
avere obbligatoriamente 6 oppure 1 come cifra delle unità.
Infatti il Numero stesso, diminuito di 1 (noce di cocco per la scimmia),
dev'essere divisibile per 5.
Non riuscendo ad impostare formule particolari che conducano ad un risultato
accettabile, ho proseguito per tentativi.
Ho notato che con un numero che ha come terna più a destra (centinaia, decine
e unità) 246 si andava oltre le tre possibilità di suddivisioni consecutive
(mentre con gli altri numeri testati si arrivava massimo a tre suddivisioni
consecutive).
Così facendo ho trovato 31246 che dà la possibilità di giungere fino alla
sesta ed ultima spartizione, con la noce di cocco per la scimmia in tutte le
suddivisioni.
Non so però se c'è un numero inferiore che dà le stesse possibilità, perchè
mi sono fissato a seguire la traccia del 246.
Ringrazio Ivana e Dino per la dettagliata
risposta alla domanda di Riccardo.
In sintesi: il numero più basso è 15621.
Dino e Ivana Niccolai
Indicando con n il numero di noci di cocco complessivamente raccolte dai
cinque marinai durante il giorno, nella prima spartizione ogni gruppetto sarà
formato da:
a = (n - 1)/5
noci di cocco. Quando si sveglia il secondo marinaio non troverà più n noci di cocco, bensì un numero più piccolo: 4·a. Egli effettuerà una nuova suddivisione in altri cinque gruppetti ognuno composto stavolta da:
b = (4·a - 1)/5
noci di cocco. Sostituendo il valore di a precedentemente trovato si ottiene:
b = (4·n - 9)/25
Ripetendo lo stesso ragionamento per il terzo marinaio si ha:
c = (4·b - 1)/5 = (16·n - 61)/125
per il quarto:
d = (4·c - 1)/5 = (64·n - 369)/625
e per il quinto:
e = (4·d - 1)/5 = (256·n - 2101)/3125
Quando tutti si svegliano il giorno dopo effettuano un'ultima ripartizione per cui:
f = (4·e - 1)/5 = (1024·n - 11529)/15625
Questa equazione prende il nome di equazione diofantea perchè deve essere soddisfatta da valori di f ed n interi: Infatti il numero minimo di noci raccolte dai marinai non si ottiene impostando f = 1, cioè con l'ultima spartizione di un solo cocco a testa in quanto si otterrebbe un valore di n non intero! Occorre cercare allora quel valore minimo di f tale che anche n sia intero. La soluzione di questa equazione può essere trovata per tentativi, ma il procedimento é molto lungo. Facendo un ragionamento a ritroso però da f possiamo scrivere:
e = 5·f + 1
quindi:
d = e + 1 + e/4
Questo significa che e oltre ad essere intero deve essere anche multiplo di quattro, e per la precedente anche f, a meno di uno, deve essere multiplo di quattro. Continuando a ritroso si ha:
c = d + 1 + d/4
cioè anche d deve essere multiplo di quattro, ma ciò comporta che allora e deve essere multiplo di 16 ed f, sempre a meno di uno, anch'esso multiplo di 16. Per b, a, ed n possiamo ragionare analogamente:
b = c + 1 + c/4
a = b + 1 + b/4
n = a + 1 + a/4
In definitiva a è un multiplo di quattro, b multiplo di 16, c multiplo di 64, d multiplo di 256, e multiplo di 1024, ed f, sempre a meno di uno, ancora multiplo di 1024. Il primo valore di f valido è pertanto 1023.
Infatti, impostando tale valore nell'equazione diofantea si ottiene il valore più piccolo per n che risulta essere 15621.
Esiste anche una semplice ed elegante soluzione, che coinvolge il concetto di "noce negativa" per risolvere l'equazione diofantea. Osserviamo innanzitutto che, poichè il numero da trovare viene diviso sei volte per cinque, ogni risposta accettabile, se sommata a 56 = 15625, ci dà la risposta successiva di ordine superiore. E' ovvio che non esiste un numero n positivo piccolo che soddisfi all'equazione (basta fare qualche tentativo per accorgersene), ma é possibile che ve ne sia uno piccolo negativo: infatti se il marinaio si avvicina al mucchio composto da -4 noci ed in prima battuta aggiunge e sottrae una noce di cocco il risultato non cambia. In tal modo si otterranno -5 noci più una reale (positiva); regala quest'ultima alla scimmia ottenendo un mucchio formato ora da -5 noci. Lo divide per cinque e si prende -1 noce. Resta nuovamente il mucchio con -4 noci. Il secondo marinaio ripete lo stesso procedimento, una noce positiva tocca sempre alla scimmia, -1 noce a lui e ne restano ancora -4. Il procedimento si reitera per tutti i marinai, lasciando invariato il numero di noci dopo la divisione (sempre -4). In questo modo, infatti, i marinai non devono fare che sottrarre e aggiungere ogni volta una noce al mucchio originario per ottenere un'equa divisione dei beni (equa sì, ma svantaggiosa per tutti). Alla mattina dunque, lasciata una noce positiva alla scimmia, ogni marinaio si prende una noce negativa. Risultato: ciascun uomo ha -2 noci e la scimmia possiede 6 noci. Dunque n = -4 è una soluzione dell'equazione diofantea, ma ovviamente non è accettabile fisicamente. Basta però sommarvi 15625 per ricavare immediatamente la soluzione di ordine superiore: -4 + 15625 = 15621. Con questo risultato si può osservare che l'ultima divisione lascia ancora 1023 noci a ciascun marinaio. D'altra parte esiste anche un teorema che dice che se X e Y sono le soluzioni di un'equazione diofantea di forma A·x - B·y = C, allora un'altra soluzione è data da X + B e Y + A, cioè, in questo caso proprio da 15621 (= -4 + 15625) e 1023 (= -1 + 1024).
Per capire meglio il concetto di noce negativa Norman Anning del dipartimento di matematica dell'Università del Michigan nel 1912 ragionò nel seguente modo: quattro noci delle 56 vengono tinte di nero e messe da parte. Quando le rimanenti vengono divise per cinque ne rimane una che viene data alla scimmia. Dopo che il primo marinaio ha preso la sua parte e la scimmia ha avuto la sua noce, rimettiamo di nuovo le quattro noci nere con le altre in modo da averne un mucchio di 55 noci, evidentemente divisibile per cinque, però prima di fare la successiva divisione mettiamo di nuovo da parte le quattro noci nere in modo che dalla divisione rimanga una noce da dare alla scimmia. Questo procedimento di prendere in prestito le noci nere solo quanto basta per vedere che si può effettuare una divisione per cinque e poi metterle da parte viene ripetuto a ogni divisione. Dopo la sesta divisione, le noci nere rimangono da parte e non sono più di nessuno. Esse non hanno una parte essenziale nell'operazione, ma servono solo a rendere le cose più chiare nel procedere.
E' possibile effettuare la generalizzazione del problema delle noci di cocco: sia M il numero dei marinai, maggiore di due, detti X il numero totale di noci raccolte dai marinai ed Y il numero di noci distribuite a ciascuno alla fine risulta:
X = [K·M(M + 1)] - (M - 1) Y = [K·(M - 1)M] - 1
dove K è un numero intero positivo che, posto uguale a 1, fornisce i valori minimi cercati nel problema. Se il numero di noci di cocco date alla scimmia alla fine di ogni tornata è pari ad N, con N qualsiasi intero maggiore di uno, si ha invece:
X = [K·M(M + 1)] - N·(M - 1) Y = [K·(M - 1)M] - N
Sprmnt21
Volevo solo riscrivere in maniera leggermente diversa quello gli altri hanno
gia' scritto sul problema delle noci di rocco. Indico con n e con x1, x2,
..., x5 il numero di noci di cocco raccolte e quello che ognuno durante la
notte sottrae e con x6 il numero di noci di cocco che spetta ad ognuno dopo
la divione mattutina.
Si ha in successione che:
n = 5 x_1+1
4 x_1 = 5 x_2+1
4 x_2 = 5 x_3+1
4 x_3 = 5 x_4+1
4 x_4 = 5 x_5+1
4 x_5 = 5 x_6+1
Sommando 4 ad ambo i membri delle precedenti uguaglianze, si ottiene:
n + 4 = 5(x_1+1)
4(x_1+1) = 5(x_2+1)
4(x_2+1) = 5(x_3+1)
4(x_3+1) = 5(x_4+1)
4(x_4+1) = 5(x_5+1)
4(x_5+1) = 5(x_6+1)
da cui, "moltiplicando tutte le uguaglianze", si ricava che
(n+4)4^5 = 5^6(x_6+1).
dato che ne' il 5 ne' alcuna sua potenza compare come fattore di 4^5, si ha
che n+4 e' multiplo di 5^6. Il piu piccolo valore che risponde al problema e'
percio' n = 5^6-4.
Sprmnt21
Ancora sulle noci di cocco, per sottolineare che quello che e' essenziale
alla natura del problema, non e' il numero totale (5) di naufraghi o il
numero di questi che "prelevano" durante la notte, prima della spartizione
alla luce del sole, ma, in un certo senso, il fatto che ci sia una sola
scimmia nell'isola ;-).
Infatti siano n, k ed h il numero di noci di cocco raccolte il numero di
naufraghi e il numero di "nottambuli" rispettivamente. Indicate con x_1, x_2,
..., x_h quello che ognuno durante la notte sottrae e con x_{h+1} il numero
di noci di cocco che spetta ad ognuno dopo la divione mattutina.
Si ha in successione che:
n = k x_1+1
(k-1) x_1 = k x_2+1
(k-1) x_2 = k x_3+1
..
(k-1) x_h = 5 x_{h+1}+1
Sommando k-1 ad ambo i membri delle precedenti uguaglianze, e "moltiplicando
tutte le uguaglianze", si ricava che
(n+k-1)(k-1)^h = k^(h+1)(x_{h+1}+1).
essendo k e k-1 coprimi, si ha che n+k-1 e' multiplo di k^(h+1). Il piu
piccolo valore che risponde al problema e' percio' n' = k^(h+1)-k+1.
Sito Web realizzato da Gianfranco Bo