Problemi di pesate

Mariano Tomatis
Ci sono 10 palline, una delle quali e' DIFFERENTE dalle altre.
Per "DIFFERENTE" si intende piu' leggera o piu' pesante.
Bastano 3 pesate con una bilancia a due braccia per isolare quella DIFFERENTE?

seguono le risposte al quesito proposto, ed una interessante discussione sulla generallizzazione del problema.

Paolo Licheri
Siano ABCDEFGHIL le palline
Prima pesata:
ABC-DEF
se i pesi sono equilibrati, la pallina anomala e' nel gruppo GHIL
quindi
seconda pesata
GHI-ABC
se equilibrata, la anomala e' L, e con la terza pesata A-L stabilisco se e' leggera o pesante
se la seconda pesata e' squilibrata, supponiamo GHI>ABC, ho stabilito che la pallina anomala e' nel gruppo GHI, ed e' piu' pesante della norma; quindi
terza pesata G-H
se equilibrata, L e' pesante
se squilibrata, individuo tra le due quella pesante.

Se invece la prima pesata e' squilibrata, p.es. ABC>DEF ho le seguenti informazioni:
_la pallina anomala e nel gruppo delle sei, mentre GHIL sono normali
_se la anomala e' nel gruppo ABC e' pesante, mentre se e' nel gruppo DEF e' leggera
quindi
seconda pesata
ABDE-GHIL
se equilibrata, la pallina anomala puo' essere C (pesante) o F (leggera),
e con la terza pesata A-C risolvo il problema
se la seconda pesata e' squilibrata,
se ABDE>GHIL, stabilisco che la pallina anomala e' A o B (pesante), quindi
terza pesata A-H
se ABDE<GHIL, stabilisco che la pallina anomala e' D o E (leggera), quindi
terza pesata D-H

Sandro.san
le palline: ABCDEFGHIL

1) peso ABC DFE
uguale : vai 2)
piatto uno piu' pesante vai 3)
piatto due piu' pesante vai 4)

2) peso AB IL
uguali: e' G o H: vai 5)
piatto uno: 6)
piatto due : 7)

3) peso ABD CIL
uguali: e' F o E: vai 8)
piatto uno: e' A o B: vai 9)
piatto due: e' C o D: vai 10)

4) come 3) ma scambiando ABC con DEF

5) peso A G: trovo la soluzione
6) peso A I : trovo la soluzione
7) peso A I: trovo la soluzione

8) peso A E
9) peso A E
10) peso D E

Si puo' fare con 11?

penso di si: (_penso_):
le palline: ABCDEFGHILK

1) peso ABC DFE
uguale : e' GHILK vai 2)
altrimenti e' come prima.


2) peso GH IA
uguali: e' LK: vai 5)
piatto uno: 6)
piatto due : 7)

5) peso A L e trovo la soluzione

6) peso G H
uguali: e' I
piatto uno e' G
piatto due e' H

7) peso G H
uguali e' I
piatto uno e' H
piatto due e' G

Comunque il concetto e' quelli di scambiare "alcune" palline tra una pesata e l'altra per aumentare l'informazione disponibile.

Barabbino
Prendi 6 palline: 3 da una parte e 3 dall'altra

I caso) PESO IDENTICO

prendi due delle 4 palline restanti e le metti sui due piatti:

caso a) peso diverso

togli una delle due palline e la sostituisci con un'altra qualunque (che siamo sicuri essere "normale"): Se i pesi sono diversi, la pallina "differente" e' quella non sostituita, viceversa e' quella
sostituita (e individui anche se e' + leggera o + pesante).

caso b) peso uguale

prendi UNA SOLA(*) delle restanti due palline e la metti sulla bilancia con un'altra pallina qualunque (che e' "normale"):
se i pesi sono uguali la pallina "dfferente" e' l'unica rimasta (ma non sai se e' piu' leggera o piu' pesante) , viceversa e' (*)quella scelta (e individui anche se e' + pes. o + legg.)

II caso) PESO DIVERSO

Chiamiamo A il piatto di sinistra e B quello di destra:
tolgo due delle tre palline dal piatto B, le metto da parte e sposto una pallina dal piatto A al piatto B. In questo modo ho 2 palline su entrambi i bracci della bilancia;

caso c) peso uguale
Vedi caso b

