Newsgroup: it.hobby.enigmi
Titolo: Pesare con il dinamometro

Propongo una interessante variante del classico gioco delle pesate.
 
Si dispone di 26 lingotti apparentemente identici. In realtà 25 di questi hanno uguale peso mentre uno pesa differentemente dagli altri.
Utilizzando una bilancia di precisione a molla (tipo bilancia pesapersone) occorre individuare il lingotto "intruso".
 
Al minimo, quante pesate sono necessarie?
Come si procede?




 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 
Non credo proprio si possa fare in meno di 5 pesate (ogni pesata esclude 
"nel peggiore dei casi" met� dei lingotti), e ho il sospetto che 5 
pesate sia comunque la risposta esatta.
Per� io mi fermo ad un metodo in 6 pesate (che funziona fino a 32 lingotti):
Peso 3 gruppi da 8: almeno due gruppi saranno uguali, cos� trovo il peso 
standard dei lingotti e individuo il gruppo dove si trova il lingotto 
diverso.
Peso 4 lingotti da questo gruppo e vedo se l'intruso � tra questi, o 
negli altri 4 (ormai so il peso esatto).
Peso 2 lingotti, stesso ragionamento.
Peso un lingotto, stesso ragionamento.
 
bye
-- 
Paolo Lucchesi - p...@NOSPAMpaololucchesi.it

 Paolo Lucchesi
 
Nella tua risposta indichi 3 gruppi da 8, ma probabilmente intendi 8, 9, 9.
 
Io ho seguito un procedimento leggermente diverso ma con esiti analoghi (risolvo entro le 6 pesate).
 
Non credo proprio si possa risolvere in 5 pesate come tu ipotizzi... ma non si sa mai :-))
 
ciao

 Non credo proprio si possa risolvere in 5 pesate come tu ipotizzi... ma non si sa mai :-))
 
Continuiamo a rimuginarci sopra.


Giusto per confrontarsi posto la mia soluzione:
 
Indico con G1, ..., G8, otto gruppi da 3 lingotti e con G9 un gruppo da 2 lingotti.
 
Pesata 1:
========
  Peso contemporaneamente G1+G2+G3
  M1 è il valore medio risultante (pesata/9)
 
Pesata 2:
========
   Peso contemporanemanete  G7+G8+G9
   M2 è il valore medio risultante (pesata/8)
 
Se M1=M2 il lingotto intruso  è tra i 9 restanti ed il gioco è notevolmente semplificato.
Analizzo allora il caso più interessante M1<M2 (analogo a M1>M2)
In questo caso M1 oppure M2 corrispondono al peso del lingotto "tipo"
 
Pesata 3:
========
   Peso contemporaneamente G1+G2+G7
   M3 è il valore medio risultante (pesata/9)
 
Se M3=M2  G3 contiene l'intruso e quest'ultimo è più leggero
Se M3<>M1 AND M3<>M2  G7 contiene l'intruso che è più pesante
   (Notare che se G7 contiene l'intruso risulterà:
    Media(G1+G2+G7)<>Media(G7+G8+G9) perche' G9 e' di due soli lingotti)
Se M3=M1   vi sono due possibilità:
          il gruppo G1+G2 contiene l'intruso che è più leggero
          il gruppo G8+G9 contiene l'intruso che è più pesante
 
Analizzo il terzo caso che è più complesso
 
Pesata 4:
========
   Peso contemporaneamente G1+G8
   M4 è il valore medio risultante (pesata/6)
 
Se M4=M1 il gruppo G9 contiene l'intruso che è più pesante
Se M4=M2 il gruppo G2 contiene l'intruso che è più leggero
Se M4<>M1 AND M4<>M2  l'intruso sarà in G1 (se più leggero) in G8 (se più pesante)
 
Analizzo quest'ultimo caso più complesso
 
Pesata 5:
========
   Peso contemporaneamnete i seguenti tre lingotti G1(1)+G1(2)+G8(1)
   M5 è il valore medio risultante (pesata/3)
 
Se M5=M1 l'intruso è G8(2) o G8(3) ed è più pesante 
   (Non può essere G1(3) perché se lo fosse dovrebbe essere M1<M5)
Se M5=M2 l'intruso è G1(3) ed è più leggero
   (Non possono essere G8(2) o G8(3) perché se lo fosse dovrebbe essere M2>M5)
Se M5<>M1 and M5<>M2 l'intruso è G1(1), G1(2) (più leggero) o G8(1) (più pesante) 
 
Analizzo quest'ultimo caso
 
Pesata 6:
========
   Peso contemporaneamente G1(1)+G8(1)
   M6 è il valore medio risultante (pesata/2)
 
