Newsgroup: it.hobby.enigmi
Titolo: Ancora le 12 palline

Ciao a tutti.
Ricordate il classico problema delle 12 palline di cui una è "differente" 
(più leggera o più pesante) delle altre?
In esso si deve stabilire qual è tale pallina, usando una bilancia a due 
piatti, con 3 sole pesate.
Il problema è molto conosciuto, si può leggerne il testo e la soluzione per 
esempio qui: 
http://utenti.quipo.it/base5/misure/pesi.htm
 (è il problema nr. 
11).
Supponiamo invece di utilizzare una tradizionale bilancia da cucina, cioè di 
quelle con un solo piatto, che indichi il peso di ciascuna pesata.
Qual è il numero minimo di pesate che permette di trovare la pallina 
differente tra le 12?
A presto
Francesco 

"Francesco Di Matteo" <frank...@TEMPOlibero.it> ha scritto nel messaggio 
news:4c978663$0$40287$4faf...@reader2.news.tin.it...

Ovviamente, come nel problema originale citato, trovare la pallina 
"differente" significa anche definire se è più leggera o più pesante delle 
altre... 

"Francesco Di Matteo" <frank...@TEMPOlibero.it> ha scritto nel messaggio 
news:4c978b13$0$40283$4faf...@reader2.news.tin.it...

Quella "differente" è solo leggermente più leggera o pesante delle altre
(non ad es. il doppio o la metà...)
Quattro pesate (forse sono troppe?) 

"Francesco Di Matteo" <frank...@TEMPOlibero.it> wrote in message 
news:4c978663$0$40287$4faf...@reader2.news.tin.it...

Intanto propongo una soluzione semplice da 5, in attesa di vedere quella da 
4.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Divido le 12 palline in 3 gruppi da 4 e li peso. Otterò due pesi "uguali" e 
uno "diverso". La pallina in questione è in quello diverso. Ne peso due di 
questo gruppo e sulla base del confronto con i precedenti "uguali" 
stabilisco in quale dei due gruppi da 2 è la pallina. Analogamente, da 
quest'ultimo gruppo ne prendo una e con l'ultima pesata la individuo e so 
quanto pesa.
Ciao
Giorgio
 

 da 4.
Scrivo la mia soluzione in 4...
SPOILER

.
.
.
Distribuisco 11 palline in 4 pesate A, B, C e D e ne confronto i pesi 
ottenuti. Le palline coinvolte in ciascuna pesata rappresentano una certa 
sintesi delle disposizioni di due oggetti (presente/assente) presi a 4 per 
volta.
A) 1, 2, 3, 4, 5, 6
B) 1, 2, 3, 7, 9, 10
C) 1, 4, 8, 9, 11
D) 1, 2, 4, 5, 7, 8
Tra di esse vale la relazione 5A=5B=6C=5D
Se ci sono delle discordanze nei pesi si capisce subito qual è la pallina 
incriminata.
Per esempio se ottengo A=62, B=62, C=50 e D=62, c'è un eccesso nelle pesate 
A, B e D e quindi è la pallina 2 che pesa 12 rispetto alle altre che pesano 
10.
Se, altro esempio, ottengo A=24, B=23, C=19, D=24 c'è un difetto nelle 
pesate B e C quindi è la pallina 9 che pesa meno (cioè 3) rispetto alle 
altre.
Se nelle prime 3 pesate non ci sono discordanze nella relazione 5A=5B=6C 
allora, dato che tutte le 11 palline sono coinvolte in esse, quella 
differente è la 12, mentre C/5 (oppure A/6) è il peso di una pallina 
normale.
Per cui posso effettuare l'ultima pesata così:
D) 12
Francesco

 10.
Non potrebbe essere la 11 che pesa meno?
Mauro


Sě, ehm... mi sa tanto che hai ragione.
Conviene differenziare il piů possibile le pesate, per numero di palline.
Per esempio
A) 1, 2, 3, 4, 5, 6, 7 (7 palline)
B) 1, 2, 3, 8, 9, 10 (6 palline)
C) 1, 4, 5, 8, 11 (5 palline)
D) 2, 4, 6, 9 (4 palline)
Cosě pur rimanendo diverse le singole disposizioni non possono sorgere 
equivoci, e la relazione tra i vari pesi diventa:
60A = 70B = 84C = 105D
Nell'esempio sopra dove supponevo le normali = 10 e la pallina 2 quella 
"differente" = 12 avremo:
A = 72
B = 62
C = 50
D = 42
e non ce modo di credere che sia la 11 la piů leggera, dato che p. es.  A/7 
č diverso da B/6 o da D/4.

 A/7 è diverso da B/6 o da D/4.
