[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Bilance con scala graduata

1. Monete false e bilance graduate
L'eterno problema... Le monete buone pesano 10 g e quelle false pesano 9 g.
Mio zio ha 5 monete e sa che alcune sono false. Purtroppo non sa né quante né quali.
Mio zio ha anche una bilancia di precisione, di quelle che indicano il peso degli oggetti, quindi potrebbe individuare le monete false con 5 pesate. Ma, siccome si diletta di matematica, vuole scoprire il numero minimo di pesate necessarie per scoprire quali sono le monete false.
Chi può aiutarlo?

2. La solita moneta falsa
Si hanno 6 monete di cui una è falsa. Quest'ultima si può riconoscere perché ha un peso diverso da quelle vere.
Come la si può individuare e anche determinare se pesa di più o di meno, con 3 pesate su una bilancia a scala graduata?

3. Il problema delle 15 monete
Il problema è simile al precedente, solo che si hanno 15 monete di cui una è falsa. Quest'ultima si può riconoscere perché ha un peso diverso da quelle vere.
Come la si può individuare e anche determinare se pesa di più o di meno, con 4 pesate su una bilancia a scala graduata?
(Kobon Fujimura)

4. Le cartucce d'inchiostro difettose
Il sig. Parodi ha appena ricevuto 7 scatole di cartucce per la sua stampante a getto d'inchiostro. Ogni scatola contiene 100 cartucce: un vero capitale! Sta per firmare l'assegno (rigorosamente coperto) e consegnarlo al corriere, quando squilla il telefono.
"Pronto, chi parla?"
"Sono il doctor Muller, responsabile qualità della ditta Kran Roxxe."
"Dica."
"Le abbiamo spedito 7 scatole di cartucce, ma ci risulta che 3 di esse contengono tutte cartucce difettose. La preghiamo di restituircele il più presto possibile e gliele sostituiremo immediatamente."
"Come faccio a riconoscere le cartucce difettose?"
"E' molto semplice: le cartucce difettose pesano 90 g mentre quelle buone pesano 100 g."
"Le altre casse contengono tutte cartucce buone?"
"Certamente, senza alcun dubbio."
Come può il signor Parodi risolvere il problema utilizzando il minor numero di cartucce ed una sola pesata su una bilancia a scala graduata?

5. Una pesa che parla alla fine!
(quesito inviato da Cesare Saleri)
Siano date 16 palline (di egual diametro) di cui 15 hanno lo stesso peso e una ha peso minore.
Avendo a disposizione una pesa (fornisce il peso in grammi), scovare la pallina più leggera con 4 pesate
Si consideri che per sapere il valore di una pesata bisogna andare alla cassa e pagare; attenzione si ha la possibilità di pagare una sola volta, e cioè alla fine delle 4 pesate (in cui verranno rilasciati in ordine di corrispondenza i 4 valori delle 4 pesate effettuate).


Risposte & riflessioni

1. Monete false e bilance graduate
Soluzione inviata da Giovanni Macchia
Si riesce a determinare il numero di monete false con 4 pesate ed il procedimento è applicabile a monete false di peso Pf e monete vere di peso Pv con Pv diverso da Pf (Pv=10 g e Pf=9 g sono un caso particolare).

Prima una premessa. Sia Pn il peso di una qualsiasi combinazione di n monete (n <=5) . Sia f il numero di monete false e v il numero di monete vere. Si ha che il peso delle n monete è dato da

(1) Pn = Pv * v + (n-v) * Pf.

da cui si può dedurre facilmente il numero di monete vere, in quanto Pn, Pv, Pf ed n sono noti , mentre le monete false sono ovviamente n-v ( nel caso di Pv=10g e Pf =9g, si ha Pn = 10*v +(n-v)*9) . Inoltre, la (1) ci dice che ,dato il numero di monete vere all'interno di un insieme di n monete, si può determinare in maniera univoca il peso corrispondente. La dimostrazione è elementare: se così non fosse, allora esisterebbe un valore v' di monete vere diverso da v tale che

(2) Pn = Pv * v' + (n-v') * Pf. Uguagliando con la (1) si ha