Se M6<M1 G1(1) è l'intruso ed è più leggero
Se M6>M2 G8(1) è l'intruso ed è più pesante
Se M6=M5 G1(2) è l'intruso ed è più leggero
 
 

Io faccio 2 gruppi da 13 ,con le prime due pesate individuo quello piu' pesante, lo divido in 2 gruppi da 6 lasciando un lingotto da parte , se le seconde due pesate mi danno un peso uguale il lingotto piu' pesante e' quello che ho messo da parte altrimenti  prendo il gruppo da 6 che pesa di piu' e lo divido in due gruppi da 3 con le terze due pesate individuo quello piu' pesante, dei tre lingotti rimanenti 1 lo metto da parte e faccio le due pesate per gli altri due, anche qui se il peso e' uguale il lingotto messo da parte e' quello piu' pesante altrimenti quello dei due che da' il peso maggiore. Ricapitolando 2 pesate da 13, 2 pesate da 6, 2 pesate da 3 e due pesate da 1, totale 8 pesate e con un po' di fortuna anche con 4 se quando faccio la pesata dei due gruppi da sei ho la fortuna di mettere da parte il lingotto piu' pesante.

 piu' pesante [...]
 
Attento, nessuno ti dice che il lingotto falso � pi� pesante; potrebbe 
essere anche pi� leggero. E non sai nemmeno di quanto.
 
(Comunque non trovo - per ora - una soluzione in 5 pesate nemmeno con 
l'assunzione che il falso sia pi� pesante; con 5 pesate posso trovarlo 
tra 24 lingotti).


 bye
 
Se si sa che e' piu' pesante dovrebbe essere possibile trovarlo tra 32 (5 bit)
basta numerare da 0 a 31 passare alla numerazione binaria e pesare insieme
quelli che hanno 1 al primo poi al secondo etc posto cioe:
 
1) 1 3 5 7  9 11 13 15   .... 25 27 29 31
2) 2 3 6 7 10 11 14 15   .... 26 27 30 31
3) 4 5 6 7 12 13 14 15   .... 28 29 30 31
4) 8 -> 15    24 -> 31
5) 16 -> 31
 
e poi prendere le piu' pesanti e ricostruire il numero (basta sommare il primo
termine delle righe appropriate).
 
Il problema e' se sono tutte uguali nel qual caso  non e' possibile sapere se 
e' 31 (sempre presente) o 0 ( sempre assente), a meno che non si sappia 
anche il peso giusto del lingotto.
 
Ma la stessa procedura puo' essere applicata a 31 lingotti ed in questo caso 
si puo' trovare il piu' pesante.
 
Ciao, 
 
Gorgo

Complimenti a Paolo che se l'è sbrigata in quattro e quattr'otto ma mi è piaciuto tantissimo anche il ragionamento di Gorgo.
Mi sono divertito a fare un modellino con Excel che (ovviamente) da conferma sperimentalmente di quanto detto nel post.
 
Ciao
Arturo

Come si procede?
 
Ciao,
avevo gi� postato un problema analogo, circa tre anni fa, legato al pi� 
clssico 12 palline in 4 pesate, qui:
https://groups.google.com/forum/#!topic/it.hobby.enigmi/iVlqCtr8jwc
 
senza peraltro giungere ad una soluzione certa.
In questo caso conviene analogamente seguire quello stesso criterio, ovvero 
effettuando una distribuzione delle prime quattro pesate che si differenzino 
al massimo relativamente ai lingotti pesati.
Per fare ci�, conviene a mio avviso suddividere i 26 lingotti in gruppi di 
due, ottenendo 13 gruppi che per semplicit� si possono elencare come A 
(lingotti 1 e 2), B (lingotti 3 e 4), C (5 e 6), ...., O (lingotti 25 e 26).
A questo punto occorre elaborare uno schema di almeno 13 "colonne" a 
"correzioni di errore", come nel totocalcio.
(usare caratteri fissi)
-------------------------------------
GRUPPI -->  A B C D E F G H I L M N O
-------------------------------------
PESATE x->  0 0 0 1 1 1 1 0 0 0 1 1 1
       y->  0 0 1 0 1 0 0 1 1 0 1 1 0
       z->  0 1 0 0 0 1 0 1 0 1 1 0 1
       w->  1 0 0 0 0 0 1 0 1 1 0 1 1
-------------------------------------
 
dove x, y, z e w sono le prime quattro pesate, in cui tutti i 13 gruppi 
vengono pesati differenziati.
In particolare i gruppi pesati appaiono cos� nelle 4 pesate:
 
