Università della LiberEtà
Giuseppina Trifiletti
Una donna aveva un cesto di uova.
Se le toglie a 2 a 2 ne resta 1.
Se le toglie a 3 a 3 ne restano 2.
Se le toglie a 4 a 4 ne restano 3.
Se le toglie a 5 a 5 ne restano 4.
Se le toglie a 6 a 6 ne restano 5.
Se le toglie a 7 a 7 non ne restano.
Quante uova aveva nel cesto?
usiamo il buon senso
Per la soluzione di questo problema basta un po’ di perspicacia:
il numero cercato non è multiplo di 2 (non è pari quindi)
(ne segue che non è multiplo né di 4, né di 6, come viene
infatti richiesto)
inoltre non è multiplo di 3 e non è multiplo neppure di 5,
però è multiplo di 7.
Basterà quindi elencare i multipli di 7 dispari, non divisibili né
per 3, né per 5.
Tra questi prima o poi deve trovarsi un numero che soddisfa le
condizioni, se queste sono compatibili tra loro
(se fosse scritto “se le toglie a 6 a 6 ne restano 3” questa
affermazione sarebbe incompatibile con l’affermazione “se le
toglie a 3 a 3 ne restano 2”, perché?)
Il numero di uova cercato non è multiplo di 2 quindi
non è pari, e ne segue anche che non è multiplo né di
4 né di 6. Perché?
Molto semplicemente
per essere multiplo di 4 o di 6 deve essere multiplo anche di 2,
dato che 6=3x2 e 4=2x2.
Meno semplicemente ma sfruttando un po’ di logica matematica
La proposizione
“Se N è divisibile per 4 allora è divisibile per 2”
È equivalente a
“Se N non è divisibile per 2 allora non è divisibile per 4”
Le proposizioni
“Se N è divisibile per 6 allora è divisibile per 2”
“Se N è divisibile per 6 allora è divisibile per 3”
Sono rispettivamente equivalenti a
“Se N non è divisibile per 2 allora non è divisibile per 6”
“Se N non è divisibile per 3 allora non è divisibile per 6”
Dato che è immediato riconoscere se un numero è
pari, per riconoscere la divisibilità per 3 basta fare la
somma delle cifre, e per riconoscere quella per 5 basta
osservare se il numero finisce per 5 o per 0,
per ricercare un numero soluzione del problema si può
procedere andando avanti di 7 in 7, scartando i
multipli pari, divisibili per 3 e per 5, e tra questi
cercare il primo che soddisfa a tutte le condizioni
(relative ai resti) del problema:
7
49
77
91
119
Eureka, trovata rapidamente una soluzione: 119!
119 soddisfa a tutte le condizioni del problema.
Ma sarà l’unica soluzione?
È 119 l’unica soluzione?
Ora che conosci una soluzione
sai trovarne altre?
Quante ce ne sono?
Anche 119 + 420 è soluzione
Anche 119 più uno qualunque dei
multipli di 420 è soluzione del
sistema.
perché?
Perché
420=3x4x5x7 ed è il mcm di 2,3,4,5,6,7
Per questo motivo il numero 119+420k soddisfa
tutte le condizioni del problema
(119 + 420k) mod (2) = 1
(119 + 420k) mod (3) = 2
(119 + 420k) mod (4) = 3
(119 + 420k) mod (5) = 4
(119 + 420k) mod (6) = 5
(119 + 420k) mod 7 = 0
NB: “a mod b” dà come risultato il resto della
divisione di a per b
un metodo alternativo
Un metodo alternativo
consiste nel risolvere il
sistema a)
a)
x
x
x
x

x

x
 1 mod 2 
 2 mod 3 
 3 mod 4 
 4 mod 5 
 5 mod 6 
 0 mod 7 
in questo caso la soluzione complica le
cose, in altre situazioni potrebbe aiutare
molto
un
metodo
maggiormente
formalizzato

x
x
x
a) 
x

x
x
significa “è equivalente a”
 1 mod 2 
 2 mod 3 
 3 mod 4 
 4 mod 5 
 5 mod 6 
 0 mod 7 

x  2mod 3
x  3mod 4
b) 
x  4mod 5

