Problemi di pesate

PROBLEMI DI PESATE

Nel 1556 Tartaglia nel suo Trattato (1) indico' come, con la serie di pesi 1,2,4,8,16,32 fosse possibile pesare qualunque numero da 1 a 40 ed oltre, servendosi di una bilancia a doppio piatto, con l'ulteriore restrizione di poter porre i pesi da una sola parte.
Se possono essere posti su entrambi i piatti sono sufficienti i pesi 1,3,9,27. Questo problema e' internazionalmente noto come problema di Bachet, perche' appare nei suoi Problemes (2) che e' considerata la prima raccolta storica di problemi ricreativi e ripubblicata negli anni molte volte.
In realta' moltissimi dei problemi del Bachet sono tratti da un manoscritto di Luca Pacioli, il De Viribus Quantitatis (3) presente qui a Bologna nella biblioteca universitaria al num.250, poco conosciuto, ma va sicuramente considerato come l'antesignano di questo genere.

Diverse serie di pesi possono essere selezionati per poter pesare da 1 a 40 con le seguenti restrizioni:
a) Nessuna altra pesata potra' essere possibile.
b) Ciascuna pesata e' possibile in un solo modo.
La soluzione a questo problema richiede un'analisi complessa.
Il generale Mac Mahon in un articolo apparso nel Quaterly Journal (4), dimostra che esistono otto di tali serie.
Precisamente sono:
(1^40), (1, 3^13), (1^4, 9^4), (1, 3, 9^4), (1^13, 27), (1, 3^4, 27), (1^4, 9, 27), (1, 3, 9, 27).
dove ogni esponente indica quante volte quel peso rientra nella serie.
Da allora un gran numero di problemi riguardanti pesate sono stati proposti, ma nessuno e' piu' conosciuto del:
PROBLEMA DELLE 12 PALLINE, i frequentatori di it.hobby.enigmi lo sanno bene, non passa settimana senza che qualche neofita lo riproponga.
Cerchiamo di saperne qualcosa di piu'.
L'enunciato e' questo:
Si hanno 12 palline apparentemente tutte uguali, tuttavia e' presente una pallina difettosa, piu' leggera o piu' pesante delle altre.
Avendo a disposizione una bilancia a doppio piatto, individuarla e determinare se sia piu' pesante o piu' leggera delle altre.
Questo problema, dove originariamente c'erano monete al posto delle palline, apparve per la prima volta nel 1945 (5).
Vi sono 2 modi essenzialmente diversi di affrontare la questione.
Nel primo metodo, le palline da pesare sono scelte in base al risultato delle pesate precedenti, nel secondo, piu' sofisticato, la distribuzione delle palline sui piatti viene stabilita a priori.
Vediamoli.

PRIMO METODO Identifico le palline con le lettere dalla A alla N, la difettosa con la X.
Prima Pesata = ABCD EFGH

Primo caso, scende un piatto (senza perdere di generalita' diciamo quello di sinistra), sappiamo subito che X e' in ABCD piu' pesante oppure in EFGH piu' leggera.
Seconda Pesata = ABCE DLMN.
Sappiamo che LMN sono regolari, allora ecco i tre casi possibili:
1) Scende ABCE, X e' fra ABC ed e' piu' pesante, in questo caso la terza pesata sara' confrontare A con B, se c'e equilibrio la pallina cercata e' la C.
2) C'e' equilibrio, allora X e' fra FGH ed e' piu' leggera. Terza pesata, confronto F con G.
3) Scende DLMN, allora X=D piu' pesante oppure X=E piu' leggera. La terza pesata sara' confrontare una di queste, diciamo D con una sicuramente regolare.

Secondo Caso, i piatti restano in equilibrio. X e' fra ILMN.
Seconda Pesata = ILM ABC.
Dato che ABC sono tutte regolari, se c'e' equilibrio, X=N, e la terza pesata consiste nel confrontare N con A.
Se ILM e' piu' pesante o piu' leggero, con la terza pesata , verranno testate I con L.

