Newsgroup: it.hobby.enigmi
Titolo: Con tre pesate

Ne abbiamo gia' trattati tanti di problemi con monete o palline da
pesare. Questo si aggiunge alla collezione.
Date 6 palline di cui una di peso differente, individuarla con 3 pesate.
Naturalmente non si conosce ne' il peso delle palline regolari ne' il
peso di quella difettosa. 
NB La bilancia e' quella elettronica che restituisce il peso esatto, non
quella a doppio piatto.
:) dario

Dario Uri wrote:

scusa, Dario ...... singolo piatto elettronico ?
Massimo


Siano A,B,...F le 6 palline.
1^ pesata (A,B)
2^ pesata (C,D)
Abbiamo 2 casi:
1) le pesate danno lo stesso peso X. La palline diversa e' tra le rimanenti.
Pesiamo E. se E pesa X/2, quella diversa e' F, altrimenti E e' la pallina
diversa;
2) La prima pesata da X, la seconda da Y. Suppongo per semplificare che X < Y.
Il caso opposto si risolve per simmetria.
Allora se la pallina diversa e' tra A e B, pesa X-Y/2; altrimenti pesa Y-X/2
3^ pesata (A,C,E)
In questo caso ho:
Peso risultante            Pallina diversa
------------------------------------------
X+Y/2                            A
3Y/2                             B
Y+X/2                            C
3X/2                             D
Divertente!!!
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/
       Search, Read, Discuss, or Start Your Own    


Pero' e' diverso... Mai visto prima.
La soluzione di Enzo mi sembra corretta.
Io avevo pensato di pesare prima 4 palline, poi 2 delle 4. Con 2 pesate
arrivo alla
stessa situazione.
Chi e' l'autore?
Come cresce il numero di palline al crescere delle pesate?
Qui sotto la mia idea....
(SPOILER)
...
...
Mi sembra che con n pesate si trovi la pallina tra 3*2^(n-2).
Divido le palline in 6 gruppi (A..F)
Peso come nella soluzione, a gruppi.
Con 3 pesate determino in quale gruppo e' e quanto pesa una pallina normale.
Le successive pesate mi servono per dividere ogni volta a meta'  il gruppo
nel quale si trova sicuramente la pallina cercata
(ogni volta ne peso meta' e so quanto dovrebbero pesare: se il peso e' OK,
la pallina sta tra quelle non pesate, altrimenti tra quelle pesate).
Quindi con n pesate la trovo tra 6*2^(n-3)=3*2^(n-2).
In un caso, pero', non ne scopro il peso.
Se voglio essere sicuro di determinarne il peso, il massimo mi sembra
3*2^(n-2)-1.
Come va?
Non mi sembra possibile far di meglio, ma non mi viene in mente una
dimostrazione.
Ciao
Mauro Fiorentini

 Divertente!!!
Fin qui tutto bene. Ho postato come assaggio solo la meta' del vero
problema.
Ecco un'ulteriore richiesta che rende il problema molto piu' divertente
!!!
Date 6 palline di cui una di peso differente, individuarla con 3 pesate,
determinando anche l'esatto peso sia delle palline regolari sia di
quella difettosa.
:) dario

,

Pare non ci sia soluzione


Pare non ci sia soluzione
Mi sembra (ma non ne sono sicuro) che non ci sia soluzione se si vogliono
predeterminare le pesate. Invece e' possibile se si decide la terza pesata
in base al risultato delle prime due.
Siano ABCDEF le palline, sia P il peso di ciascuna delle buone e Q il peso
di quella anomala.
Prime due pesate:
G1 = A+B+C+D
G2 = A+B+E
per comodita' ragiono sulle medie
X = G1/4
Y = G2/3
se X=Y la pallina anomala sara' F, e la peso da sola con la pesata ancora a
disposizione, mentre il peso buono sara' P=X=Y.
Se invece X<>Y, la pallina anomala sara' tra le prime cinque ed F e'
sicuramente buona. Allora, terza pesata:
G3 = A+C
media Z = G3/2
Z potra' essere uguale a X, a Y o a nessuna delle due, in funzione di quale
sia la pallina anomala, secondo lo schema che segue:
Anomala Z=X Z=Y
A       NO  NO
B       NO  NO
C       NO  NO
D       NO  SI
E       SI  NO
Caso SI,NO
L'anomala e' necessariamente E. Il peso buono e' P=X=Z, quello cattivo
Q=G2-2*P
Caso NO,SI
L'anomala e' necessariamente D. Il peso buono e' P=Y=Z, quello cattivo
Q=G1-3*P
Caso NO,NO
In questo caso l'anomala e' una delle prime tre (A,B,C)
mentre le altre sono sicuramente buone, quindi D=E=P.
Posso allora scrivere i risultati delle pesate nel modo seguente:
G1=A+B+C+P
G2=A+B+P
G3=A+C
da cui posso ricavare i pesi di due palline:
C=G1-G2
A=G3-C
considero due sottocasi:
A=C
sono entrambe buone, l'anomala e' B, il cui peso vale Q=G1-3*P
A<>C
una delle due e' anomala, B e' buona. Quindi
G1=A+C+2*P
ricavo P e verifico quale, tra A e C, sia buona e quale anomala.
SEOO
ciao
paolo

 Pare non ci sia soluzione
Ti assicuro che si puo' fare.
Non demordere!
:)dario



-----------== Posted via Deja News, The Discussion Network ==----------


 quella a doppio piatto.