A --> w
B --> z
C --> y
D --> x
E --> x, y
F --> x, z
G --> x, w
H --> y, z
I --> y, w
L --> z, w
M --> x, y, z
N --> x, y, w
O --> x, z, w
 
La relazione tra le 4 pesate dovrebbe quindi essere (se tutti i lingotti 
pesassero uguale) 6x = 7y = 7z = 7w
Laddove si verifica una discrepanza, questa dovrebbe poterci dire quale 
gruppo ne � la causa.
Per esempio se si verificano i seguenti pesi:
x = 70
y = 60
z = 59
w = 60
dato che solo z risulta in difetto, l'unico gruppo che viene pesato in z � 
B, oppure si potrebbe anche dire che x, y e w sono in eccesso, e l'unico 
gruppo che risulta pesato in esse (e non in z) � N.
Per cui appare chiaro che nel gruppo B uno dei due lingotti potrebbe pesare 
di meno, oppure che nel gruppo N uno dei due potrebbe pesare di pi�.
Supponendo di voler risolvere la questione in 5 pesate (in 6 sarebbe 
banale), mi chiedo: si pu� riuscire in una sola pesata, a discriminare quale 
dei 4 lingotti � quello diverso?
 
A me pare che volendo limitare la cosa a questo esempio (che per� potrebbe 
anche non essere cos� probante) si pu� escludere che si tratti di un 
lingotto pi� pesante in N.
Infatti, detto 'a' il peso di un lingotto "normale" e 'b' il peso di quello 
diverso, si tratterebbe di risolvere il sistema:
 
13a + b = x
11a + b = y
12a = z
(dove ovviamente deve sussistere la relazione 6x = 7y), il quale a mio 
avviso non � risolvibile.
Mentre pi� plausibile �:
14a = x
12a = y
11a + b = z
sempre dato 6x = 7y
 
Perci� se tutto questo � vero la quinta pesata non dovrebbe che cercare 
quale dei due lingotti in B � pi� leggero, e a quel punto basta prenderne 
uno dei due a caso e pesarlo, e se il suo peso moltiplicato 12 � y allora il 
pi� leggero sar� l'altro (e viceversa).
Ciao
Francesco 
 
 
 
--- news://
freenews.netfront.net/
 - complaints: 
ne...@netfront.net
 ---

conferma sperimentalmente di quanto detto nel post.
 
 
Quindi scusa mi pare che le soluzioni di Paolo e Gorgo siano da sei pesate: 
si pu� fare in sei pesate al minimo? Confermi? 


 --- news://
freenews.netfront.net/
 - complaints: 
ne...@netfront.net
 ---
 
 
No sono in cinque, ma devi sapere il peso del lingotto normale ed allora si
puo' fare con 32 oppure se e' piu pesante o piu' leggero e si puo' con 31.
 
Ma, se non mi sbaglio, il secondo caso porta ad una soluzione in sei.
 
La procedura descritta (con 31 e cinque pesate) da un risultato se si fa
l'ipotesi che il lingotto e' piu' pesante ed un altro se e' piu' leggero
quindi una sesta pesata (uno dei due con uno sicuramente normale) puo'
risolvere il problema e trovare il lingotto farlocco.
 
Ciao,
      Gorgo

      Gorgo 


 
 
Direi di si.
 
Ciao,
      Gorgo
 

 si pu� fare in sei pesate al minimo? Confermi? 
 
Fare delle affermazione in questo NG è una cosa (per me) sempre molto pericolosa...
perciò ritratto tutto ciò che ho detto in questo thread 
(e quindi, implicitamente, ritratto anche di aver ritrattato :-)))
 
Ciò detto:
la migliore soluzione che avevo trovato quando ho postato questo gioco era in 6 mosse e pertanto mi sembrava cosa buona e giusta far giungere i miei apprezzamenti a chi aveva raggiunto in modo elegante questa soluzione.
 
Poi sei arrivato tu che hai modificato i pesi e le misure.
Hai insinuato il dubbio postando una soluzione che in realtà è ineccepibile
(nota il tono categorico della mia affermazione che posso permettermi grazie al fatto di aver anticipatamente già ritrattato tutto :-).
Ho cercato un controesempio (che però non può esistere) per non dover ritrattare, ma, per restare in tema, ritratto anche questo.
 
Ciao e grazie per il tuo contributo
 
Arturo

Arturo 
 
 
 


 lingotto pi� pesante in N.
 
In effetti questo si pu� fare sempre, se la bilancia ha una precisione
sufficiente. 
 
Se a � il peso di un lingotto normale e d l'eccesso di peso (positivo o
negativo) del lingotto anomalo, si pu� impostare un sistema di equazioni
per ognuno dei 13 possibili casi. Ad es., se il lingotto anomalo � nel
gruppo G, il sistema �:
 