Quindi con n pesate si possono discriminare fino a 2^n-1 palline
infatti 2^n-1 è la somma di tutte le combinazioni COMB(n,x) da x=1 a n
con 4 pesate le palline massime sono 2^4-1=15
pallina      da mettere nelle pesate:
1 ____________1
2 ____________ 2
3 ____________ 3
4 ____________ 4
5 ____________ 1,2
6 ____________ 1,3
7 ____________ 1,4
8 ____________ 2,3
9 ____________ 2,4
10 ___________ 3,4
11 ___________ 1,2,3
12 ___________ 1,2,4
13 ___________ 1,3,4
14 ___________ 2,3,4
15 ___________ 1,2,3,4
ovvero
pesata_1 = 1 5 6 7 11 12 13 15
pesata_2 = 2 5 8 9 12 14 15
pesata_3 = 3 6 8 10 11 13 14 15
pesata_4 = 4 7 9 10 11 12 13 14 15
es:
se eccedono o scarseggiano le pesate 2,3,4 la pallina diversa è la 14
se ecc. o scar. le pesate 1,4 la pallina diversa è la 7
ecc...

 Quindi con n pesate si possono discriminare fino a 2^n-1 palline
Un po' meno, perché le pesate devono avere un numero diverso di palline.
In realtà, sapendo quali sono le pesate che non tornano, si può arrivare
a 2^n palline; una non verrà mai pesata, se le pesate tornano tutte la
pallina diversa è quella.
Con n (> 2) pesate il numero massimo di palline dovrebbe essere 
2^n - (n-1).
Per avere un numero diverso di palline in ogni pesata[*], basta eliminare
per esempio la palline che compaiono
- solo nella prima pesata
- solo nelle prime 2 pesate
...
- solo nelle prime n-1 pesate
(totale n-1 palline eliminate).
[*] è necessario che le pesate siano *tutte* diverse?
Mauro

 Un po' meno, perché le pesate devono avere un numero diverso di palline.
e perchè mai?
Le pesate possono anche essere tutte con lo stesso numero di palline.
La pallina di peso diverso si trova controllando la divisibilità del peso 
trovato col numero di palline presenti per pesata:
Es: mettiamo diavere 15 palline: 14 di peso 9 e 1 di peso 5
distribuiamo le pesate come esposto:
pesata_1 = 1 5 6 7 11 12 13 15
pesata_2 = 2 5 8 9 12 14 15
pesata_3 = 3 6 8 10 11 13 14 15
pesata_4 = 4 7 9 10 11 12 13 14 15
la pesata 1 e la 3 hanno 8 palline, la pesata 2 ne ha 7 e la pesata 4 ne ha 
9.
Per trovare la pallina di peso diverso basta controllare la divisibilità per 
8 del peso trovato con le pesate 1 e 3, la divisibilità per 7 della pesata 2 
e la divisibilità per 9 della pesata 4.
Se il peso di una pesata non è divisibile per il numero totale di palline in 
quela pesata allora è sicuro che li c'è una pallina di peso diverso dalle 
altre.
Una volta che sappiamo in quali pesate è presente la pallina col peso 
diverso è facile trovarla seguendo lo schema
pallina    pesate col peso non divisibile
               per il numero di palline in quella
               pesata
1 ______1
2 ______ 2
3 ______ 3
4 ______ 4
5 ______ 1,2
6 ______ 1,3
7 ______ 1,4
8 ______ 2,3
9 ______ 2,4
10 ______ 3,4
11 ______ 1,2,3
12 ______ 1,2,4
13 ______ 1,3,4
14 ______ 2,3,4
15 ______ 1,2,3,4
es. mettiamo la pallina col peso 5g al numero 8, tutte altre sono di 9g
le  pesate risultano
pesata_1 = 72g
pesata_2 = 59g
pesata_3 = 68g
pesata_4 = 81g
72 è divisibile per 8 quindi la pesata 1 è a posto.
59 non è divisibile per 7 quindi la pesata 2 contiene la pallina diversa.
68 non è divisibile per 8 quindi anche la pesata 3 continene la pallina 
diversa.
81 è divisibile per 9.
le pesate che contengono la pallina diversa sono la 2 e la 3.
nello schema sopra è facile vedere come 2,3 corrisponda appunto alla pallina 
8. c.v.d. ;-)
ps.
metto le mani avanti: il caso di una pallina eccentrica col peso doppio 
rispetto alle altre non è contemplato! :-P

 e la divisibilità per 9 della pesata 4.
E se le palline hanno tutte un peso multiplo di 504?
Oppure se il peso non è intero?
Mauro

 E se le palline hanno tutte un peso multiplo di 504?
è uguale, l'importante è che la "pallina diversa" non abbia un peso multiplo 
delle altre.
Avevo infatti aggiunto un ps mettendo le mani avanti. :-)

>" Se hai ragione.."
non è dubitativo.. era "Si ai ragione.."  ;-) 

 non è dubitativo.. era "Si ai ragione.."  ;-)
pure con l'acca! :-P


