Newsgroup: it.hobby.enigmi
Titolo: [REQ] Problema di pesate

A scanso di equivoci, e visto che proprio io gestisco le FAQ, vorrei
sapere se questo problema e' gia' stato postato, e se si', qual e' la
soluzione.
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?
Secondo chi me l'ha proposto, bastano, ma io non sono riuscito a trovare
il metodo.
Qualcuno puo' darmi una mano, o dimostrare l'impossibilita' di farlo?
Grazie
Mariano


Con la consapevolezza di fare qualche errore per la fretta,
posto la soluzione.
SPOILER
.
.
.
.
.
.
.
.
.
.
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' Go H: vai 5)
piatto uno: 6)
piatto due : 7)
3) peso ABD CIL
uguali: e' FoE: 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.
Ciao.
sandro.san


Visto che si riesce con 12, si dovrebbe riuscire anche con 10.
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.
Ciao
Giorgio

 ha scritto nel messaggio
news:39BEBA1E...@geocities.com...

Se non ricordo male avevamo risolto anche il problema con 12 palline e tre
pesate. Purtroppo non ho piu' la soluzione.
Con 10 palline ho una soluzione che permette di isolare quella differente ed
anche di stabilire se e' piu' leggera o piu' pesante.
spoiler
v
v
v
v
v
v
v
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
ciao
paolo

Rilancio con 13 (e' la mia ultima offerta!!)
.
.
.
.
.
.
.
.
.
.
.
.
Spoiler
Giustamente Il sig. Vecchi mi ha dato una lezione di
sintetismo :-) ma io faccio il programmatore e percio':
(vi riparmio i GOTO e gli  ENDIF)
ABCD EFGH sono differenti si veda "giorgio".
se sono uguali e' ILMNO
peso IL Mx
se sono uguali e' N o O
se sono diversi
peso IM xx
e vado avanti..
HOVINTOQUALCHECCOSA?
[Quando ero piu' piccolo e meno
rincoglionito mi pare che trovai un limite
superiore piu' alto. Dico stupidaggini?]
sandrosan
sandro.san

,

SPOILER
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
V
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.
WOOOOOWWW!! Mi e' proprio piaciuto!
Grazie per il bellissimo indovinello Mariano.
Ciao a tutti, Barabbino.
Sent via Deja.com 
http://www.deja.com/
Before you buy.

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?
sandro.san



Ma scusa ....
ci si riesce con 12 palline, per cui ci si riesce anche con 10.
Basta iniziare con una pesata 4-4, come del resto segnalato dalle tue
FAQ, alla domanda numero 11 ... :-)
Ciao!
Maurizio Mascheroni
===================================================
Maurizio Mascheroni           
mask...@maskeret.com
---------------------------------------------------
La Mecca - Chess Encyclopedia:
 
http://www.maskeret.com/mecca
Blip - Blitz Press Release (News from the world):
 
http://www.maskeret.com/blip
Chess in Italy and much more:
 
http://www.maskeret.com/micio
L'Italia Scacchistica, chess magazine:
 
http://www.maskeret.com/italiascacchistica
Franco Romagnoli, chess shop:
 
http://www.maskeret.com/romagnoli
===================================================

 wrote in message
8pnig1$92b$1...@suite03.caspur.it...

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.
Ciao
Giorgio
P.S. sandro.san, perché mi chiami "sig. Vecchi"? :-) Tra l'altro sono
programmatore anch'io!!! :-)

 programmatore anch'io!!! :-)
Eccesso colposo di reverenza;-) Mi scuso.
sandro.san

 Giorgio
Ciao,
Giovanni Rana


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.
Ciao
Giorgio

 formula. 
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.
ciao :) dario

 ciao :) dario
... 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.
Ciao
Giorgio