Pv * v + (n-v) * Pf = Pv * v' + (n-v') * Pf

eguaglianza soddisfatta solo se v =v', che contraddice l'ipotesi. In altre parole, c'è una corrispondenza biunivoca tra monete vere e peso. Pertanto, possiamo considerare in maniera completamente equivalente un insieme di monete come combinazione di monete vere o false oppure come avente un determinato peso. Usiamo pertanto una logica a due valori per risolvere il problema.

Indichiamo con V le monete che pesano Pv con F le monete che pesano Pf. Un insieme di monete sarà determinato da una combinazione di V ed F: per esempio, un insieme formato da 3 monete da Pv e 2 da Pf sarà indicato con VVVFF .

Si riesce a determinare il numero di monete false con 4 pesate. Indichiamo con A, B, C, D ed E le 5 monete. Dapprima determiniamo il numero delle monete false. Poniamo tutte le 5 monete sul piatto e misuriamo il peso totale Ptot (1a pesata). Indicato con f il numero di monete false è valida la seguente equazione:

Pf * f + Pv * v = Ptot Poiché v= 5 - f si ha Pf * f + Pv * (5-f) = Ptot da cui con semplici passaggi si ha

(3) f = (5 * Pv - Ptot)/(Pv -Pf) (nel caso del problema f = 50- Ptot).

Dalla (3) si deduce che, nel caso in cui f = 0, non vi sono monete false e nel caso f = 5 le monete sono tutte false. Ed ora analizziamo caso per caso i rimanenti valori di f.

a) f = 1 (una sola moneta è falsa) Pesiamo A (2a pesata). Si ha che A = V oppure A =F. Nel secondo caso abbiamo determinato quale è l'unica moneta falsa. Concentriamoci su A=V

Pesiamo ABC (3a pesata). Si possono avere i seguenti casi

a1) ABC = VVV a2)ABC = VFV

Esaminiamoli: a1) ABC = VVV In questo caso, D o E è falsa. Pesiamo D (4a pesata) . Se D = V allora E = F , altrimenti D = F. In ogni caso abbiamo determinato la moneta falsa.

a2) ABC = VFV In questo caso una delle due monete aggiunte (B o C) è falsa. Pesiamo B (4a pesata). Se B = V allora C = F , altrimenti B = F. In ogni caso abbiamo determinato la moneta falsa.

b) f = 2 (due monete sono false)

Poniamo AB sulla bilancia e pesiamo (2a pesata). Si possono avere i seguenti casi

b1) AB = FF
b2) AB = VV
b3)AB = VF

Nel caso b1 abbiamo trovato le due monete false. Esaminiamo gli altri due casi.

b2) AB = VV

Pesiamo CD (3a pesata). Vi possono essere solo i seguenti casi (ricordiamo che le monete false sono 2 e pertanto un altro VV non si può avere)
b21) CD = FF
b22)CD = VF

Nel caso b21 abbiamo determinato le 2 monete false. Nel caso b22, E sarà sicuramente F, poiché le monete false sono 2 e ne abbiamo individuata almeno 1. Pertanto , pesiamo C (4a pesata). Se C = F, allora C=F ed E=F . Se C = V, allora D=F ed E = F. Pertanto abbiamo determinato le monete false.

b3) AB = VF

Pesiamo ACD (3a pesata) . Si possono avere i seguenti casi

b31) ACD = VVV b32) ACD = VVF b33) ACD = FFV

Nel caso b31, si ha che E sarà sicuramente F e, poiché A=V, dalla b3) si ha che B = F. (ricordiamo che le monete false sono 2). Analizziamo i due casi rimanenti:

b32) ACD = VVF

In questo caso si hanno queste due possibilità:
b321) (A = V ) e ((C o D ) = F) (e quindi B = F ed E = V) oppure
b322) A=F e quindi E = F, poiché B,C e D devono essere V.