x  0mod 7
È lo stesso scrivere come segue, esplicitando le
equazioni che hanno coefficienti interi e
soluzioni intere.
x
x
x
x
x
x
 2 k 1
 3l  2
 4m  3
 5n  4
6 p 5
7q

x

x
x

x
 3l  2
 4m  3
 5n  4
7q
perché i due sistemi sono equivalenti?
I sistemi a) e b) sono equivalenti dato che le equazioni sotto a
destra sono superflue perché seguono dalle equazioni a
sinistra. Tutte le soluzioni delle equazioni a sinistra sono anche
soluzioni di quelle a destra, e dato che si devono trovare le
soluzioni comuni, bastano, sono sufficienti, le equazioni a
sinistra
x  3mod 4  x  1mod 2
x  5mod 6  x  1mod 2
x  5mod 6  x  2mod 3
Se x diviso per 4 dà resto 3 allora è dispari, quindi lo stesso x
diviso per 2 deve certamente dare resto 1,
così se x diviso per 6 dà resto 5, lo stesso x diviso per 3 darà
resto 2 e diviso per 2 darà resto 1.
se ci sono 35 uova e vado di 4 in 4, ne restano 3.
Se vado di 2 in 2 ne resta 1 (3mod2), solo perché 4 e divisibile per 2
Ci sono sempre 35 uova, se si va di 6 in 6 ne restano 5
e poi di 3 in 3 ne restano 2 (5 mod 3)
e se si va di due in due ne resta 1 (5mod2)
Ma solo perché i gruppi di 6 sono divisibili per 2 e per 3
Un giorno, durante una sagra di paese, un signore
ha assistito alla seguente scena.
Una specie di maga (diceva di essere una
sensitiva) raccontò di avere un rapporto del tutto
particolare con i numeri.
I numeri avevano la possibilità di metterla in
comunicazione con chi li possedeva e le
raccontavano con che tipo di persone aveva a che
fare.
“I numeri” – diceva – “hanno il potere di rivelare il
senso della realtà”.
Ordinò a uno del pubblico
a) di scegliere sei persone,
b) di ordinarle: I, II, III, IV, V, VI
c) di distribuire a cinque persone del pubblico 8
piccoli cartoncini rettangolari, che sostituivano le
monete, con scritto ad esempio 5 grammi (peso)
d)a uno dei sei, a scelta del pubblico, dovevano
essere consegnati cartoncini con un peso diverso,
un grammo in più o in meno di quello esatto.
La maga volle che il falsario, ma anche il peso,
venissero scelti da uno qualunque del pubblico, a sua
insaputa, in modo tale che non si pensasse a volgari
trucchi.
Il pubblico decise chi doveva essere il falsario, per
esempio Siro Alfa che si trovava al quarto posto, e a
Siro diede cartoncini con scritto 4, invece di 5.
Poi la sensitiva disse all'aiutante di prendere una
moneta dal primo, due dal secondo, etc,
1+2+3+4+5+6 = 21 monete in tutto. Le voleva per
avere un contatto diretto con l'anima di chi le
possedeva, disse.
L'aiutante eseguì.
Poi la sensitiva chiese all'aiutante il numero somma
di tutti i pesi.
L'aiutante simulò la bilancia sommando tutti i
numeri presenti nei foglietti.
La sensitiva disse che voleva pesare la cattiveria
presente nelle monete, cattiveria assorbita dal
personaggio che le possedeva, così disse al pubblico
la sensitiva.
L'aiutante diede come somma 101.
A questo punto la sensitiva strepitò dicendo che il
numero 101 gli avrebbe indicato con estrema
chiarezza il nome del falsario.
Ella si ritirò alcuni minuti per cogliere bene il
messaggio che il numero voleva trasmettergli.
Dopo un po’ si rivolse al pubblico, indicò con il
dito Siro, seduto al IV posto, imprecando contro
la sua slealtà che sarebbe stata punita dagli dei.
Una vera maga.
Come ha capito? Forse il numero palindromo 101
ha proprietà magiche? Forse perché 21 è un
numero triangolare?
Gropatia, così si chiamava,
era sì una maga, ma dei numeri.
Il suo nome mi ricordava qualcuno, ma chi?
La maga fece rapidamente i calcoli
101mod21=17
cioè 101=4*21+17
dato che il resto è 17 il falsario deve essere il quarto.
Se il resto fosse stato 20 il falsario sarebbe il primo (un solo
grammo in meno),
se fosse stato 19 il secondo (due grammi in meno),
se 18 il terzo, se 17 il quarto, se 16 il quinto, se 15 il sesto.
Se invece le monete false pesassero 1 grammo in più, allora i
resti potrebbero essere
resto 1 (una sola moneta falsa), il primo è il falsario,
resto 2 (due monete false) il secondo è il falsario,
resto 3 (tre monete false) il terzo è il falsario,
…
Se il resto fosse zero allora non ci sarebbe nessun falsario:
tutte le monete avrebbero lo stesso peso.
provate voi ora con 4 personaggi
quali sono le condizioni necessarie perché il gioco sia semplice e funzioni?
Non è certamente importante né 101, né 21
I
I personaggi devono essere proprio 6?
Assolutamente no
II
Bisogna togliere 1 moneta dal primo, 2 dal secondo, 3 dal terzo … ?
Così è più facile
III
Le monete buone devono avere un peso intero?
Sì, perché si utilizzano proprietà dei numeri interi
IV
La moneta falsa deve differire solo di 1g dalle monete buone?
Sì, se si vuole procedere come abbiamo detto
Un altro esempio
GROPATIA sa che i personaggi coinvolti sono 5.
Sa che viene prelevata 1 moneta dal I, 2 dal II, 3 dal III, 4
dal IV, 5 dal V.
Sa che il numero di monete da pesare è quindi 15.
Sa che i resti possono essere
I
II III IV V
1, 2, 3, 4, 5
Oppure
I
II
III
IV V
14, 13, 12, 11, 10
Il peso che le viene comunicato è 133.
133 diviso 15 dà 8 con il resto di 13
QUINDI IL FALSARIO è IL II
GROPATIA, se vuole trovare l’imbroglione, deve procedere
come segue. Tenere presente che ella non conosce il peso delle
monete.
• Memorizzare il numero di persone: n
• Fare il calcolo della somma dei primi n numeri naturali S:
S=n(n+1)/2
• Memorizzare il peso totale delle monete T
• Ricordare che i resti che può ottenere sono
a)1, 2, 3, 4, …, n
se le monete pesano 1g in più
b)S-1, S-2, S-3, …, S-n
se le pesano 1g di meno
• Fare la divisione tra T e S e tenere conto solamente del resto
Se il resto è 1 o S-1 allora il falsario è il I, se il resto è 2 o S-2
allora è il II, e così via
generalizziamo il problema
se i personaggi sono n,
S=1+2+3+4+5+6+7+…+n
S=n*(1+n)/2
Se le monete false pesano 1 grammo di più
T=S*p+x
1<x<n, S>n
T mod S = x
Il resto può variare da 1 ad n
Se le monete false pesano 1 grammo di meno
T=S*p-x (-x non può essere un resto)
T=S*(p-1)+S-x
T mod S = S-x
Il resto può variare da S-1 a S-n
NB. Se i personaggi sono n, anche il numero di monete che
ognuno possiede deve essere maggiore o uguale a n
la conta nel lager
In un campo di lavoro per prigionieri di guerra si trovavano
10 persone. I prigionieri dovevano essere eliminati. Il capo
delle guardie, sadico ma amante della matematica, decise
di salvare la vita di uno di loro. Per scegliere il fortunato
decise di fare una conta con 19 battute. Disse ad ogni
prigioniero di disporsi in cerchio, dichiarò che per contare
avrebbe incominciato da chi si trovava alla sua sinistra e che
avrebbe saltato naturalmente se stesso. Poi, prima di
iniziare la conta, chiese: ”Qualcuno di voi vuole per caso
cambiare posto?” Uno solo alzò la mano e si mise alla sua
destra.
Perché mai?
Anche qualche altro prigioniero aveva capito perché, ma non
volle competere per il posto della salvezza, preferì morire
insieme ai suoi amici.
Conta neraè questa qua.
Tuttin cerchio perla man.
Uno solnon peri rà
Quelche infine re ste rà
E se i prigionieri fossero stati ad esempio 24? Si
poteva reagire con altrettanta prontezza?
NO. Il conto da fare è diverso, perché 24>19
Perché funzioni la precedente strategia è necessario
che il numero di battute sia maggiore del numero
dei prigionieri.
Infatti se accade il contrario non è più vero che il
resto non sarà mai 0 e allora prima o poi uscirà
colui che precede il primo della conta, e quindi non
si salverà.
il problema di Giuseppe Flavio
nota storica
Sei schiavi vengono numerati da 1 a 6 e disposti in cerchio.
Stanno per essere uccisi tutti tranne l'ultimo, unico fortunato,
che sopravviverà.
Per decidere l'ordine in cui saranno uccisi si fa una conta
speciale: partendo dal numero 1 e contando i vivi in senso
orario, se ne uccide uno no e uno sì, cioè 2, 4, 6, ...
I cadaveri vengono immediatamente rimossi e non vengono
più contati.
Solo l'ultimo sopravvissuto sarà lasciato libero e si salverà.
Josephus, fortunato e intelligente, appena sa quale numero gli
è stato assegnato, tira un sospiro di sollievo. Infatti ha capito
che sarà salvo.
Che posto occupava?
Nel gioco (anche macabro) la conta è: no, si, no, si … viene
eliminato il sì, si inizia da 1 e si procede in senso orario.
Il numero che resta è sempre dispari.
Quando il numero è una potenza di 2 resta sempre il
numero 1, il primo della conta.
Infatti ad ogni giro il numero viene dimezzato, si chiude il cerchio
con un eliminato, e la conta ricomincia sempre da 1 e chiude
sempre il cerchio con un eliminato. Infatti il numero, diviso ad
ogni giro per 2, resta sempre una potenza di due fino ad arrivare
ad 1
Se il numero non è una potenza di 2 il cerchio non si chiude
sempre su l’ultimo eliminato.
L’ultimo resta indietro rispetto a 1 di un numero di posti pari
alla differenza tra la potenza di 2 successiva a N e il numero N.
N
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16
ultimo
1
3
1
3
5
7
1
3
5
7
9
11 13 15 1
Se ci sono 8 persone, 8-8=0, resta l’1
Se ci sono 7 persone, 8-7=1, resta 7
Se ci sono 6 persone, 8-6=2, resta il 5
8
1
7
7
2
6
3
6
5
2
1
4
3
5
4
6
5
1
2
4
3
Accade proprio che la formula corretta si ottiene considerando la
differenza D tra la prima potenza di 2 che supera il numero e il
numero N. il posto che precede 1 a distanza D è l’ultimo che
rimarrà.
Sia se il numero è una potenza di 2, sia se non lo è, bisogna
calcolare la distanza tra il numero e la potenza di 2 successiva a
N. Se chiamiamo P quella che precede N si ha
2P-N = D;
8-8 = 0;
8-7=1;
8-6=2;
Si va indietro di D, in senso antiorario, partendo da 1, senza
contarlo, cioè N-D+1, oppure, che è lo stesso, si va avanti di N(2P-N)+1 contando l’1.
Quindi
N – (2P-N) + 1 = 2N-2P+1
è il numero dell’ultimo che rimane.
UN METODO VERAMENTE ELEGANTE
Per trovare il numero si può fare così:
ruotare a sinistra la rappresentazione binaria di
N con rientro da destra della cifra (sempre uno)
che esce a sinistra.
Esempio: N = 107  in base 2  1101011  rotazione 
1010111  in base 10  87
Verifica: 2*( 107 - 64 ) + 1 = 2*43 + 1 = 87
INFATTI
Spostamento a sinistra: 2N
Tolgo la cifra più significativa: 2N - 2P = 2(N - P), dove P è la
più grande potenza di due che non supera N
Rientro da destra: 2(N - P) + 1
Nota storica
Il problema di Josephus può apparire un po' macabro ma ha una lunghissima
tradizione matematica ed alcune versioni sembrano essere ispirate da fatti
storici realmente accaduti come le decimazioni di guerra e la punizione dei
disertori.
Secondo alcuni studiosi le sue origini sono irlandesi e risalgono all'800.
Problemi simili a questo erano inoltre conosciuti nella cultura araba e in quella
giapponese già nel 1300.
Il famoso medico e matematico Gerolamo Cardano, nel 1539 fu il primo ad
identificare il sopravvissuto con l'ebreo Josephus Flavius (37-100), autore
del De bello Judaico.
Ecco la ricostruzione della vicenda attraverso alcune citazioni tratte da: Flavio
Giuseppe, La guerra giudaica, Libro III, A. Mondadori, 1982.
Siamo in Palestina, nell'anno 67 d. C. E' in pieno svolgimento la guerra tra i
Romani e i Giudei, che si concluderà con la distruzione di Gerusalemme.
I Romani andavano a caccia di Josephus, uno dei capi della rivolta. Egli,
grazie ad un aiuto divino, era saltato dentro ad una profonda cisterna
comunicante lateralmente con un'ampia grotta invisibile dall'alto. Ivi trovò
nascosti una quarantina di compatrioti.
Per due giorni rimasero nascosti ma al terzo furono traditi da una donna che
rivelò ai Romani il loro nascondiglio. Data la situazione, i compagni di
Josephus decisero di suicidarsi piuttosto che cadere in mano ai Romani.
Josephus tentò di distoglierli ma loro si inferocirono contro di lui e
minacciarono di ucciderlo per primo. "In un momento così drammatico non
venne meno a Josephus l'accortezza e, fidando nell'aiuto di Dio, mise in gioco
la vita dicendo: -Poiché abbiamo deciso di morire, lasciamo alla sorte di
regolare l'ordine in cui dobbiamo darci l'un l'altro la morte: ognuno sarà
ucciso da chi verrà sorteggiato dopo di lui, e così sarà la sorte a stabilire il
destino di tutti senza che nessuno debba perire di sua mano."
I suoi compagni accettarono la proposta e Josephus, "non si saprebbe dire se
per un caso o per volere di Dio, restò alla fine assieme ad un'altro e non
volendo né essere condannato dalla sorte né contaminarsi le mani con il
sangue di un connazionale se fosse rimasto ultimo, persuase anche il
compagno a fidarsi delle assicurazioni dei Romani e ad accettare di aver salva
la vita.“ Condotto a Roma dopo la guerra, Josephus fu dichiarato uomo libero,
gli fu concessa la cittadinanza romana, assegnata una pensione ed ebbe
ospitalità presso la dimora dell'imperatore Tito Flavio Vespasiano.
Che cosa si può desiderare di più? In un certo senso questa è una storia a
lieto fine ma per alcuni, Josephus fu soltanto un rinnegato.
il problema delle conte
nell’ informatica
􀂄 N oggetti sono disposti in cerchio
􀂄 Si elimina un oggetto ogni M e si richiude il cerchio
􀂄 Quale oggetto rimane per ultimo?
Con quale ordine si eliminano gli oggetti?
Non esiste una formula valida per tutti i casi.
Nelle diapositive successive si mostra come si può
risolvere il problema con l’informatica. Questo metodo,
però, non avrebbe aiutato Giuseppe Flavio e neanche i
prigionieri di guerra dell’esempio precedente.
Implementazione
􀂄 Lista circolare
􀂄 ogni oggetto connesso a quello immediatamente a SX
􀂄 i = i-esimo oggetto
􀂄 creazione della lista di N oggetti per inserzione
􀂄 partendo da 1, contare M-1 oggetti
􀂄 connettere l’M-1-esimo oggetto con l’M+1-esimo, saltando l’M-esimo
􀂄 terminazione: 1 solo oggetto rimanente.
In informatica, una lista concatenata è una delle
strutture
dati
fondamentali
usate
nella
programmazione.
Essa consiste di una sequenza di nodi, ognuno
contenente campi di dati arbitrari e riferimenti che
puntano al nodo successivo e/o precedente.
Le liste concatenate permettono l'inserzione e la
rimozione di nodi in ogni punto della lista in tempo
costante.
Esistono diversi tipi di liste concatenate: liste
concatenate semplici, liste concatenate doppie e liste
circolari.
Spunti tratti da
ENIGMI E GIOCHI MATEMATICI di Martin Gardner,
Biblioteca Universale Rizzoli
PROGETTI realizzati in collaborazione con Università di
Udine e Liceo Copernico negli anni 2000-2007
Personali riflessioni e rielaborazioni