SECONDO METODO Notazione:
/ Scende il piatto di sinistra. \ Scende il piatto di destra. = Equilibrio.
Per un risultato certo, ciascuna pallina deve subire un trattamento personalizzato... diverso da ogni altra.
Considerazioni preliminari
a) Tutte le palline devono essere pesate almeno una volta.
b) Occorrono 24 risultati differenti, perche' la difettosa puo' essere scelta fra 12 ed essere piu' pesante o piu' leggera.
c) Con 3 pesate e' possibile ottenere 27 diversi risultati, ma nel nostro caso se una pallina difettosa e' presente, = = = per le tre pesate non sara' possibile.
d) Dobbiamo eliminare altri 2 risultati, per comodita' scegliamo \\\ e ///, bastera' non pesare la stessa pallina per 3 volte sullo stesso piatto.

Per una distribuzione inequivocabile, dividiamo le nostre palline in quattro gruppi di 3.
Questa volta rappresento le palline con le lettere ABC, DEF, GHK, XYZ, divise cosi' nei quattro gruppi.
Per distribuire sulla bilancia le palline di ciascun gruppo in modo diverso, posso avvalermi del seguente schema:

            Fuori          Piatto        Piatto
            Bilancia       Sinistro      Destro

ABC         0              1             2
DEF         1              2             0
GHK         2              0             1
XYZ         1              1             1

Lo schemino ci indica che per ogni pesata le palline ABC non devono essere escluse (Fuori Bilancia = 0), una sara' sempre sul piatto di sinistra e due sul piatto di destra. Per la considerazione fatta al punto d) la pallina sul piatto di sinistra non puo' essere sempre la stessa. Cosi' anche per gli altri gruppi. Delle palline DEF, una sara' sempre fuori bilancia, due sul piatto di sinistra, e nessuna sul piatto di destra ecc..
Con un po' di attenzione e trattando le palline di ciascun gruppo ciclicamente, possiamo finalmente trovare una distribuzione per ciascuna pesata che rispetta cio' che si e' detto:


             Fuori          Piatto        Piatto
             Bilancia       Sinistro      Destro

Prima         DHKX          AEFZ          BCGY
Seconda       EKGY          BFDX          CAHZ
Terza         FGHZ          CDEY          ABKX

Osservando lo schema possiamo dire che se nessuna pesata risultera' bilanciata, la pallina difettosa e' stata pesata 3 volte, percio' fara' parte del gruppo ABC.
Se una sola pesata risultera' in equilibrio e nelle altre due e' sceso lo stesso piatto, deve essere nel gruppo DEF.
Con 2 pesate in equilibrio su tre, la pallina e' da cercare nel gruppo GHK.
Infine se sara' fra XYZ ci sara' stata una pesata in equilibrio, e per le altre due sara' sceso prima un piatto poi l'altro.
Ogni possibile risultato delle tre pesate Individuera' una ed una sola pallina:

/\\   A+        \//   A-
\/\   B+        /\/   B-
\\/   C+        //\   C-

=//   D+      =\\   D-
/=/   E+       |=|   E-
//=   F+       \\=   F-

==\   K+      ==/   K-
=\=   H+      =/=   H-
\==   G+      /==   G-

=/\   X+       =\/    X-
\=/   Y+       /=\    Y-
/\=   Z+       \/=    Z-

A questo punto possiamo affrontare un problema leggermente piu' complicato:
Date 13 palline fra cui forse una e' difettosa, ed una quattordicesima pallina sicuramente normale, trovare l'eventuale pallina differente, e dire se sia piu' pesante o piu' leggera.
Utilizzando la stessa soluzione del problema precedente (secondo metodo), possiamo facilmente sciogliere la matassa, difatti non faremo altro che aggiungere sul piatto di sinistra la tredicesima pallina, e sul piatto di destra la pallina regolare in tutte le pesate.
Se la difettosa e' tra le prime 12, i risultati restano quelli visti in precedenza, con = = = non ci sono palline difettose. Con /// oppure \\\ la 13esima e' piu' pesante o piu' leggera rispettivamente.
Questo e' un problema che possiamo definire "perfetto" perche' sono richiesti 27 esiti, tutti quelli ottenibili con tre pesate.
Alcune generalizzazioni sono state studiate da Roberto Magari (6) e Dani Ferrari (7).
Se pensiamo ad n palline di cui 0,1,2, o 3 possono essere piu' pesanti oppure differenti, si possono confezionare decine di enigmi, fino ad arrivare a mostruosita' non risolvibili con mezzi umani, come questa proposta da Ferrari:

