Dodici palline e una scala

Dividi questo i nto tre gruppi di quattro, A1, A2, A3, A4; B1, B2 …; C1, C2 … Ogni passo qui corrisponde a una pesata.

• Pesare A contro B.
  • Se A> B, pesare A1, B1 e B2 contro B3 , B4 e C1.
    • Se i pesi sono uguali, uno tra A2 … 4 è più pesante; pesare A2 e A3. Se sono uguali, A4 è più pesante. Se uno è più pesante, allora quella palla è più pesante.
    • Se il primo gruppo è più pesante, allora A1 è più pesante o B3-4 è più leggero. Confronta B3 e B4; se sono uguali, A1 è più pesante; se sono diversi, la più leggera è la palla più leggera.
    • Se il primo gruppo è più leggero, B1 o B2 sono più leggeri. Pesali e guarda.
  • Se A < B, rinumera tutte le palle A in palle B ed esegui quanto sopra passi.
  • Se A = B, pesare A1, A2, A3 contro C1, C2, C3
    • Se sono uguali, pesare A1 contro C4. Se A1 è più leggero, C4 è la palla dispari ed è pesante. Se A1 è più pesante, allora C4 è la palla dispari ed è leggera.
    • Se A è più pesante di C, pesare C1 contro C2. Se sono uguali, C3 è la palla dispari ed è più leggera. Se non sono uguali, la più leggera delle due sfere è la più leggera
    • Se A è più leggera di C, pesare C1 contro C2. Se sono uguali, C3 è la palla dispari ed è più pesante. Se non sono uguali, la più pesante delle due palle è la palla più pesante.

Possiamo lavorare allindietro da il terzo passo per vedere, approssimativamente, perché funziona. Alla terza pesata, le opzioni devono essere ridotte a due o tre palline. Ciò significa che la seconda pesata deve ridursi a due o tre possibili palline.

Sappiamo che il primo passaggio rimuoverà 1/3 o 2/3 delle possibili soluzioni, qualunque cosa tu faccia. Ciò significa che, nel caso 1/3, è necessario dividere le possibilità da 8 in un gruppo di 3, un gruppo di 3 e un gruppo di 2. Da questo, il terzo punto di pesatura alla palla dispari fuori. Poiché questo caso implica che un set di palline è più pesante, in virtù del fatto di aver trovato la biglia dispari, sappiamo se è più pesante o più leggera, quindi in realtà non dobbiamo preoccuparci affatto di questa informazione.

Nel caso 2/3, è necessario ridurre le possibilità in un gruppo di 3 e un gruppo di 1, cosa abbastanza facile da fare in modo intuitivo. Poiché in realtà non conosciamo il peso relativo della pallina dispari in questo caso, le informazioni della terza pesata devono essere utilizzate per determinare se la pallina è più pesante o più leggera.

Commenti

• Sebbene questa risposta sia corretta, speravo in una risposta che spiegasse la strategia alla base delle scelte degli articoli da pesare.
• @JoeZ. I ‘ ho aggiunto qualcosa su come ho determinato questa risposta, anche se ‘ non sono sicuro di poter parlare di una soluzione generale a questo problema. (Inoltre, Cordiali saluti, ‘ ho modificato la mia risposta allaltra tua domanda.)
• Quello che ‘ hai messo è bene. Stavo pensando di ragionare più che di strategia, ripensaci.

Ecco è un altro modo per risolvere questo problema, che non coinvolge affatto alcun tipo di ramificazione condizionale. È infatti possibile impostare in anticipo un programma di pesatura fisso e determinare comunque quale palla è più leggera o più pesante in sole 3 pesate. Spiegherò come di seguito.

Lessenza di problemi come questi è: quante informazioni puoi ottenere dalla procedura che sei autorizzato a intraprendere? Ad ogni pesata, la bilancia può inclinarsi a sinistra, a destra o rimanere in equilibrio.Questo ti dà un totale di 3 ³ = 27 possibili risultati, e in questo caso devi discernere 24 risultati da essi (una delle 12 palline è leggera o pesante, che è 12 × 2 = 24 ).

Quindi, dobbiamo iniziare il noioso compito di mappare ogni risultato a un risultato.

Una delle cose che possiamo immediatamente notare è che ci sono anche tre stati per ogni sfera può essere inserito durante ogni pesata – sul lato sinistro della bilancia, sul lato destro della bilancia o fuori dalla bilancia. Naturalmente, questo viene mappato agli stati della scala in un modo che è intuitivamente analogo:

Se la palla dispari è più pesante …

