Monete false: una variante

[luciano]

Conoscevo ed ho rivisto qui il problema delle 12 monete di cui una
falsa; quello che segue credo non sia mai stato postato (perlomento
non si trova nelle faq):
si hanno a disposizione 13 monete, fra le quali, FORSE, e' presente
una moneta falsa (non e' noto se piu' pesante o piu' leggera); avendo
inoltre a disposizione una moneta campione, individuare con tre pesate
su di una bilancia a due piatti, se esiste la moneta falsa e se e'
piu' pesante o piu' leggera.

[Paolo Licheri]

luciano ha scritto nel messaggio <3657d046...@news.interbusiness.it>...

E' un bel problema, e credo che meriti un commento:

Inizialmente ho 27 possibilita' differenti: 13 possibili monete piu'
pesanti, 13 possibili piu' leggere ed una possibilita' che siano tutte
buone.
Ad ogni pesata, con tre possibili esiti, le possibilita' si riducono ad un
terzo, cosi' dopo la prima saranno 9 possibilita' residue, poi 3 ed infine
dopo la terza pesata una sola possibilita'.
E' facile vedere che, se per la prima pesata utilizzo 4+4 (o meno) monete
"sospette", in caso di equilibrio tra i due piatti rimango bloccato: infatti
le cinque monete non utilizzate danno 5+5+1=11 possibilita' residue, contro
le 9 ammmissibili.
Se invece utilizzo 5+5 (o piu') monete sospette, rimango bloccato in caso di
NON equilibrio, avendo 10 possibilita' residue (5 possibili piu' pesanti e
cinque possibili piu' leggere).
Appare quindi obbligata la scelta di utilizzare per la prima pesata nove
monete sospette (5+4) integrate dalla moneta campione.

Provo ora a dare la soluzione descrivendola come un diagramma di flusso:

Siano 1,2, ... 13 le monete sospette, e 0 la moneta campione sicuramente
buona.

A)
Prima pesata: (1,2,3,4,5)-^-(6,7,8,9,0)
Se
(1,2,3,4,5)=(6,7,8,9,0) vai al passo B
(1,2,3,4,5)>(6,7,8,9,0) vai al passo E
(1,2,3,4,5)<(6,7,8,9,0) caso simmetrico al precedente, tralascio lo
sviluppo.

B)
Informazioni disponibili a questo punto:
Le monete 1...9 sono buone, l'eventuale falsa e' tra 10,11,12,13
Seconda pesata: (10,11,12)-^-(1,2,3)
Se
(10,11,12)=(1,2,3) vai al passo C)
(10,11,12)>(1,2,3) vai al passo D)
(10,11,12)<(1,2,3) caso simmetrico al precedente

C)
Informazioni disponibili:
10,11,12 sono buone, l'eventuale falsa e' 13
Terza pesata: (13)-^-(0) individuo se 13 e' piu' leggera, buona o piu'
pesante
Vai al passo Z

D)
Informazioni disponibili:
La falsa, piu' pesante, e' 10,11 o 12
Terza pesata: (10)-^-(11)
Se una delle due e' piu' pesante, e' falsa
Se 10=11, la falsa piu' pesante e' 12
Vai al passo Z

E)
Informazioni disponibili:
Esiste certamente una falsa, che puo' essere 1...5 piu' pesante oppure 6...9
piu' leggera; 10...13 sono buone.
Seconda pesata: (4,6,7)-^-(5,8,9)
Se
(4,6,7)=(5,8,9) vai al passo F
(4,6,7)>(5,8,9) vai al passo G
(4,6,7)>(5,8,9) caso simmetrico al precedente

F)
Informazioni disponibili:
4,5,6,7,8,9 sono buone; la falsa puo' essere 1,2 o 3 piu' pesante.
Terza pesata: (1)-^-(2)
Se una delle due e' piu' pesante, e' falsa
Se 1=2 la falsa piu' pesante e' 3
Vai al passo Z

G)
Informazioni disponibili:
La falsa puo' essere 4 piu' pesante oppure 8 o 9 piu' leggera
Terza pesata: (8)-^-(9)
Se una delle due e' piu' leggera, e' falsa
Se 8=9, la falsa piu' pesante e' 4
Vai al passo Z

Z)
ciao
paolo

[Dario Uri]