--== Sent via Deja.com 
http://www.deja.com/
 ==--
---Share what you know. Learn what you don't.---

Altra soluzione sempre dal mio collega Alexis (con due occhiaie cosi'
per non averci dormito sopra)
    A B C D E F G H I L M N O P Q
x1  - - - - - - - -
x2          - - - - - - - -
if(x1==x2)
{
    A B C D E F G H I L M N O P Q
x1  - - - - - - - -
x2          - - - - - - - -
x3              - - -       - -
x4            - -             - -
  bad = {E;F;G;H;O;P;Q}
  elimino E;F;G;H una per volta dall'insieme bad con il seguente metodo:
  per scoprire che la pallina Y e' good, trovo due insiemi di palline
di
   cardinalita' diversa, in cui Y non appartiene a nessuno dei due
insiemi
   S1 e S2, e bad-{Y} incluso in S1 | S2
   if peso(S1)/|S1| == peso(S2)/|S2|
	bad-{Y} e' good => Y bad
   else
      bad=bad-{Y} => Y good
   Ecco dunque gli insiemi, per ogni Y:
   Y=E S1=x3 S2=x4 (x3/5==x4/4)
   Y=F S1=x1-x4 S2=x3 ((x1-x4)/4==x3/5)
   Y=G S1=x2-x3 S2=x3-x4 ((x2-x3)/3==x3-x4)
   Y=H S1=x1-x3 S2=x4 ((x1-x3)/3==x4/4)
  a questo punto bad={13;14;15}
  good=x1/8
  if(x3==5*good) bad=Q;
  else if(x4==4*good) bad=O;
  else bad=P;
}
else
{
    A B C D E F G H I L M N O P Q
x1  - - - - - - - -
x2          - - - - - - - -
x3      - -         - -
if(x3/4==x1/8)
{
  bad={M;N} banale
}
else
{
  bad={A;B;C;D;I;L}
  if(x3/4==x2/8) bad={A;B} banale
  else
  {
    bad={C;D;I;L}
    good=(x1+x2-x3)/12;
    if(x1==8*good) bad={I;L} banale
    else bad={C;D} banale


 dalle altre.
Allora, con calma perche' non e' del tutto semplice.
Etichettiamo le monete da 1 a 15 e le 4 pesate A,B,C,D.
Procediamo con le prime due pesate.
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"). In questo caso la
difettosa e' fra le monete pesate 2 volte oppure le NON pesate, dobbiamo
indagare fra: 1,2,3,12,13,14,15 e dovendo fare in modo che ogni moneta
sospetta sia distribuita in modo differente da ciascuna altra per essere
individuata, possiamo procedere con:
C = 2,3,14,15.
D = 1,3,13,15.
Le monete sospette appaiono cosi' nelle varie pesate:
MONETA    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 problema? purtroppo no! Facciamo un esempio.
I risultati delle 4 pesate sono 81,81,40,40.(diciamo grammi)
Se le monete fossero tutte autentiche i risultati delle prime due pesate
(8 monete) sarebbero il doppio delle ultime due(4 monete). Qui vediamo
che c'e' un eccesso di 1 sulle prime due pesate oppure un difetto di 0.5
sulle ultime due. Nel primo caso avremmo 10g per le monete autentiche e
11g per moneta num.12, unica ad apparire nelle pesate A,B oppure 8.1g
per le autentiche e 7.6g per la moneta num.3, unica ad apparire nelle
pesate C,D. Come fare per evitare questa ambiguita'?
Il trucco sta nell'aggiungere una o due monete sicuramente autentiche in
C o in D.
Noi decidiamo di aggiungere 2 monete in C, che diventa: C = 2,3,14,15 +
8,9.
A questo punto possiamo fare uno schemino che ci da per ogni moneta
sospetta lo scompenso ottenuto confrontando le pesate 4C-6D e B-2D che
sarebbero =0 con monete tutte uguali.
Monete  1  2  3  12  13  14  15
4C-6D  -6  4 -2   0  -6   4  -2
B-2D   -1  0 -2   1  -1   1  -1     (Tab1)
In questo modo la moneta diversa puo' essere individuata
inequivocabilmente. es:
A=81, B=81, C=60, D=40, non da adito a dubbi
4C-6D = 240-240 = 0
B-2D  =  81- 80 = 1   
E' la moneta num.12 piu' pesante di 1.
Un'altro es: A=79.5, B=79.5, C=59.5, D=40
4C-6D = 238-240 = -2
B-2D  = 79.5-80 = -0.5  i due risultati stanno 4/1, cosi' e' la moneta
num.14 in A,B,C. In D sono tutte autentiche percio' 40/4 = 10g per le
autentiche e 9.5 per la num.14.
Il problema in questo modo e' completamente risolto.
Nel caso che le due prime pesate siano differenti, il sistema e' del
tutto analogo, le sospette sono quelle pesate una volta sola:
4,5,6,7,8,9,10,11. Procediamo con:
C = 6,7,10,11 + 3,14
D = 5,7,9,11
La distribuzione diventa:
MONETA  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
Potete vedere che i risultati delle pesate 4C-6D e B-2D sono identici a
quelli ottenuti nel caso precedente, (Tab1) la corrispondenza per le
monete 1,2,3,12,13,14,15 e' rispettivamente 9,10,11,4,5,6,7 c'e' in piu'
la moneta num 8, che e' presente solo nella pesata A, e da' 4C-6D = B-2D
= 0.
Spero sia tutto chiaro.
:)dario