b321 è caratterizzato da (AE=VV) e ((C o D ) = V) mentre b322) è caratterizzato da AEC =FFV. Pertanto, pesiamo AEC (4a pesata), Se AEC = VVF allora siamo nel caso b321 con C = F e B=F. Se AEC=VVV allora siamo nel caso b321 con B = F e D =F. Se AEC = FFV, siamo nel caso b322 con A=F e E =F. Pertanto abbiamo determinato le monete false.

b33) ACD = FFV

Poiché le monete F sono solo 2, Ce D non possono essere entrambe F , poiché ne abbiamo individuata 1 in A o B. Pertanto, A deve essere F. Pesiamo C. Se C = F allora A=F, C=F. SE C =V , allora A=F e D =F. Pertanto abbiamo determinato le monete false

c) f = 3 (tre monete sono false) Poniamo ABC sulla bilancia e pesiamo (2a pesata). Si possono avere i seguenti casi (poiché le monete sono 5 e 3 sono false, non si può avere il caso VVV):

c11) ABC = FFF
c12) ABC = VVF
c13) ABC = VFF

Nel caso c11, abbiamo individuato le monete false. Esaminiamo i casi rimanenti

c12) ABC = VVF

Poiché le monete false sono 3, allora le rimanenti monete D ed E sono entrambe F. Pesiamo A (3a pesata). Se A = F, allora abbiamo trovato la terza moneta falsa, altrimenti pesiamo B (4a pesata). Se B = F abbiamo trovato la 3a moneta falsa, mentre se B=V allora C =F per soddisfare la relazione ABC=VVF. In ogni caso abbiamo trovato le 3 monete false.

c13) ABC = VFF

Abbiamo che o D o E è F, ma non possono esserlo entrambi . Pesiamo ABD (3a pesata). Si possono avere i seguenti casi:

c131) ABD = FFF
c132) ABD = VFF
c133) ABD = VVF

Nel caso c131 abbiamo individuato le 3 monete false. Esaminiamo i rimanenti casi:

c132) ABD = VFF

In questo caso si può avere

c1321) D=V e (A = F e B = F) e quindi E =F e C =V oppure
c1322) D=F e (A =F o B =F) e quindi E=V e C= F

c1321 è caratterizzato da AE =FF mentre c1322 è caratterizzato da AE = FV se A = F oppure AE=VV se A =V. Pertanto pesiamo AE (4a pesata). Se AE =FF, allora siamo nel caso c1321 con A = F, E =F e B=F. Se AE = VF, siamo nel caso c1322 con A = F, C=F e D=F. Infine se AE = VV siamo nel caso c1322 con D=F, C=F e B=F. In ogni caso abbiamo trovato le 3 monete false

c133) ABD = VVF In questo caso D non può essere F, poiché dalla c13 almeno un'altra moneta in ABD dovrebbe essere F. Pertanto D =V ed E=F. Pertanto, AB=VF e quindi C=F. Pesiamo A (4a pesata). Se A =V allora B =F e allora B=F, C=F ed E=F. Se A=F, allora A=F, C=F ed E=F. In ogni caso abbiamo trovato le 3 monete false.

d) f = 4 (quattro monete sono false)

Poniamo ABCD sulla bilancia e pesiamo (2a pesata). Si possono avere i seguenti casi (poiché le monete false sono 4 , sono da escludere i casi con 2 o più monete vere)

d1) FFFF
d2) VFFF

Nel primo caso abbiamo determinato le 4 monete false. Concentriamoci sul secondo caso

d2) VFFF

In questo caso, poiché le monete false sono 4 e ne rimane solo una, E =F. Pesiamo AB (3a pesata). Si possono avere 2 casi: d21) AB =FF d22) AB =VF

Nel caso d21 si deduce che CD=FV. Basta pesare C (4a pesata). Se C =F, allora le monete false sono A, B, C, E. Se C=V, allora D = F e le monete false sono A,B, D, E.

