Le 6 monete (il Remake)

[giobimbo]

Ho 6 monete, una è falsa, quella falsa ha un peso diverso da quelle vere ma non si sa se pesi di più o di meno. Come posso determinare quale sia la moneta falsa e se pesi di più o di meno con tre pesate su una bilancia per oro che dia il valore preciso delle monete?

Questo chiedeva il vecchio problema di Paolo32 un anno e mezzo fa.

Abbiamo un insieme ordinato (a, b. c, d, e, f) di 6 monete di cui una falsa il cui peso vale F mentre le altre 5 pesano V ciascuna. Facciamo un esempio numerico, più facile da seguire, ponendo V=2 e F=3. Ci sono 6 casi possibili:
(C1) (2,2,2,2,2,3)
(C2) (2,2,2,2,3,2)
(C3) (2,2,2,3,2,2)
(C4) (2,2,3,2,2,2)
(C5) (2,3,2,2,2,2)
(C6) (3,2,2,2,2,2).

Definiamo le tre pesate come:
P1=a+b+c
P2=b+e+f
P3=c+d+e
per cui:
P1(C1)=2+2+2=6 e P2(C1)=2+2+3=7 e P3(C1)=2+2+3=6
P1(C2)=2+2+2=6 e P2(C2)=2+3+2=7 e P3(C2)=2+2+3=7
P1(C3)=2+2+2=6 e P2(C3)=2+2+2=6 e P3(C3)=3+2+2=7
P1(C4)=2+2+3=7 e P2(C4)=2+2+2=6 e P3(C4)=2+2+2=7
P1(C5)=2+3+2=7 e P2(C5)=3+2+2=7 e P3(C5)=2+2+2=6
P1(C6)=3+2+2=7 e P2(C6)=2+2+2=6 3 P3(C6)=2+2+2=6

Mettiamo tutto sotto forma di tabella (vedi sotto, con omessi per chiarezza i risultati che davano 6). Nelle tabelle si vede facilmente che V=2 e F=3 e per ogni caso F ha un’unica soluzione S(C), ovvero:
S(C1)=f, S(C2)=e, S(C3)=d, S(C4)=c, S(C5)=b, S(C6)=a

502 Base5 sol. 6 monete.png (41.46 KiB) Visto 6806 volte

[giobimbo]

Purtroppo, la stessa tabella di V=2 e F=3 viene anche ponendo V=2,33333… e F= 1,33333… per cui rifaccio tutto cambiando anche i valori dei pesi a, b, c, … in modo da non avere numeri decimali.
Pongo dunque il peso della moneta vera uguale a 1 mentre quella falsa vale 4, V=1 e F=4. Ci sono 6 casi possibili:
(C1) (1,1,1,1,1,4)
(C2) (1,1,1,1,4,1)
(C3) (1,1,1,4,1,1)
(C4) (1,1,4,1,1,1)
(C5) (1,4,1,1,1,1)
(C6) (4,1,1,1,1,1).

Definiamo le tre pesate come (ho corretto P3):
P1=a+b+c, P2=b+d+e, P3=c+e+f
da cui, caso per caso ricaviamo la tabella sotto in cui ho omesso il segno + e alle monete pesate corrisponde il quadretto giallo (e stavolta ci siamo).

502 remake.png (11.36 KiB) Visto 6792 volte

[giobimbo]

Avevo scritto “Purtroppo” perché avevo capito che bisognasse trovare “anche” il valore di F, quindi in verità lo schema era corretto.
Comunque, come capire se V>F o se F>V? E quale delle monete è quella falsa?
Supponiamo di avere il caso C(1) e sommiamo le tre pesate ottenendo 3+3+6=12. Abbiamo pesato 9 monete e 12/9=1,333. Poniamo V>1,333 (a sinistra) e F>1,333 (a destra) ricavandone le 12 tabelle della figura sotto.

Remake 2.png (21.82 KiB) Visto 6785 volte

Quale tabella presenta la stessa struttura del caso C(1) (cioè la prima tabella in alto nel precedente intervento) che ha la colonna delle pesate con risultati:
3 = piccolo
3 = piccolo
6 = grande?
La prima a destra con F=3>(V=1) e la moneta falsa è la “e”. Siccome C(1)=(1,1,1,1,1,3) la moneta falsa sarà la "3".
Lo stesso procedimento si seguirà per tutti gli altri casi.

[giobimbo]