caso d) peso diverso

Sottocaso 1) il peso e' "diverso" allo stesso modo di come lo era nel II caso), cioe' se il piatto A saliva (scendeva), continua a salire (scendere); allora vuol dire che in A c'e' una palla piu' leggera (pesante) o che in B ce ne e' una piu' pesante (leggera).
Allora tolgo le due palle dal piatto B (ricordandomi pero' quale delle due e' quella che e' sempre stata nel piatto B (vedi caso II);
Se pesano uguali, allora la pallina "diversa" e quella delle due palle che ho tolto che e' sempre rimasta nel piatto B e pesa di piu' (di meno);
se invece i pesi sono diversi, la palla diversa e' quella piu' leggera (pesante).

Sottocaso 2) il peso e' diverso in maniera differente da come lo era nel caso II (cioe' se il piatto A saliva (scendeva) orascende (sale))

Allora vuol dire che il piatto A conteneva una palla piu' leggera (pesante) che e' proprio quella che ho spostato sul piatto B.

Giorgio Vecchi
Partiamo mettendone 4 e 4. Se sono pari si riesce facilmente ad individuare la differente tra le altre 2 con 2 pesate.

Se non sono pari, chiamiamo P ogni pallina potenzialmente pesante (quella che sta sul braccio che è sceso) e p ogni pallina potenzialmente leggera (quella che sta sul braccio rimasto su) e N ognuna delle due normali
rimaste.

Alla seconda pesata si possono disporre così:

ppPP pPNN

se scende a sinistra, con la terza pesata si possono mettere le 2 P di sinistra ognuna su un piatto e quella che scende è più pesante e se rimangono pari è la p di destra a essere più leggera.
Se scende a destra si fa la stessa cosa con le 2 p di sinistra. Se rimangono pari ho due palline p e P da individuare con una pesata.

Sandro.san
Rilancio con 13 (e' la mia ultima offerta!!)

Se e' vero che si puo' fare con 13, di sicuro non e' detto che si riesca a sapere se e' piu' pesante o piu' leggera.
Forse in questo caso il limite e' proprio 10?

Giorgio Vecchi
In realtà il limite è 12 (determinando anche il peso della pallina anomala).
Dopo la prima pesata pari, rimangono 4 palline. Se ne mettono 3 su un piatto e 3 normali sull'altro; se rimangono pari si ha una pesata per determinare il peso di quella rimasta; se un braccio scende (o sale) significa che tra le 3 c'è quella pesante (o leggera), basta pesarne 1 e 1 e si determina tutto.

Ma si può arrivare fino a 13, sempre determinando anche il peso della pallina anomala. Si risolve però utilizzando un piccolo trucco: si può fare uso di una quattordicesima pallina che abbia peso "normale".

Vi lascio il piacere di risolverlo

Giovanni Rana
Bè, ci penso io. Per brevità, glisserò sulle parti ovvie: se qualcuno vuole, posterò poi pure quelle.

Siano 1 2 3 4 5 6 7 8 9 10 11 12 13 e 14 ( normale) le palline: la prima pesata è (1 2 3 4 5),(6 7 8 9 14).
Se i piatti restano in pari, allora dobbiamo trovare una pallina differente fra quattro usando due pesate ed una pallina di peso noto, e questo è immediato.
Se invece non restano in pari, allora uno dei piatti sale e l' altro scende:
1) Scende (1 2 3 4 5). Divido le nove palline incriminate in tre insiemi con intelligenza, (1 2 6) , (3 4 7 ) e ( 5 8 9) . Metto sui piatti (1 2 3 ), (3 4 7):
se restano livellati devo sgamare la pallina fra (5 8 9) con una sola pesata, ma sapendo che il possibile "difetto" di 8 e 9 è dello stesso tipo e quello di 5 del tipo opposto. E questo è pure banale. Allora supponiamo che non restino livellati: i due insiemi (1 2 6) e (3 4 7 ) son del tutto equivalenti, per cui si può supporre sempre che scende ( 1 2 6 ). Quindi le palline incriminabili son ( 1 2 7 ): nota che , come per ( 5 8 9), 1 e 2 hanno la stessa possibilità di difetto e 7 l' altra, per cui la soluzione è altrettanto banale.
2) Scende ( 6 7 8 9 14) . Qui potrebbe sempre che non ci sia simmetria, dato che una volta scende un piatto di palline "ignote" e una volta scende un piatto in cui una è nota. Non è così, ovviamente: questa pesata serve solo per partizionare l' insieme delle nove palline in due insiemi disgiunti, per così dire di "colore diverso". E difatti la partizione successiva delle palline in tre insiemi resta la stessa, e pure i ragionamenti, dove non a caso ho parlato di tipi diversi e non di palline più pesanti o più leggere.