Nel caso d22 si deduce che C e D sono entrambe F. Pesiamo A (4a pesata). Se A=F, allora le monete false sono A, C, D ed E. Se A=V , allora B=F e le monete false sono B,C,D ed E

In ogni caso ho determinato le 4 monete false.

2. La solita moneta falsa
Soluzione inviata da Ivan D'Avanzo
Chiamiamo le monete A, B, C, D, E, F.
Dividiamo le monete in tre gruppi da due.
peso A,B = X
peso C,D = Y
Possono succedere due cose,
1) X = Y

2) X diverso da Y

1) Vuol dire che le 4 monete che ho pesato sono buone, quindi peso la E. Se essa pesa X/2, vuol dire che la falsa è la F, altrimenti il contrario.


2) La falsa è tra le 4 che ho pesato, quindi la E e la F sono buone.
allora peso A,C,E. Potrò ottenere i seguenti risultati:

2a) A+C+E= 3/2X : Vuol dire che A,C,E e B sono buone e dato che anche la F è buona, la falsa è la D.
2b) A+C+E= 3/2Y : Vuol dire che A,C,E e D sono buone e dato che anche la F è buona, la falsa è la B.
2c)A+C+E= X/2+Y : Vuol dire che la falsa è tra queste tre, e che la A è buona. Ma dato che anche la E è buona allora la falsa è la C.
2d) A+C+E= Y/2+X : Vuol dire che la falsa è tra queste tre, e che la C è buona. Ma dato che anche la E è buona allora la falsa è la A.

La soluzione funziona, ma solo in un caso, non riesco a sapere se la moneta falsa pesa di più o di meno della buona. Il caso è quando X = Y, peso la E e casomai E è quella buona. So per certo che quella falsa è la F ma non so dirti se è più o meno pesante delle altre. Sinceramente penso che non sia possibile, ma studierò un altro metodo.

3. Il problema delle 15 monete
La seguente soluzione è di Dario Uri

Devo dire che questo e' un problema davvero complesso ed alla luce di cio' che abbiamo detto per il problema precedente (quello delle 6 monete o palline), ecco la soluzione.
Etichettiamo le palline con i numeri da 1 a 15, e chiamiamo le 4 pesate A,B,C,D. Procediamo con le prime due pesate nel seguente modo:

A = 8,9,10,11,12,13,14,15.
B = 4,5,6,7,12,13,14,15.
Non pesate = 1,2,3.

Supponiamo per il momento che i risultati delle prime due pesate siano uguali, (vedremo in seguito il caso "differenti").
La difettosa e' fra quelle NON pesate oppure pesate due volte.
Dobbiamo quindi indagare fra 1,2,3,12,13,14,15., e dovendo fare in modo che ogni pallina sospetta sia pesata in modo differente da ciascuna altra per essere individuata, possiamo procedere con:

C = 2,3,14,15
D = 1,3,13,15

Le palline sospette appaiono cosi' nelle varie pesate:

Pallina   Pesate
1           D
2           C
3           C,D
12          A,B
13          A,B,D
14          A,B,C
15          A,B,C,D

Questo risolve gia' il nostro problema ?
Purtroppo no! Facciamo un esempio. I risultati delle 4 pesate sono 81, 81, 40, 40.
Se le palline fossero tutte autentiche i risultati delle prime due pesate sarebbero il doppio delle ultime due.
Qui vediamo che c'e' un eccesso di 1 in A, B oppure un difetto di 0.5 in C, D.
Nel primo caso avremmo 10g. per le palline autentiche e 11g. per la num.12 che e' l'unica ad apparire nelle pesate A, B oppure 8.1g. per le autentiche e 7.6 grammi per la num.3, unica ad apparire nelle pesate C, D.
Come fare per evitare questo ostacolo ?
Il trucco sta nell'aggiungere una o due palline sicuramente autentiche in C o in D.
Noi decidiamo di aggiungere 2 palline in C, che diventa:

C = 2, 3, 14, 15, + 8, 9.