Per concludere, è saltato fuori che, se P è il numero di pesate, si trova F anche adattando tale schema per P=(3,4,5,…) e m monete, con m=P*(P-1). Un esempio coi primi 3 valori di P nella figura sotto

Base5 algoritmo.png (10.44 KiB) Visto 6777 volte

Ancora, sintetizzando quanto detto prima:
1) Dalle tre pesate P1, P2 e P3 ricavo la tabella T1
2) Dalle 12 tabelle di Fig.1 e Fig.2 ricavo la tabella T2 isomorfa a T1
3) La x-esima colonna di T2 contiene l’elemento F
4) La x-esima colonna di T1 contiene la moneta falsa
5) Se T2 è nella Fig.1 (quella a sinistra) la moneta falsa pesa meno di quella vera
6) Se T2 è nella Fig.2 (quella a destra) la moneta falsa pesa di più di quella vera.

Ringrazio Paolo32 per aver riproposto questo problema, mi ha fatto passare ore piacevoli.

[giobimbo]

Avendo messo i risultati man mano che li ottenevo le cose son rimaste un poco slegate tra loro, come mi hanno fatto notare, da cui questo riepilogo.

Abbiamo le monete aj (per j=1,2,…,6) con le quali facciamo le pesate Pi (per i=1,2,3). Costruiamo la tabella TP delle pesate P1=a1+a2+a3, P2=a2+a4+a5 e P3=a3+a5+a6 come illustrato nella Fig.1, oppure più sinteticamente, eliminando i simboli + e = come illustrato in Fig.2, dove una casella gialla indica l’esistenza di una moneta.
Se le monete avessero tutte lo stesso peso avremmo P1=P2=P3 ma una moneta (che indichiamo con F mentre le altre sono V) ha un peso diverso. Non sappiamo in quale colonna di TP sia F per cui facciamo le 12 tabelle con tutti i casi possibili. In Fig.3 F<V e in Fig.4 F>V.
Nelle tre pesate le righe con F daranno un risultato diverso da quelle con monete tutte vere. Indichiamo con min un risultato Pi se esso è il minore dei tre, con Max se esso è il maggiore dei tre. Vediamo come in un caso pratico si trova la soluzione.
Supponiamo di aver avuto:
P1=12=min
P2=18=Max
P3=12=min
a cui corrispondono le tabelle t3 e T4 (vedi Fig.5 e Fig.6), ma se mettiamo i valori delle monete in modo da ottenere i pesi dell’ipotesi vediamo che solo T4 ha senso, quindi la moneta falsa è a4 e pesa di più di quella vera.
Supponiamo di aver avuto:
P1=15=Max
P2=15=Max
P3=9=min
a cui corrispondono le tabelle t6 e T2 (vedi Fig.7 e Fig.8.), ma se mettiamo i valori delle monete in modo da ottenere i pesi dell’ipotesi vediamo che solo T2 ha senso, quindi la moneta falsa è a2 e pesa di più di quella vera.

502 xxx.png (73.25 KiB) Visto 4839 volte

[franco]

Mah ...
Avevo qualche dubbio sul post precedente, ma questo riepilogo non ha fatto che aumentarli.
Secondo me, funziona solo se si sa già che la moneta falsa è più leggera o più pesante oppure nel caso che la differenza fra vere e false sia così grande da rendere non valida una delle due possibili soluzioni.
Nel primo esempio che fai

P1=12=min
P2=18=Max
P3=12=min
a cui corrispondono le tabelle t3 e T4 ...

le possibili soluzioni ssarebbero:
V=4 --- F=m4=10
V=6 --- F=m3=0 (impossibile)

Se però ottenessi queste altre 3 pesate (sempre con P2 maggiore di P1 e P3):
P1=28,5=min
P2=28,8=Max
P3=28,5=min
come faccio a stabilire con certezza quale delle due seguenti soluzioni è quella corretta?
V=9,5 --- F=m4=9,8
V=9,6 --- F=m3=9,3

6MONETE.png (15.18 KiB) Visto 4787 volte

ciao
Franco

[giobimbo]

Hai perfettamente ragione, le due soluzioni sono indistinguibili, ho avuto la sfortuna di scegliermi esempi che invece confermavamo la mia ipotesi mandandomi fuori strada. Siamo di nuovo da capo .

[NothIng]