Giorgio Vecchi
Esatto!

Volevo aggiungere qualche considerazione.

13 è il massimo. Ad ogni pesata sono possibili 3 esiti: o scende da una parte, o scende dall'altra o rimane in equilibrio.
Con n pesate i possibili diversi "risultati" sono 3^n. Nel caso di 3 pesate sono 27 e, se le pesate sono ben concepite, ognuno di questi casi è associabile all'individuazione di una pallina anomala: 13 stabiliscono che una determinata pallina delle 13 è più pesante, altri 13 che è più leggera e il 27° caso è quello in cui i bracci della bilancia rimangono in equilibrio nelle 3 pesate e ciò permette di dire che non c'è alcuna pallina anomala.

Quindi rilancio la palla (o la pallina?) per l'ultima volta (o almeno credo).

Bisogna trovare un modo, una volta "battezzate" tutte le palline (ad esempio numerandole da 1 a 13), per pre-impostare opportunamente le 3 pesate e sulla base dei 3 esiti risalire al numero e al peso della pallina anomala utilizzando una semplice formula.
Mi spiego meglio: il modo di disporre le palline sui piatti della biliancia nelle 3 pesate deve essere stabilito una volta per tutte prima di cominciare a pesare e non cambia in base agli esiti delle pesate stesse. Una opportuna predisposizione delle pesate fa sì che sia possibile risalire alla pallina anomala attraverso l'applicazione di una corrispondente formula applicata agli esiti delle 3 pesate stesse.

E' sempre necessario utilizzare la 14a pallina "normale", che ha sempre e solo una funzione equilibratrice.

Dario Uri
Abbiamo gia' trattato moltissimi problemi di pesate in passato. Spingendoci anche in terreni complessi, ma questa variante ancora no.
Per il momento considero solo le 12 palline, vedremo alla fine come aggiungere la 13esima.
Ci sono molti modi per selezionare a priori le 3 pesate, serve solo che ciascuna pallina abbia un trattamento personalizzato, se ed es. la pallina n e' presente sul piatto di sinistra nelle prime due pesate, deve essere l'unica con questa distribuzione.
Un metodo per associare i tre risultati al numero della pallina cercata con un calcolo, e' dato da Martin Gardner in Enigmi.... num.5 pag.133,
usa naturalmente il sistema ternario, ma il procedimento e' tuttaltro che semplice.
Allora ci provo utilizzando un "sistema ternario bilanciato", dove viene eliminata la cifra 2, ed ogni potenza di 3 puo' essere presa solo una volta, in questo caso si utilizzano anche le potenze negative.
Comincio con esprimere i numeri da 1 a 13 in suddetto modo:


3^n=9 3 1

1= 0 0 1
2= 0 1 -1
3= 0 1 0
4= 0 1 1
5= 1 -1 -1
6= 1 -1 0
7= 1 -1 1
8= 1 0 -1
9= 1 0 0
10= 1 0 1
11= 1 1 -1
12= 1 1 0
13= 1 1 1