A questo punto possiamo fare una schemino che ci da' per ciascuna pallina sospetta la differenza ottenuta confrontando le pesate 4C - 6D e B - 2D che risulterebbero = 0 se le palline fossero tutte uguali.

Palline ->  1    2    3   12    13    14    15
4C-6D      -6    4   -2    0    -6     4    -2
B-2D       -2    0   -2    1    -1     1    -1

Cosi' la pallina puo' essere individuata.
Difatti se ad es. A=81, B=81, C=60, D=40, si avrebbe:

4C - 6D = 240 - 240 = 0
B-2D = 81 - 80 = 1

E' la pallina num 12 piu' pesante di 1g.
Un'altro es.

A=79.5, B=79.5, C=59.5, D=40.

Si ottiene:

4C - 6D = 238 - 240 = -2.
B - 2D = 79.5 - 80 = -0.5.

I due risultati stanno 4/1 percio' e' la pallina num.14 che si trova in A,B,C.
In D sono tutte autentiche e peseranno 40/4 = 10g. l'una, e la num 14 pesera' 9.5g.
Nel caso che le due prime pesate siano differenti, il sistema e' del tutto analogo, le sospette sono quelle pesate una volta sola, vale a dire 4,5,6,7,8,9,10,11.
Allora procedendo con:

C = 6, 7, 10, 11 + 3, 14.
D = 5, 7, 9, 11.

La distribuzione diventa:

Pallina   Pesate
4           B
5           B,D
6           B,C
7           B,C,D
8           A
9           A,D
10          A,C
11          A,C,D        

Possiamo anche notare che i risultati delle pesate 4C - 6D e B - 2D sono identici a quelli ottenuti nel caso precedente e la corrispondenza per le palline 1,2,3,12,13,14,15 e' rispettivamente 9,10,11,4,5,6,7 c'e' in piu' la pallina num.8 che e' presente solo nella pesata A.
Risulta:

4C - 6D = B - 2D = 0.

4. Le cartucce d'inchiostro difettose
Soluzione inviata da Andro
Io adoprerei 127 cartucce prese così dalle 7 scatole:
1 dalla prima,
2 dalla seconda,
4 dalla terza,
8 dalla quarta,
16 dalla quinta,
32 dalla sesta e
64 dalla settima.
Se le cartucce fossero tutte buone, il peso sarebbe di 12700 grammi. Il peso P sarà invece minore di 12700.
Chiamiamo x=(12700-P)/10
Il numero x è univocamente determinato dalla somma dei 3 numeri di cartucce prelevati dalle 3 scatole difettose.
Se ad esempio ottengo x=74, le scatole difettose sono la seconda (da cui ho prelevato 2 cartucce), la quarta (da cui ne ho prelevate 8) e la settima (da cui ne ho prelevate 64: 2+8+64=74). Per come si è costruito x, non c'è un'altra terna che può dare come somma 74.

Alessandro Venturi ci riesce con 63 cartucce
Il numero di scatoloni contenenti cartucce non buone e' noto a priori, quindi si puo' tranquillamente ignorarne uno e lasciare il procedimento inalterato. Si ha un massimo di 63 cartucce utilizzate. Se la scomposizione binaria del numero di cartucce non buone pesate ha un contributo di solo due potenza di 2 allora lo scatolone escluso conterra' sicuramente cartucce fallate.