Paolo Licheri wrote:
>
> luciano ha scritto nel messaggio <3657d046...@news.interbusiness.it>...
> >Conoscevo ed ho rivisto qui il problema delle 12 monete di cui una
> >falsa; quello che segue credo non sia mai stato postato (perlomento
> >non si trova nelle faq):
> >si hanno a disposizione 13 monete, fra le quali, FORSE, e' presente
> >una moneta falsa (non e' noto se piu' pesante o piu' leggera); avendo
> >inoltre a disposizione una moneta campione, individuare con tre pesate
> >su di una bilancia a due piatti, se esiste la moneta falsa e se e'
> >piu' pesante o piu' leggera.
>
> E' un bel problema, e credo che meriti un commento:
>
> Inizialmente ho 27 possibilita' differenti: 13 possibili monete piu'
> pesanti, 13 possibili piu' leggere ed una possibilita' che siano tutte
> buone.

Difatti e' un problema che possiamo definire "perfetto", le possibilita'
eguagliano il numero di discriminazioni con 3 pesate.
Pero' si puo' usare la stessa sol. gia' accennata per le 12 palle.
Abbandonando la sol. piu' ovvia di determinare la 2° e 3° pesata in
funzione delle precedenti, avevamo gia' accennato su come stabilire a
priori le 3 pesate in modo che a ognuno dei 24 possibili risultati
corrispondesse una ed una sola pallina.
Rimanendo alle 12 palle con 1 difettosa, vediamo come si fa:

Poniamo come risultato di una pesata
- equilibrio.
/ scende il piatto di sinistra.
\ scende il piatto di destra.
a) Tutte le palline devono essere pesate almeno 1 volta.
b) Occorrono 24 risultati differenti, perche' ogni pallina puo' pesare +
o -.
c) Dei 27 possibili risultati delle 3 pesate, --- e' impossibile,
perche' non sarebbe presente la pallina difettosa, contrariamente
all'enunciato.
d) Cosi' posso decidere di eliminare altri 2 risultati, scelgo /// e
\\\, (ma e' possibile eliminare qualunque coppia). Per ottenerlo mi
basta non pesare una
stessa pallina per 3 volte sullo stesso piatto.

Supponiamo ora di dividere le nostre palline in 4 gruppi di 3 ciascuno:
Rappresento le palline con le lettere A,B,C D,E,F G,H,K X,Y,Z.
Devo distribuire le palline di ciascun gruppo in modo diverso per ogni
pesata, lo posso fare con l'aiuto di uno schemino:

Fuori Piatto Piatto
bilancia sinistro destro
ABC 0 1 2
DEF 1 2 0
GHK 2 0 1
XYZ 1 1 1

Lo schemino ci indica che per ogni pesata le palline ABC non devono
essere escluse, una sara' sempre sul piatto di sinistra e due sul piatto
di destra, per la considerazione d) la pallina sul piatto di sinistra
non puo' essere sempre la stessa. Lo stesso per gli altri tre gruppi
cioe',
del gruppo DEF, una sara' sempre fuori bilancia e due sul piatto di
sinistra ecc..
Trattando le palline ciclicamente, si possono fare le tre pesate
rispettando le distribuzioni appena viste:

Fuori Piatto Piatto
bilancia sinistro destro

Prima DHKX AEFZ BCGY
Seconda EKGY BFDX CAHZ
Terza FGHZ CDEY ABKX

Possiamo vedere che, se nessuna pesata e' bilanciata, la pallina
difettosa e' stata pesata 3 volte, ed e' nel set ABC. Se una sola pesata
e' in equilibrio e nelle altre due e' sceso lo stesso piatto, deve
essere nel set DEF. Con 2 pesate in equilibrio su tre, la pallina sara'
nel set GHK, ed infine con una sola pesata in equilibrio e nelle altre
due e' sceso prima un piatto poi l'altro deve eseere nel set XYZ.
E' facile vedere che ad ogni possibile risultato delle tre pesate
corrisponde una ed una sola pallina.
Es: -// = D+
-/- = H-
/-\ = Y- ecc...

Con questa distribuzione abbiamo visto che non potremo ottenere i 3
casi:
---, ///, \\\.

Ora questi li uso per risolvere la variante proposta da Luciano,
semplicemente aggiungendo per le 3 pesate appena viste, la palla
campione, diciamo a destra e la 13esima a sinistra.
E' evidente che se la 13esima palla e' regolare e una delle 12 A-Z e'
difettosa,non cambia niente dal prob. precedente, altrimenti si verifica
uno dei 3 casi appena visti.
dario

[Enrico 2]

Dario Uri <MD4...@mclink.it> scritto nell'articolo
<365BF82C...@mclink.it>...

> Paolo Licheri wrote:
> >
> > luciano ha scritto nel messaggio
<3657d046...@news.interbusiness.it>...

Chapeau

enrico