Considero ora le 3 colonne come indicanti le 3 pesate da effettuare ed 1=pallina sul piatto di destra, -1 pallina sul piatto di sinistra, 0=pallina fuori bilancia.
Perche' questo sia possibile devo operare un bilanciamento, far risultare cioe' per ciascuna colonna 4 segni 1, 4 segni -1 e 4 segni 0.
Una riga andra' eliminata. Il modo piu' semplice per fare questo, e' di invertire i segni + e - delle palline dispari 1,3,5... ottengo cosi':
(le 3 pesate ABC le metto in orizzontale)


1 2 3 4 5 6 7 8 9 10 11 12 13

A) 0 0 0 0 -1 1 -1 1 -1 1 -1 1 -1
B) 0 1 -1 1 1 -1 1 0 0 0 -1 1 -1
C) -1 -1 0 1 1 0 -1 -1 0 1 1 0 -1


Posso vedere che un perfetto equilibrio dei 3 segni -1,0,1 lo ottengo eliminando la pallina num.7.
Allora numero le mie 12 palline da 1 a 13 (senza la 7) e procedo alle 3 pesate come indicato dallo schemino,
ricordo -1 = piatto SX, 1= piatto DX:


Prima pesata
SX= 5,9,11,13
DX= 6,8,10,12

Seconda pesata
SX= 3,6,11,13
DX= 2,4,5,12

Terza pesata
SX= 1,2,8,13
DX= 4,5,10,11


A questo punto, non c'e' bisogno di calcoli, il risultato delle 3 pesate (-1 se si abbassa a SX, 1 se si abbassa a DX, 0 in caso di equilibrio) indica in ternario bilanciato, il numero della pallina cercata.
Se il risultato e' positivo, la pallina indicata e' piu' pesante altrimenti e' piu' leggera (RICORDANDO DI RIINVERTIRE I SEGNI SE LA PALLINA E' DISPARI).

Se ad es. per le prime 2 pesate scende il piatti di SX, e c'e' equilibrio nella terza pesata, avro' -1,-1,0 = -9, -3, 0 = -12 e' la pallina mum 12 piu' leggera delle altre.

Ma tu hai proposto il sistema "completo" di 13 palline + un campione,
allora numero come 7, l'ulteriore pallina, pareggiando la simmetria con quella buona = B. Dato che lo schema prevedeva per la 7 -1,1,-1 diventa:




Prima pesata
SX= 5,9,11,13,7
DX= 6,8,10,12,B

Seconda pesata
SX= 3,6,11,13,B
DX= 2,4,5,12,7

Terza pesata
SX= 1,2,8,13,7
DX= 4,5,10,11,B


Il conto finale resta lo stesso.
E' il tuo metodo ancora piu' semplice ?
Questo e' il massimo che ho potuto fare.

Giorgio Vecchi

... e direi che hai proprio fatto il massimo!!! E' proprio il mio metodo!


Una volta definiti a, b e c gli esiti delle 3 pesate, la semplice formula cui facevo riferimento è:

p = 9a+3b+c

o più in generale, definito e[i], l'esito della i-esima pesata:

p = sommatoria(i=1..n) 3^(i-1)*e[i] (invertendo l'ordine delle pesate rispetto a prima),

sempre ricordandosi di invertire di segno quando p è dispari (e quindi moltiplicando il risultato per (-1)^p ).

Questo perché il metodo è generalizzabile per n pesate e quindi può essere applicato a 40 palline con 4 pesate, 121 palline con 5 pesate e così via.

Come giustamente hai fatto notare, eliminando la pallina numero 7 si riesce ad individuare la pallina anomala tra 12 palline senza ricorrere alla pallina equilibratrice. Questo è quindi un ennesimo metodo (per me il più elegante) per risolvere il problema delle 12 palline.

Per quanto riguarda la scomposizione di ogni valore di pallina nei corrispondenti -1, 0 e 1, si può operare "a mano" individuando l'opportuna somma delle potenze di 3 con eventuale segno negativo, oppure operando in maniera automatica attraverso una trasformazione in base 3 del valore della pallina + 13 (oppure (3^n-1)/2), con l'avvertenza che le cifre trovate devono essere tutte scalate di 1.
Es. per la pallina 11 si dovrà trasformare
24 (11+13) in base 3 che dà 220 e togliere 1 ad ogni cifra per ottenere 1, 1, -1.

indice varie

home