Giorgio Tumelero è arrivato a 51 cartucce: è una sfida per tutti!
Ringrazio Andro per il suo lavoro - di cui questo scritto è solo un miglioramento - che mi ha fatto capire quanto è matematicamente interessante questo problema in senso generale:
trovare una base minima di fattori primi che permetta una scomposizione "additiva" unica, come i numeri primi nella scomposizione "moltiplicativa".
Iniziamo col notare che (1) non ci devono essere due fattori uguali e che (2) anche le somme di due fattori devono essere tutte diverse.
Infatti,
(1) se a = a' allora p = a + b + c = a' + b + c. Il peso p ha due scomposizioni;
(2) se c = a + b = a' + b' allora p = a + b + d = a' + b' + d. Il peso p ha due scomposizioni.
Come base prendiamo l'insieme B = {0, 1, 2, 4, 7, 13, 24}.
L'insieme contenente tutte le somme di due termini è:
SommaB2 = {0+1, 0+2, ..., 1+2, 1+4, ..., 2+4, ..., 13+24} = {1, 2, 4, 7, 13, 24, 3, 5, 8, 14, 25, 6, 9, 15, 26, 11, 17, 28, 20, 31, 37}. Tale insieme contiene elementi tutti diversi e quindi soddisfa la condizione (2).
L'insieme contenente tutte le somme di tre termini è:
SommaB3 = {0+1+2, 0+1+4, 0+1+7, ..., 0+2+4, 0+2+7, 0+2+13, ..., 1+2+4, 1+2+7, ..., 7+13+24} = {3, 5, 8, 14, 25, 6, 9, 15, 26, 11, 17, 28, 20, 31, 37, 7, 10, 16, 27, 12, 18, 29, 21, 32, 38, 13, 19, 30, 22, 33, 39, 24, 35, 41, 44}. Tale insieme contiene elementi tutti diversi e ogni elemento ammette un'unica scomposizione in fattori presi da B. La somma dei numeri in B dà 51.
Vediamo se essa è minima.
Siccome la somma gode della proprietà commutativa, da un insieme di 7 numeri si ricavano 35 distinte somme e, tenendo conto che la somma di tre fattori non dà mai 1 o 2, possiamo dire che se SommaB'3 contiene i numeri da 3 a 37 allora la base B' è minima. Dalla mia SommaB3 mancano i numeri 4, 23, 34, 36 e ci sono 38, 39, 41, 44, quindi, in teoria, si potrebbe eliminare qualcuno di questi quattro ultimi numeri inutili trovando una base con valore minore di 51.

5. Una pesa che parla alla fine!
Soluzione inviata da Enrico Delfini
Disponiamo le palline in un reticolo 4x4 e numeriamole in ordine (1-2-3-4 nella prima riga da sinistra a destra; 5-6-7-8 nella seconda riga sempre da sinistra a destra e così via).

  A B C D
r1
1

2

3

4
r2
5

6

7

8
r3
9

10

11

12
r4
13

14

15

16

Le palline risultano così ordinate in 4 righe (r1, r2, r3, r4) e 4 colonne (A, B, C, D)

I PESATA: mettiamo sulla bilancia le otto palline delle righe r1 e r2 (1-2-3-4-5-6-7-8): saremo con ciò in grado (quando avremo il risultato) di sapere se la biglia X è nelle due righe di sopra o in quelle di sotto. Per ora però non lo sappiamo e passiamo alla
II PESATA: mettiamo sulla bilancia le 8 biglie delle colonne A e B (1-2-5-6-9-10-13-14); incrociando i due risultati saremo in grado di individuare la quartina cui appartiene la biglia X.
III PESATA: mettiamo sulla bilancia le 8 biglie delle righe r2 e r3 (5-6-7-8-9-10-11-12), saremo con ciò ingrado di restringere il campo a una coppia di palline.
IV PESATA: pesando le 8 biglie delle due colonne B e C (2-3-6-7-10-11-14-15) potremo identificare la biglia X anomala.

Le 4 pesate potranno assumere solo 2 valori a seconda che contengano o no la pallina più leggera.
Chiamati i due valori P (pesante) e L (leggero), si hanno 16 combinazioni che permettono di individuare la pallina più leggera.

Pesata Risultati
r1+r2 L L L L L L L L P P P P P P P P
A+B L L L L P P P P L L L L P P P P
r2+r3 L L P P L L P P L L P P L L P P
B+C L P L P L P L P L P L P L P L P
pall. legg. n° 6 5 2 1 7 8 3 4 10 9 14 13 11 12 15 16

Sito Web realizzato da Gianfranco Bo