Problemi su bilance con scala graduata

Una moneta vera pesa 10 grammi, mentre una moneta falsa pesa 9 g.
E' possibile, con una bilancia ad ago di precisione e una sola pesata, scoprire qual è il pacchetto delle monete false?

8. Monete di cioccolato avvelenate
Abbiamo 5 sacchetti di monete di cioccolato da 1,1 kg ciascuno.
Alcuni sacchetti sono pieni di monete avvelenate, altri invece contengono soltanto monete buone. Ma non sappiamo né quanti, né quali.
Sappiamo, però che le monete buone pesano 10 g ciascuna mentre quelle avvelenate pesano 11 grammi.
Inoltre abbiamo una bilancia digitale che ha una portata massima di 5 kg e indica i pesi in grammi.
Com'è possibile, con una sola pesata scoprire quali sono i sacchetti pieni di monete avvelenate e quelli pieni di monete buone?

7. Risparmiare soldi con la bilancia automatica
Tre ragazzi A, B, C vogliono pesarsi con una bilancia automatica spendendo solo una moneta.
Salgono tutti e tre sulla bilancia e inseriscono la moneta.
La bilancia segna un peso di 117 kg. Per un pelo! Infatti la portata massima della bilancia è 120 kg.
Scende A e l'ago scende a 79 kg.
Scende B e l'ago scende a 45 kg.
Quanto pesa ciascuno dei tre ragazzi?
Facile vero?

Hai alcuni sacchi di farina da 2 chili e mezzo; una bilancia a due piatti, e un peso da 100 grammi.

(Grazie a Enrico Delfini per aver inviato questo problema al Forum (Ennesimo quiz di pesate). Il problema è tratto dal blog di Maurizio Codogno)

5. 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?

4. La solita moneta falsa
Si hanno 6 monete di cui una è falsa. Quest'ultima si può conoscere 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ò conoscere 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)

2. 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?

1. Una pesa che parla alla fine!
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 ciò alla fine delle 4 pesate (in cui verranno rilasciati in ordine di corrispondenza i 4 valori delle 4 pesate effettuate).

Risposte & riflessioni

Ciascun sacchetto dà un aumento di peso che permette di individuarlo univocamente.

se pesano 13 g in più, stanno nei sacchetti 1, 3, 4 perché 13 può essere ottenuto in un solo modo, sommando numeri presi dalla sequenza 1, 2, 4, 8, 16, 32, e cioè: 1 + 4 + 8. Tali numeri corrispondono ai sacchetti 1, 3, 4.

1) Metto su un piatto un sacco intero da 2500 gr. + il peso da 100 gr. e sull'altro un sacco vuoto nel quale trasporto pian piano farina dal primo sacco, fino a raggiungere l'equilibrio dei due piatti, così che nel primo sacco restino 1200 gr. e nel secondo 1300 gr 2) Sposto il peso da 100 gr. nel secondo piatto, in modo che il peso totale sia 1400, e sostituisco il sacco da 1200 gr. con uno intero da 2500 gr. , dal quale tolgo tanta farina, finché i piatti non tornino in equilibrio, cioè finquando non avrò tolto 1100 gr. di farina dal sacco grande, man mano sistemata in un sacchetto a parte inizialmente vuoto..

1) metto il peso da 100 su un piatto e distribuisco il contenuto di un sacco sui due piatti in modo di pareggiarli.

2) tolgo dal sacco da 1200 farina fino a pareggiare il peso da 100 rimasto sui piatti

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

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

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

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

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.

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

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.

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:

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.

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):

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.

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

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

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é alla 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.

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)

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

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

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.

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:

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:

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:

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.

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

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:

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:

Io adopererei 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.

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.

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.

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ò in grado 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

A+B

r2+r3

B+C

pall. legg. n?

Bilance con scala graduata

Risposte & riflessioni