• e la palla è posizionata sul lato sinistro, la scala si inclinerà a sinistra.
• e la palla sarà posizionata sul lato destro, la scala si inclinerà a destra.
• e la palla è fuori scala, la bilancia rimarrà bilanciata.

Se la palla è più leggera, le prime due casse vengono invertite.

Ci sono 27 modi possibili per posizionare ciascuna palla in tutte e tre le pesate, ciascuna corrispondente a un risultato diverso se quella palla è quella dispari. Dobbiamo trovare una disposizione delle palle in cui ogni possibile insieme di posizionamenti e il suo inverso (per i casi pesanti e leggeri) siano distinti, quindi no due palline sono una nello stesso posto per tutte e tre le pesate.

Ecco “una disposizione preliminare che soddisfa la proprietà di distinzione. Si noti che nessuna disposizione possibile appare più di una volta in entrambe le tabelle:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 L R 4 L R R L 5 L R R L 6 L R R L 7 L L R R 8 L L R R 9 L L R R 10 L L R R R L 11 L R L R L R 12 R L L L R R L = place it on the left R = place it on the right = leave it off 

Subito ci imbattiamo nel problema che “non stiamo mettendo lo stesso numero di palline su ciascuna scala. Se hai sette palline su un lato e una sullaltro, ovviamente la bilancia si inclinerà di lato con sette palline (a meno che la tua strana pallina fuori non sia ridicolmente pesante, ma non lasciamolo divertire scenario). Quindi dobbiamo invertire alcune di queste configurazioni in modo da “reinserirne quattro su ciascun lato per ogni pesata. Con alcuni tentativi ed errori, possiamo ottenere qualcosa del genere:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 R L 4 L R R L 5 R L L R 6 L R R L 7 R R L L 8 L L R R 9 L L R R 10 R R L L L R 11 R L R L R L 12 L R R R L L 

Quindi il nostro programma di pesatura finale delle palle è il seguente:

Weighing 1: 1 4 8 12 / 5 7 10 11 Weighing 2: 2 6 9 11 / 4 7 10 12 Weighing 3: 5 8 9 10 / 3 6 11 12 

E i risultati sono interpretati come tali:

==L : 3L L== : 1H R== : 1L ==R : 3H L=L : 8H R=L : 5H =L= : 2H L=R : 5L R=R : 8L =LL : 9H LL= : 7L RL= : 4L =LR : 6H LLR : 10L RLL : 12L =R= : 2L LR= : 4H RLR : 11H =RL : 6L LRL : 11L RR= : 7H =RR : 9L LRR : 12H RRL : 10H = : scale balanced L : scale tipped to the left R : scale tipped to the right nL : ball n is light nH : ball n is heavy 

E quindi, abbiamo creato uno schema di pesatura in cui ogni pesata è completamente predeterminata in anticipo, che riesce comunque a determinare quale palla è quella dispari e se è più leggera o più pesante.

Potresti notare che “t non abbiamo utilizzato LLL, RRR o === nei nostri accordi.

Non possiamo “utilizzare LLL e RRR come una tredicesima coppia per una tredicesima palla, perché alla fine dovremmo mettere nove palline sulla bilancia e non cè modo di farlo poiché nove è strano. Noi probabilmente potrebbe usarlo in luogo di una delle LLR/RRL coppie, ma lasciando LLL e RRR crea una simmetria nel grafico dei risultati che mi piace di più.

Tuttavia, ciò che è interessante è che puoi avere una tredicesima palla che mai metti su qualsiasi bilancia, e se la tua bilancia è bilanciata in tutte e tre le pesate, la tredicesima palla che non hai mai pesato è la strana palla fuori (anche se ovviamente non puoi dire senza una quarta pesata se è più leggera o più pesante).

Commenti

• Quindi, fondamentalmente si può risolvere questo problema con 13 palline, se si ha la 14esima sfera etalon. Ottima risposta.
• Probabilmente anche 14 palline, dove la quattordicesima pallina può essere più pesante è risolvibile, ma è più difficile, molto probabilmente puoi ‘ t.

Alcune delle risposte esistenti a questa antica domanda sono eccellenti, ma cè una famosa risposta che Penso che meriti una menzione qui. Viene da un articolo su Eureka , la rivista annuale della società matematica studentesca dellUniversità di Cambridge, scritto da CAB Smith con lo pseudonimo di “Blanche Descartes”.

Ha due caratteristiche molto interessanti. La prima è che si tratta di una soluzione “non ramificata”: non è necessario modificare ciò che si fa nelle pesate successive a seconda dei risultati di quelle precedenti. Il secondo è che una volta che lhai visto è quasi impossibile dimenticarlo.