x = 14a+d
y = 12a
z = 12a
w = 12a+d
 
Ho controllato con Mathematica che in tutti i casi uno solo dei sistemi
ha soluzione, quindi in un colpo solo questo ci dice quanto valgono a e
d e qual � il gruppo a cui appartiene il lingotto anomalo.
 
La cosa funziona anche perch� in nessun caso il lingotto anomalo non sta
in x e sta invece in y, z e w: se cos� non fosse avremmo due possibili
soluzioni nel caso in cui y=z=w.
 
Inoltre � cruciale il fatto che il numero di lingotti pesati in x sia
diverso che nelle altre pesate. Una bella soluzione.
 
M.
 
-- 
Per rispondermi via e-mail togli l'ovvio.

chiarir� qualcun altro mi sa tanto che rimarr� col dubbio :( 
 
Per affermare che la soluzione che hai proposto (in 5 mosse) è corretta ho ragionato nel seguente modo:
 
Sia PMi il peso medio della pesata i-ma.
Quindi: 
  PM1 = (pesata 1/7)
  PM2 = (pesata 2/6)
  ecc.
 
Si osserva che se il lingotto falso è presente nella pesata 1 allora PM1 è diverso da PM2, PM3 e PM4.
Infatti, indicando con PMk indifferentemente uno dei valori PM2, PM3 o PM4, si ha:
   PM1=PMk => 1/7(6V+1F) = 1/6(5V+1F) => 36V+6F =35V+7F=>V=F
In altri temini:
   PM1=PMk => pesata 1 non include il lingotto falso
 
Analizziamo ora i possibili casi:
 
PM1=x
PM2=PM3=PM4=y
Banalmente il lingotto falso è nella pesata 1.
Si osservi che lo schema non prevede che lo stesso lingotto sia pesato in tutte e tre le pesate successive alla prima.
 
PM1=PMk=x
PMi=PMj=y
poiché PM1=PMk => la pesata 1 non può includere il lingotto falso 
ovviamente PMi e PMj includono il lingotto falso
 
PM1=x
PMi=PMj=y
PMk=z
(con x<>y<>z)
e' questo il caso più complesso perché si presta ad una doppia interpretazione.
Cominciamo con l'osservare che PM1 diverso da tutti gli altri implica che la prima pesata include il lingotto falso.
Il dubbio è:
   il lingotto falso è nelle pesate 1-ma e k-ma
oppure
   il lingotto falso è nelle pesate 1-ma, i-ma e j-ma  ?
 
Supponiamo inizialmente che il lingotto falso sia nelle pesate 1-ma, i-ma e j-ma.
Si ha:
    1/7(6V+1F)=x  (x = PM1)
    1/6(5V+1F)=y  (y = PMi = PMj)
    V=z           (z = PMk)
    con V<>F
 
    da cui:
    (dalla prima relazione) 6/7z+1/7F=x =>  F=7x-6z 
    ma contemporaneamente è anche
    1/6(5z + 7x-6z)=y => 5z+7x-6z=6y => 7x=6y+z => x=6/7y+1/7z
 
Supponiamo ora che il lingotto falso sia nelle pesate 1-ma e k-ma.
Si ha:
    1/7(6V+1F)=x    (x = PM1)
    V=y             (y = PMi = PMj)
    1/6(5V+1F)=z    (z = PMk)
 
    da cui (per simmetria):
    x=6/7z+1/7y
 
Infine dimostriamo che le due relazioni non possono essere contemporaneamente vere.
   6/7z+1/7y=6/7y+1/7z => 6z+y=6y+z => 5z=5y => z=y (che è contro l'ipotesi)
 
In conclusione il caso in esame si discrimina analizzando la relazione che esiste tra i pesi rilevati nelle pesate:
  PM1 = 6/7 PMi + 1/7 PMk => lingotto falso nelle pesate 1-ma, i-ma e j-ma (PMi = PMj)
  PM1 = 6/7 PMk + 1/7 PMi => lingotto falso nelle pesate 1-ma e k-ma (PMi = PMj)
 
 
Ciao
Arturo

Arturo
 
Ho fatto un po' di fatica all'inizio, ma ti ringrazio per questa esauriente 
dimostrazione, molto ben fatta...
Francesco 


 Per rispondermi via e-mail togli l'ovvio. 
 
 
 


 anomalo.
 
Certo, non credo proprio che sia possibile trovare il lingotto in 4
pesate. Ma gi� la soluzione in 5 pesate � tutt'altro che ovvia, come
abbiamo visto.