Avete 16 monete d'oro, in apparenza tutte uguali.
Forse sono tutte buone, forse una o due o tre sono false.
Se ci sono monete false, sono piu' leggere di quelle buone.
Con la solita bilancia, in 6 pesate trovate se e quante monete false esistono e individuatele

Ci sono 3^6 = 729 possibili risultati con 6 pesate, ed il problema per come e' posto, ammette 697 casi.

Abbandoniamo ora le bilance a doppio piatto e prepariamoci ad affrontare un problema del tutto diverso, ma non certo piu' semplice utilizzando una moderna bilancia elettronica con esatta lettura del peso.
Il problema e' questo:

Date sei palline di cui una di peso differente, individuarla in 3 pesate, stabilendo anche il peso esatto sia delle palline regolari che quello della pallina difettosa

Dal momento che non abbiamo dati riguardanti il peso delle regolari, tantomeno alla differenza in piu' o in meno che puo' assumere la pallina cercata, la soluzione dovra' essere data dal confronto finale dei tre risultati.
Dovremo distribuire le palline nelle tre pesate in modo diverso l'una dalle altre, se ad es. una pallina fosse coinvolta solo nella prima pesata, questa, affinche' possa essere distinta dalle altre, deve essere l'unica con tale caratteristica.
Una siffatta distribuzione valida fino a 7 palline, si puo' ottenere prendendo le disposizioni con ripetizione di 2 oggetti presi 3 alla volta.
Se A,B,C indicano le tre pesate , "1" quando una pallina viene posta sul piatto, "0" quando ne resta fuori, possiamo scrivere (tralasciando il caso banale) le seguenti combinazioni:

Palline ->      1  2  3  4  5  6  7  
A               0  0  0  1  1  1  1
B               0  1  1  0  0  1  1
C               1  0  1  0  1  0  1

La tabella indica le seguenti pesate:

A = palline  4,5,6,7
B = palline  2,3,6,7
C = palline  1,3,5,7

Sembrerebbe cosi' di aver gia' risolto il problema, difatti se ci fosse differenza nella prima pesata, questa indicherebbe subito la pallina num.4.
Tuttavia non sappiamo se sia piu' pesante o piu' leggera, percio' per ogni risultato ci sono ancora due possibilita'.
Un esempio chiarira' meglio questo punto.
Supponiamo di ottenere 60, 60, 58 grammi per le tre pesate, i casi sono 2.

a) L'unica pallina che compare nell'ultima pesata, la num. 1, e' piu' leggera di 2 grammi e le regolari peserebbero 20g.
b) L'unica pallina che compare nelle prime due pesate, la num.6 e' piu' pesante di 2 grammi, e le regolari peserebbero 14.5g.

Per evitare questa ambiguita', dovremo eliminare alcune delle 7 combinazioni prese in esame.
Vi sono 2 modi doistinti per selezionare 5 combinazioni utili dalle sette appena viste.

Primo Modo
Palline -> 1  2  3  4  5
A          1  1  1  0  0
B          1  0  0  1  1
C          0  1  0  1  0

A = palline 1,2,3
B = palline 1,4,5
C = palline  2,4

In questo modo il problema con 5 palline e' senz'altro risolto, difatti se ci fossero solo palline regolari, varrebbe la relazione 2A=2B=3C ed una differenza in uno o piu' di questi rapporti determina in modo inequivocabile la pallina cercata. Se ad esempio, i risultati fossero A=37, B=36, C=25, si vede subito che per ristabilire la relazione vi e' un eccesso di 1 grammo nella prima e terza pesata. Potremmo concludere che la pallina num.2 pesa 13g. e le altre 12g. ciascuna.

Secondo Modo
Palline -> 1  2  3  4  5
A          1  1  1  1  0
B          1  1  0  0  1
C          1  0  0  1  0

A = palline  1,2,3,4
B = palline  1,2,5
C = palline  1,4