La soluzione di Smith è scritta interamente in versi e include una spiegazione di come funziona, ma citerò solo la risposta effettiva. “F” ecco il nostro protagonista, il professor Felix Fiddlesticks, la cui madre gli ha chiesto aiuto per il puzzle. Ho apportato alcune piccole modifiche alla formattazione originale.

F ha disposto le monete in fila
E ha tracciato su ciascuna una lettera, quindi,
Per formare le parole: F AM NOT LICKED
(Un lidea nel suo cervello era scattata.)

E ora sua madre gli imporrà:
“MA, MI PIACE / TROVA
FALSO / MONETA!”

Ciascuna delle tre righe dellingiunzione di F “descrive una pesata.Quando li hai fatti tutti, i risultati determinano in modo univoco quale moneta è falsa e in che modo.

Commenti

• +1. Questo penso è una versione abbellita di Joe Z ‘ s answer

Ho passato un po di tempo a lavorare su questo puzzle dopo che è apparso in “Brooklyn Nine-Nine” (se vuoi, puoi vedere il Capitano Holt descrivere il puzzle qui ) e ho scritto una soluzione illustrata e dettagliata qui: Soluzione dellisola di Tyreses . In questa particolare versione sto tentando di trovare un isolano, Diffy, che è più pesante o più leggero degli altri 11 isolani.

Lezioni

La soluzione finale tiene conto di due cose da cui ho imparato tentativi precedenti:

1. In un gruppo di quattro, posso identificare Diffy in due pesate.

   A. Per prima cosa, ho impostato due isolani del gruppo contro due noto non Dif fys. Se laltalena si inclina, so che Diffy è uno di questi due. Se laltalena rimane in piano, so che Diffy è uno degli altri due.

   B. Ora seleziono uno dei due rimanenti Diffy possibili e lo metto contro un non Diffy noto. Se la scala si inclina, ho trovato Diffy. Se il tabellone rimane in parità, so che Diffy è lultimo isolano rimasto.

   C. In alternativa, se laltalena si inclina nel passaggio A e si desidera sapere se DIffy è pesante o leggero, è possibile annotare la direzione dal passaggio A e mettere i due possibili Diffys rimanenti sulla scala luno di fronte allaltro. Se laltalena si inclina nella stessa direzione del passaggio A, allora Diffy è quello ancora sullo stesso lato di quando era durante il passaggio A. Altrimenti, se lorientamento dellaltalena cambia, Diffy è sullaltro lato.

2. In un gruppo di tre posso identificare Diffy in una pesata, purché disponga di informazioni direzionali. Descriverò questo in modo più dettagliato in Usa n. 3.

Soluzione

A causa della lezione n. 1, posso dividere quattro isolani prima di controllare il resto. Se Diffy è in quel gruppo di quattro, la prima pesata risulterà pari e ora posso identificarlo tra quelle quattro con le mie due mosse rimanenti. Se Diffy non è in quel gruppo di quattro, ora ho quattro isolani che posso escludere e utilizzare anche per tarare laltalena.

Quindi, per il mio primo utilizzo dellaltalena, ho pesare gli otto isolani rimanenti uno contro laltro con quattro su ciascun lato.

Usa # 1

Ho già delineato il mio piano se questo primo utilizzo altalenante risulta pari, quindi cosa succede se risulta strano? È qui che entra in gioco il genio.

Ora ho alcune “informazioni direzionali”. Dora in poi chiamerò qualunque direzione laltalena inclinata in Uso 1 “Direzione 1” o “D1” in breve. So che se Diffy è pesante, è dalla parte dellaltalena che è caduta, e se se Diffy è leggera, è dalla parte dellaltalena che è salita. Se sposto Diffy, laltalena cambierà orientamento! Non ha scelta perché Diffy, e solo Diffy, fa inclinare laltalena. Inoltre, ricorda la lezione n. 2, ho informazioni direzionali e una mossa dopo quella attuale, quindi posso eliminare completamente tre possibili Diffy prima del prossimo utilizzo dellaltalena. Dovrò utilizzare uno degli isolani che ho escluso in Uso 1 per mantenere tre isolani su ciascun lato.

Usa # 2

