Puzzle di pesatura monete difficile: 14 monete, 1 falso (più pesante o più leggero), 3 pesate predeterminate
Questa recente domanda mi ricorda un rompicapo sulla pesatura di monete che ho imparato molti anni fa. È uno degli enigmi più difficili di questo tipo che io conosca. Pubblicherò la mia soluzione tra pochi giorni, e nel frattempo spero che qualcuno possa apprezzarla. (Mi scuso se si tratta di una ripetizione, ma ho cercato e non sono riuscito a trovare questa versione esatta.)
Ci sono $14$ monete sospette ,$13$di cui sono buoni e hanno lo stesso peso, e l'ultimo è cattivo e hanno un peso diverso (più pesante o più leggero). Inoltre, hai un file$15$la moneta nota per essere buona.
Vuoi scoprire quale moneta sospetta è cattiva e il più possibile (vedi sotto), se è più pesante o più leggera. Ci sono quindi$28$ possibili risposte: $14$ sospetti $\times \{heavier, lighter\}$.
Ti è permesso $3$pesate su una bilancia. Adesso ovviamente$3$ le pesate ti danno solo $3^3 = 27$ possibili risultati, quindi non è possibile distinguere completamente tutti $28$risposte. Il requisito è che:
$26$ del $27$ i risultati devono portare a una risposta univoca (quale moneta è cattiva e se è più pesante o più leggera)
mentre l'ultimo risultato deve portare a sapere quale moneta è cattiva, ma senza sapere se è più pesante o più leggera (cioè raggruppa insieme $2$ risposte per quella moneta).
Il puzzle di cui sopra sarebbe già abbastanza difficile, ma ecco la svolta finale: quali monete usare in una pesata non possono dipendere dai risultati delle pesate precedenti.
Per essere più precisi, etichetta le monete sospette ABCDEFGHIJKLMN
e la moneta nota per essere buona X
. Prima di iniziare, è necessario annotare quali due sottoinsiemi di monete sono coinvolti in ciascuno dei file$3$pesate, ad es ABCDX-EFGHN, IJKL-MNAB, CDEFGH-IJKLMN
. In questo modo, la seconda pesata IJKL-MNAB
è predeterminata e non può dipendere dal risultato della prima pesata ABCDX >/=/< EFGHN
, ecc. (In effetti, ora puoi eseguire$3$ pesate in qualsiasi ordine.)
Riesci a trovare un tale insieme di $3$ pesate predeterminate che soddisfano i requisiti?
SUGGERIMENTO # 1: il risultato$(=, =, =)$, cioè tutti $3$a parità di pesate, può avvenire solo se la moneta difettosa non viene affatto utilizzata in nessuna pesatura. Ciò corrisponde al 2 ° punto elenco del requisito. Cioè in qualsiasi soluzione corretta, c'è esattamente una moneta che non è utilizzata in nessuna pesatura e il risultato$(=,=,=)$ indica che questa moneta è cattiva, ma senza sapere se la moneta è più pesante o più leggera.
SUGGERIMENTO # 2: lascia che il file$28$ risposte essere $S = \{A+, A-, B+, B-, ..., N+, N-\}$ dove $+$ e $-$significa rispettivamente più pesante e più leggero. Nel frattempo, il$27$ i risultati formano a $3 \times 3 \times 3$ cubo, che possiamo denotare $T = \{-1, 0, +1\}^3$, dove $-1, 0, +1$denotano che il lato sinistro della bilancia è più leggero, uguale o più pesante. Dobbiamo trovare una mappatura$f: S \to T$ con queste proprietà:
- Il suggerimento n. 1 lo mostra già $f(N+) = f(N-) = (0,0,0)$.
- Il resto $26$ risposte e $26$ i risultati devono essere mappati in modo biettivo.
- Predeterminati pesate$\implies f(A+)$ e $f(A-)$sono correlati in un certo modo. Come?
- Di quali altri vincoli abbiamo bisogno $f$?
Risposte
Supponiamo che una tripla dei risultati di pesata determini una moneta. Se il risultato di una pesata è "uguale", la moneta non compare in quella pesata. Altrimenti, la moneta appariva sul lato "minore" di ciascuna pesata o sul lato "maggiore" di ciascuna pesata a seconda che la moneta fosse più leggera o più pesante.
Per ogni moneta, quindi, scegliere un modello di risultato di pesata distinto che determinerà quella moneta. (La pesatura di schemi di risultati completamente ribaltati deve identificare la stessa moneta con il peso opposto, quindi non li useremo.)
A < = =
B = < =
C = = <
D < < =
E < = <
F = < <
G < > =
H < = >
I = < >
J < < <
K < < >
L < > <
M > < <
N = = =
Quindi sappiamo esattamente come assemblare ogni pesata (cioè A
appare solo nella prima pesata; G
appare sui lati opposti delle prime due pesate; J
appare sullo stesso lato di tutte le pesate; ecc.) Tranne che non sappiamo quale lato mettere le monete sono accese, ma decidere i lati risulta essere facile, poiché dobbiamo semplicemente bilanciare il numero di monete in ogni pesata. La moneta X
(la nota moneta buona) è necessaria perché altrimenti ci sono nove monete coinvolte in ogni pesata. Non saremo in grado di distinguere tra monete N
più leggere o più pesanti.
Una soluzione è
AGJKL-DEHMX
BIJKM-DFGLX
CHJLM-EFIKX
Ora che @tehtmi ha pubblicato una soluzione valida, ecco il mio approccio leggermente diverso.
Come ho accennato nel suggerimento n. 2, la cosa interessante delle pesate predeterminate è:$f(A+) = -f(A-)$, cioè le due risposte $A+, A-$ deve avere risultati opposti in tutto $3$pesate. (L'opposto di "balance" aka "$=$"aka $0$ è ovviamente bilancia.) Questo generalmente non è vero in una soluzione in cui una pesata successiva dipende dal risultato di una pesata precedente.
Quindi comunque diventa una questione di assegnazione $13$ $+$è e $13$ $-$è al $26$ risultati non centrati nel complesso $3 \times 3 \times 3$ cubo, tale che:
- Vincolo 1: per qualsiasi coppia di risultati $y,z$ che sono riflessi al centro, $y,z$ deve avere segni opposti.
In questo cubo, il file $6$ facce ($3$ coppie di facce) rappresentano il $3$pesate. Se avessimo accesso a un numero illimitato di monete note per essere buone (infatti$9$è sufficiente), allora il vincolo 1 è sufficiente. Diciamo che la faccia superiore ha$A+, B+, C+, D+, E+, F+, G+, H+, I+$, quindi la faccia inferiore ha $A-, B-, \dots, I-$ e la pesatura sarebbe quella $9$ monete vs $9$ monete note per essere buone.
Ma abbiamo solo $1$ moneta nota per essere buona, e questo si traduce in:
- Vincolo 2: ciascuno dei $6$ facce (ogni faccia essendo $9$ risultati) deve consistere in $5$ di un segno, e $4$di un altro. La pesatura sarà il$5$ vs il $4$ più la moneta nota bene.
A questo punto, il problema diventa un piccolo puzzle da colorare che deve essere risolto per tentativi ed errori. Una soluzione è mostrata di seguito (le tre separate$3 \times 3$ i quadrati rappresentano gli strati superiore, centrale e inferiore del cubo):
+ - +
- + +
+ - -
- + -
+ ? -
+ - +
+ + -
- - +
- + -
e solo per completezza, ecco come assegnare loro delle lettere in modo che corrispondano esattamente alla soluzione di tehtmi:
J+ F- M+
E- C+ H+
L+ I- K-
D- B+ G-
A+ N? A-
G+ B- D+
K+ I+ L-
H- C- E+
M- F+ J-
dove ad esempio la coppia faccia sinistra-faccia destra è la pesata JLAGK-EDHMX
e la coppia faccia superiore-faccia inferiore è la pesata LHCMJ-KIEFX
, ecc.
A proposito, questo risultato è equivalente al seguente risultato:
- Se solo ci fossero $13$ monete sospette (e $1$ male come al solito), più una singola moneta conosciuta-buona, poi in $3$pesate predeterminate possiamo trovare la moneta cattiva e dire se è più pesante / leggera. Dopotutto, non abbiamo nemmeno usato il file$14$th moneta
N
nella soluzione sopra.
che è a sua volta strettamente più forte di questo classico risultato:
- Il classico$12$-coin puzzle viene spesso posto senza il vincolo di pesate predeterminate, ma in realtà può essere risolto utilizzando pesate predeterminate. In questo classico, non esiste una moneta conosciuta bene. Tuttavia, nella nostra soluzione
J
(un sospetto) eX
(la moneta nota bene) compaiono in tutti$3$pesate e sempre su lati opposti. Quindi eliminarli entrambi risolve il classico puzzle con$3$ pesate predeterminate di $4$-vs-$4$ ogni.
C'è una descrizione molto semplice di una strategia di pesatura predeterminata ottimale per qualsiasi numero di monete $n\ge 1$. Questo utilizza il sistema ternario bilanciato , che descrivo ora. Ogni numero intero positivo$n$ può essere scritto in modo univoco nella forma $$ n=\sum_{i=0}^\infty b_i3^i,\qquad b_i\in\{-1,0,+1\}\text{ for }i\in\mathbb N, \text{only finitely many $b_i \ neq 0$.} $$ Per esempio, $25=1\cdot 3^3+0\cdot 3^2+(-1)\cdot 3^1+1.$ Utilizzando $+$ come simbolo per la cifra $1$ e $-$ per la cifra zero, scriveremmo $25$ in ternario bilanciato, con infiniti zeri iniziali, come $$ 25=\cdots000+0-+ $$ Ora, considera la seguente trasformazione su questa sequenza infinita di $\pm$se $0$S; nega ogni simbolo che ha un numero dispari di zeri alla sua destra. Il risultato dell'esempio precedente è$$ 25\bowtie\cdots 000\color{red}-0-+ $$Io chiamo questa rappresentazione ternaria contorta di$25$. Quindi, disponi tutte queste sequenze infinite in una matrice infinita, in cui le cifre che sono state negate durante la conversione in ternario contorto sono evidenziate in rosso.
$$ \def\r{\color{red}} \begin{matrix} 0 & \bowtie & \cdots & 0 & 0 & 0 & 0\\ 1 & \bowtie & \cdots & 0 & 0 & 0 & +\\ 2 & \bowtie & \cdots & 0 & 0 & + & -\\ 3 & \bowtie & \cdots & 0 & 0 & \r - & 0\\ 4 & \bowtie & \cdots & 0 & 0 & + & +\\ 5 & \bowtie & \cdots & 0 & + & - & -\\ 6 & \bowtie & \cdots & 0 & \r - & \r + & 0\\ 7 & \bowtie & \cdots & 0 & + & - & +\\ 8 & \bowtie & \cdots & 0 & \r - & 0 & -\\ 9 & \bowtie & \cdots & 0 & + & 0 & 0\\ 10 & \bowtie & \cdots & 0 & \r - & 0 & +\\ 11 & \bowtie & \cdots & 0 & + & + & -\\ 12 & \bowtie & \cdots & 0 & \r - & \r - & 0\\ 13 & \bowtie & \cdots & 0 & + & + & +\\ 14 & \bowtie & \cdots & + & - & - & -\\ \vdots &&\vdots &&&\vdots \end{matrix} $$ Per trovare la strategia di pesatura per $n$ monete, numera le monete da $0$ per $n-1$. Per ogni colonna di quella matrice, pesare le monete corrispondenti alle etichette di riga della$+$E 'in quelle colonne, contro le monete corrispondenti a $-$'s (ignorando le infinite colonne iniziali le cui voci $0$ per $n-1$sono tutti zero). Potrebbe anche essere necessario aggiungere la moneta di riferimento su un lato per equalizzare questi gruppi.
Per il tuo problema di $n=14$, le pesate sono (dove $R$ denota moneta di riferimento):
- $1,4,7,10,13\quad $ vs $\quad 2,5,8,11,R$
- $2,4,6,11,13\quad $ vs $\quad 3,5,7,12,R$
- $5,7,9,11,13\quad $ vs $\quad 6,8,10,12,R$.