Questo genere di giochi non mi piace ma questo mi ha colpito per due aspetti:
il numero di monete è il doppio delle pesate permesse
i tentativi di soluzione che leggo si basano su concetti di peso "maggiore, "minore", "uguale" mentre io istintivamente ho pensato a peso "diverso", "uguale".
Ecco i miei pensieri.

Divido le 6 monete in 3 gruppi $\displaystyle{A,B,C}$ di due monete ciascuno.
Suppongo che esista un metodo per determinare quali sono i due gruppi con monente vere e quello con monete false con due pesate.

Con queste condizioni rimane una pesata per trovare l'unica moneta falsa, si può farlo prendendo una moneta $\displaystyle{G_v}$ da un gruppo di monete vere e una moneta $\displaystyle{G_f}$ dal gruppo di monete false.
Ci sono due casi

1. $\displaystyle{G_v =G_f}$ --> la moneta del gruppo "false" che non è stata scelta è quella falsa, le altre cinque sono vere
2. $\displaystyle{G_v \neq G_f}$ --> la moneta $\displaystyle{G_f}$ è falsa, le altre cinque sono vere

[NothIng]

Suppongo che esista un metodo per determinare quali sono i due gruppi con monente vere e quello con monete false con due pesate.

Prima pesata: $\displaystyle{A}$ e $\displaystyle{B}$

1. $\displaystyle{A = B}$ --> le quattro monete dei gruppi $\displaystyle{A}$ e $\displaystyle{B}$ sono vere e una moneta del gruppo $\displaystyle{C}$ è falsa. Non serve una seconda pesata.
2. $\displaystyle{A \neq B}$ --> serve una seconda pesata.

Seconda pesata: si pesano $\displaystyle{A}$ e $\displaystyle{C}$ sapendo che $\displaystyle{A \neq B}$

1. $\displaystyle{A = C}$ e $\displaystyle{A \neq B; }$ --> le quattro monete dei gruppi $\displaystyle{A}$ e $\displaystyle{C}$ sono vere e una moneta del gruppo $\displaystyle{B}$ è falsa.
2. $\displaystyle{A \neq C}$ e $\displaystyle{A \neq B; }$ --> le quattro monete dei gruppi $\displaystyle{B}$ e $\displaystyle{C}$ sono vere e una moneta del gruppo $\displaystyle{A}$ è falsa.

[NothIng]

Come posso determinare quale sia la moneta falsa e se pesi di più o di meno con tre pesate su una bilancia per oro

Ooops ho dimenticato un pezzetto: come scoprire se la moneta falsa pesa di più o di meno.

Quando sulla bilancia è messo il gruppo con la moneta falsa si può dire se pesa più o meno in accordo alla posizione dei piatti

--> le quattro monete dei gruppi A e B sono vere e una moneta del gruppo C è falsa. Non serve una seconda pesata.

Qui si può usare la pesata che "non serve" dopo avere scoperto la moneta falsa per determinare se è più pesante o no


Il quesito parla di "bilancia per oro": ho imamginato fosse una di quelle a due piatti ma più lo rileggo e più mi vengono dubbi a riguardo

[franco]

Il quesito parla di "bilancia per oro": ho imamginato fosse una di quelle a due piatti ma più lo rileggo e più mi vengono dubbi a riguardo

Io avevo interpretato "bilancia per oro" come una bilancia a piatto singolo e indicazione del peso.

Il sistema che proponi, con la bilancia a 2 piatti, mi pare che consenta di individuare con certezza la moneta falsa ma non se sia più leggera o più pesante:

Peso A vs B
... se A<B peso A vs C
... ... se A<C allora A è falsa ed è più leggera
... ... se A=C allora B è falsa ed è più pesante
... se A>B peso A vs C
... ... e A>C allora A è falsa ed è più pesante
... ... se A=C allora B è falsa ed è più leggera
... se A=B A e B sono entrambe vere e peso C vs D
... ... se C<D peso C vs A
... ... ... se C<A allora C è falsa ed è più leggera
... ... ... se C=A allora D è falsa ed è più pesante
... ... se C>D peso C vs A
... ... ... se C>A allora C è falsa ed è più pesante
... ... ... se C=A allora D è falsa ed è più leggera
... ... se C=D anche C e D sono vere e peso E vs A
... ... ... se E<A allora E è falsa ed è più leggera
... ... ... se E>A allora E è falsa ed è più pesante
... ... ... se E=A allora F è falsa ma non ho modo di sapere, con 3 sole pesate, se è più leggera o più pesante

(salvo errori )