Se Use # 2 ci dà un altalenante uniforme possiamo trovare Diffy nei tre che abbiamo rimosso, ma se non lo fa, dobbiamo prestare attenzione nella direzione in cui si muove laltalena. Si è spostato nello stesso modo di prima, Direzione 1, o ha cambiato orientamento in Direzione 2? La nostra prossima scelta sarà basata sulla risposta! Se si è spostato in Direzione 1, allora sappiamo che Diffy non è uno degli isolani che ha cambiato lato per lUso n. 2. Se laltalena si è mossa in direzione 2, allora Diffy è uno degli interruttori laterali. Ad ogni modo, lo abbiamo ridotto ad essere uno di tre o due. Luso del n. 3 è un po difficile da generalizzare poiché è diverso per ogni possibilità.

Usa il n. 3

Nel caso in cui ho un gruppo di tre possibili isolani Diffy, due di quegli isolani erano dalla stessa parte durante lUso # 1, quando laltalena si spostò in D1. Se metto uno di questi isolani su ciascun lato dellaltalena e laltalena si sposta di nuovo in D1, allora sappiamo che Diffy è lisola sul lato originale. Se laltalena si sposta in D2, allora sappiamo che Diffy si trova sul lato opposto dellaltalena. Se laltalena rimane in equilibrio, sappiamo che Diffy è il terzo membro del gruppo.

All Mapped Out

Commenti

• Questa soluzione è viziata per questa domanda.È accettabile solo se chiedono di identificare Diffy ma non se è più leggero o più pesante (vedi Even – Even – Anche nel tuo diagramma, L non è stato ponderato :)) Poi di nuovo, in quel caso possiamo risolvere il puzzle con 13 persone.

Questa è una riscrittura di R. Allen Gilliam di La soluzione di Jared Anderson da unaltra versione di questo puzzle su questo sito. Forse è proprio come funziona la mia mente, ma questo sembra molto più facile da capire.

Numera gli uomini (o monete, o palline) da 1 a 12.
Pesare 1 2 3 4 contro 5 6 7 8.
Se sono la stessa cosa, allora luomo diverso è 9 10 11 o 12. Vai al punto I di seguito.
Se sono diversi, prendi nota se 1 2 3 4 è più pesante o più leggero.

Pesare 1 2 3 5 contro 4 10 11 12. (Si noti che sappiamo che 10 11 e 12 non sono diversi.) Ci sono tre possibilità:
(1) Se 1235 ha lo stesso differenza (più pesante o più leggera) come 1234, allora il diverso deve essere 1 2 o 3 e ha la stessa differenza (più pesante o più leggera) di 1234. Vai a II sotto.
(2) Se 1235 equilibra 4 10 11 12 , allora il diverso deve essere 6 7 o 8 (quelli che abbiamo rimosso) e ha la stessa differenza (più pesante o più leggera) di 5678. Vai a II sotto.
(3) Se 1235 ora ha la differenza opposta (più pesante o più chiaro) come 1234, quindi 4 o 5 è il diverso. O 4 ha la stessa differenza di 1234 (più pesante o più leggero) o 5 ha la stessa differenza di 5678 (più pesante o più leggero). Quindi pesiamo semplicemente 4 contro 1. Se sono la stessa cosa, allora 5 è il diverso. Se sono diversi, allora 4 è il diverso.

I. Trovare quale di 9 10 11 12 è diverso con due pesate quando non sai se il diverso è più pesante o più leggero:

Pesare 9 contro 10. Due possibilità:
(1) Se “è diverso, quindi deve essere 9 o 10. Pesare 9 e 11. Se” sono uguali, 10 è quello diverso. Se “sono diversi” è 9.
(2) Se “sono lo stesso, quindi deve essere 11 o 12. Pesare 9 e 11. Se” sono lo stesso, 12 è quello diverso. Se “sono diversi, è 11.
(Se è” s 12, non sapremo se fosse più pesante o più leggero dato che non lo abbiamo mai pesato. Lo abbiamo trovato per eliminazione. Deve essere diverso poiché tutti gli altri pesano lo stesso.)

II. Trovare quale dei tre uomini è diverso con uno che pesa quando sai se laltro è più pesante o più leggero:

Rinomina i tre uomini 1 2 3. Pesa 1 contro 2. Due possibilità:
(1) Se sono uguali, 3 è il diverso.
(2) Se sono diversi, a seconda di quale ha la differenza corretta rence (più pesante o più leggero) è quello diverso.