Ciao Pedro,
scusa non capisco questa tua risposta a Mauro.
Ad ogni modo controlla la tua disposizione delle pesate, mi pare che sia 
errata.
Tu comunque svilupperesti l'integrale di 4 doppie in 16 colonne ed escludi 
solo il caso banale di *nessuna pallina*.
Però così le pesate coinvolgono sempre 8 palline.
Come Mauro mi aveva già fatto notare, con pesate omogenee permangono le 
ambiguità.
Francesco 

 Però così le pesate coinvolgono sempre 8 palline.
 sono 8 solo alla pesata 1 e 2, alle altre due sono 7 e 9.
 vedi sopra.

 errata.
avevo ritoppato! :)
la sequenza giusta in effetti è
p1 = 1 5 6 7 11 12 13 15
p2 = 2 5 8 9 11  12 14 15
p3 = 3 6 8 10 11 13 14 15
p4 = 4 7 9 10  12 13 14 15
sono tutte di 8. Allora si bisogna che ci sia qualche pallina in meno 
rispetto a 15 per levare l'indeterminazione. 

 pure con l'acca! :-P
..e pure per "tutte le pesate con 8 palline" avevi ragione, avevo sbagliato 
io a riportare la serie di combinazioni.
Allora si..serve qualche pallina (1 basta?) meno rispetto a 2^n-1 

 Allora si..serve qualche pallina (1 basta?) meno rispetto a 2^n-1 
Rispetto a 2^n perché puoi avere una pallina che non viene pesata
(quando non ci sono pesaate anomale è lei); il problema chiede solo di
individuare la pallina, non chiede se è pesante o leggera.
Una pallina in meno di sicuro non basta perché ci sarebbero solo due
"tipi" di pesate (2^(n-1) palline e 2^(n-1)-1 palline) e se tutte quelle
dello stesso tipo hanno lo stesso peso non possiamo sapere dove si trova
la pallina diversa.
Togliendo n-1 palline si possono avere pesate tutte diverse (e
sicuramente è sufficiente) però forse basta togliere 2 palline per avere
3 tipi di pesate diverse (2^n - 2 palline totali).
Mauro

> Allora si..serve qualche pallina (1 basta?) meno rispetto a 2^n-1 
Ciao ragazzi,
Effettivamente e' possibile individuare una pallina difettosa fra 15. 
Questo problema (dove le palline erano monete) fu proposto per la prima 
volta dal giapponese Kobon Fujimura, su Recreational Mathematics 
Magazine num. 9 Giugno 1962. A suo tempo avevo scritto un articoletto 
che includeva la soluzione:
http://www.uriland.it/matematica/Pesate.html
dario

 ha scritto nel messaggio 
news:4z8no.6681$%a.3...@tornado.fastwebnet.it...

Ciao Dario!
fa piacere rileggere un tuo post...
Sì, quando mi son posto il problema avevo finito per trovare questa tua 
pagina, ed è infatti da essa che ho estrapolato la mia soluzione (che tra 
l'altro era inizialmente difettosa, poi mi pare corretta).
Tu prima esponi il problema classico delle 12 palline con bilancia a due 
piatti, poi passi a quello delle 6 palline con bilancia a unico piatto e 
infine a quello da 15 da te citato di Fujimura.
Dato che a me interessava trovare "l'analogo" delle 12 palline, cioè quello 
a piatto unico, il punto era capire se conveniva usare il metodo Fujimura 
oppure se utilizzare il metodo alternativo delle disposizioni (con n-1 
palline, di cui l'ultima può venir pesata sola) che tu hai illustrato per 
quello da 6 palline.
Io ho utilizzato quest'ultimo metodo.
Comunque il punto è capire quali sono i limiti (nel senso del max numero di 
palline in N pesate) di entrambi.
Non è chiaro, per esempio (ce lo si chiedeva in questo stesso thread) quale 
dev'essere la "disomogeneità" delle varie pesate (come nr di palline 
coinvolte), in modo tale da costruire relazioni tra esse che risolvano tutte 
le ambiguità.
Tra l'altro non ho trovato in rete la soluzione del 9 palline in 3 pesate 
(sempre con piatto unico) che viene proposto al link che avevo dato io 
all'inzio del thread (vedi il problema nr. 10 in 
http://utenti.quipo.it/base5/misure/pesi.htm
)
Cosa ne pensi?
Francesco

> 
http://www.uriland.it/matematica/Pesate.html
astronomia, musica (la chitarra non è un caso vero?), entomologia e 
matematica.
Direi che abbiamo un bel po' di passioni in comune. ;-)
Pazzesca la saletta dei rompicapo, io che ne ho un centinaio (tutti 
autocostruiti con filo di ferro zincato, cordicelle, palline, anelli da 
tende, chiodi, bulloni, ecc... :-D ) pensavo ingenuamente di averne tanti .. 
mi ha veramente impressionato. :)
Ma il De Viribus del Pacioli l'hai passato tu allo scanner?