La relazione diventa 3A = 4B = 6C e come nel caso precedente, una differenza indica la pallina difettosa in modo univoco.
Questo secondo caso, a differenza del primo, ci permette l'introduzione della sesta pallina !!
Notando che le prime due pesate coinvolgono tutte le 5 palline, se la difettosa e' fra queste dopo la seconda pesata si osserverebbe una differenza nella relazione 3A = 4B e procederemmo come visto pesando 1,4.. Se invece 3A = 4B fosse rispettata, procederemmo nella terza pesata con C=6.
Questa e' l'unica procedura che risolve il problema dato.
Il passo successivo lo fece il giapponese Kobon Fujimura, proponendo sul RMM (8) di trovare, determinando anche il peso, una pallina difettosa su 15 in 4 pesate.
Devo dire che questo e' un problema davvero complesso ed alla luce di cio' che abbiamo detto per il problema precedente, 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.

Riferimenti bibliografici
1) Niccolo' Fontana "Trattato de' numeri e misure" 1556 libro I cap. XVI art. 32
2) Bachet de Mezierac " Problemes palaisans et delectable" 1612, prob.V pag,154
3) Luca Pacioli "De viribus quantitatis" ~ 1500
4) Mac Mahon "" Quaterly Journal of Mathematics" 1886 vol.XXI pp 367-373
5)"Scripta Mathematica" 1945, vol 11 num.3-4 pag 360
6) Roberto Magari "Palline e Pesate" rivista Sapere aprile 1984 pp 57-58
7) Dani Ferrari "MC Microcomputer" num.144 ottobre 1994 pp 276-279
8) Kobon Fusjimura " Recreational Mathematics Magazine" num.2

Aggiungo qui sotto alcune varianti non banali. ID(n) e �l numero di identifacazione del libro dove il problema e' pubblicato.
ID(n) e' riferito alla lista dei libri in mio possesso.

ID(1120) pag.137
Ti vengono date 6 palle. Due rosse, due blu e due gialle.
Sono identiche in apparenza, ma una rossa, una blu ed una gialla hanno lo stesso peso e le chiameremo leggere.
Anche le rimanenti 3 hanno lo stesso peso, ma maggiore delle altre. Schematicamente possiamo scrivere:
R=B=G > r=b=g.
Utilizzando la bilancia a doppio piatto due sole volte, determina la pesante e la leggera di ogni colore.

ID(1120) pag. 137
Ti vengono date 5 palle da biliardo.Identiche in apparenza.
Tre di queste sono regolari ed hanno lo stesso peso. Delle rimanenti due, una e' piu' pesante ed una piu' leggera delle normali.
Queste ultime due, insieme pesano come due palle regolari.
Determina la pesante e la leggera usando una bilancia a doppio piatto il minimo numero di volte possibile.

ID(1120) pag. 137
Simile al precedente, ma con 9 palle.
Sette sono regolari, una pesante ed una leggera, queste ultime due, insieme bilanciano 2 palle regolari.
Determina la pesante e la leggera usando una bilancia a doppio piatto il minimo numero di volte possibile.

ID(1022) pag. 123
Sono date 5 palle tutte differenti in peso. Con una bilancia a doppio piatto, ordinarli dalla piu' pesante alla piu' leggera in 7 pesate.

ID(1048) pag. 147
Ci sono 9 scatole di mentine nella mia dispensa.
Quel birichino di mio nipote ha preso un certo numero di mentine da una delle scatole e le ha rimesse in una delle 9 scatole a caso.
Ora ci sono 2 possibilita':
a) Le scatole hanno conservato lo stesso peso.
b) Una scatola e' piu' pesante ed una piu' leggera, esattamente della stessa quantita'.
Con una bilancia a doppio piatto, stabilire quale sia la scatola piu' pesante e quella piu' leggera oppure appurare l'equita' dei pesi in quattro pesate

ID(1048) pag.124
Sono date 4 scatole di monete.Ciascuna scatola ne contiene 13.
Due scatole contengono solo monete genuine, mentre le altre due contengono monete contraffatte.
Le monete contraffatte pesano 2 grammi di piu' o due grammi di meno delle normali.
Tutte le monete false contenute nella stessa scatola sono uguali, ma non necessariamente dello stesso peso dell'altra scatola con monete false. Il peso delle monete regolari e' conosciuto. Identifica con una sola pesata le due scatole con monete false utilizzando una bilancia elettronica sufficientemente precisa.