Questa sembra essere la soluzione più semplice per 12 elementi se devi solo trovare lelemento di peso diverso, come richiedono alcune versioni del puzzle. La soluzione di Joe Z può trovare larticolo e la differenza con 12 articoli e il diverso articolo con 13 articoli. Trovare il diverso articolo e la differenza con 14 articoli sembra matematicamente impossibile con 3 pesate perché ci sono solo 27 possibili risultati con 3 pesate e ci sono 28 possibilità con 14 elementi. Ma una variazione della soluzione di Joe Z potrebbe trovare lelemento diverso su 13 e se è più pesante o più leggero? In tal caso, trovare il diverso ma non la differenza con 14 gli articoli sarebbero possibili. Trovare quello diverso ma non la differenza su 15 sarebbe impossibile perché puoi lasciare solo un articolo fuori dalle pesate pur essendo in grado di identificare quello diverso, e se peserai larticolo allora lo farai sapere se è più leggero o più pesante, cosa che sappiamo essere matematicamente impossibile con 14 elementi.

Questa soluzione è simile a quello fornito da R Gilliam ma diverso nel secondo passaggio Divi de le palline in 3 gruppi di 4 palline ciascuno. Chiamiamoli g1 g2 e g3 scegliamo due gruppi qualsiasi e li pesiamo luno contro laltro. Uno dei due scenari è vero. Le padelle sono bilanciate: le 8 palline che avete appena pesato hanno tutte il peso corretto. Le padelle sono sbilanciate: 4 palline che non hai pesato hanno tutte il peso corretto.

In ogni caso, alla fine della prima pesata avrai almeno 4 palline del peso corretto.

Per la seconda pesata un lato del piatto dovrebbe avere 3 palline del peso corretto. Se le padelle erano sbilanciate dopo la prima pesata, mettere 3 palline da una delle padelle sbilanciate nellaltro piatto. Se le padelle erano bilanciate dopo la prima pesatura, mettere 3 delle 4 palline che hanno messo la prima pesata nellaltro piatto.

Se le padelle sono sbilanciate dopo questa pesata saprai se la strana è più pesante o più leggera poiché una delle padelle contiene palline del peso corretto. Se le padelle sono bilanciate, la quarta palla che è stata lasciata fuori è la strana e puoi scoprire se è più lottare pesandolo contro una palla di peso corretto.

Se le padelle sono sbilanciate, sai se la strana palla è più pesante o più leggera. Prendi 2 delle 3 palline dalla padella (che non contiene le palline del peso corretto) e pesale una contro laltra. Sai già se lo stravagante è più pesante o più leggero. Se le padelle sono sbilanciate, scegli la padella che corrisponde alla direzione del peso della strana palla. se i piatti sono in equilibrio la terza palla è la strana.

Puoi anche risolverla usando 4 gruppi di 3 palline . Pesa 3 contro 3 e se è in equilibrio, puoi tenere da parte quelle 6 palle come note-uguali. Se non si bilanciano, sai che la biglia dispari è in quel gruppo di 6. Quindi, pesare 3 dei noti-uguali contro uno dei 2 gruppi di 3 incognite. Se è in equilibrio, il dispari è nella finale gruppo di 3. Se non si bilancia, sai che il dispari è ancora sulla bilancia. Infine, usando lultimo gruppo di 3 palline che è sconosciuto e disuguale, mettine una su ciascuna estremità e tieni da parte la terza. Se la bilancia è in equilibrio, sai che la palla solitaria che hai tenuto da parte è la palla dispari. Se la scala non è bilanciata, sai che la palla dispari è sulla scala. Per determinare la palla dispari e se è più pesante o più leggera, devi aver notato se il gruppo sconosciuto era più pesante o più leggero del noto uguale gruppi. Se erano più pesanti, allora la palla solitaria è più pesante.

Commenti

• ” Per determinare il palla dispari e se è ‘ più pesante o più leggero, devi aver notato se il gruppo sconosciuto era più pesante o più leggero dei gruppi noti uguali. ” Se tutti e tre i gruppi pesati nelle prime due pesate erano uguali, ‘ non dispone di queste informazioni.

(1) Posiziona le palline 6 e 6 sulla bilancia. Rimuoverne uno da ogni lato finché la bilancia non si equilibra.

(2) Prendi le ultime due palline rimosse (o le restanti due se la bilancia non è mai bilanciata) e posizionale da un lato (lato A) e due palline di uguale peso dallaltro (lato B). Se il lato A è più basso, lo stravagante è più pesante, se il lato B è più basso, lo stravagante è più leggero. Rimuovine uno da ogni lato. Se la bilancia è in equilibrio, la palla rimossa dal lato A è la palla strana, altrimenti lo è la palla rimasta sul lato A.

Commenti

• Ciò richiede a sette pesate. Il problema ti chiede di farlo in tre.
• @nosun – Benvenuto in puzzling.se. Solo per farti sapere, a volte le risposte errate vengono sottovalutate per separarle dalle risposte buone. Questo non ha lo scopo di scoraggiarti dal fornire buone risposte ad altre domande.