Trova la strana palla fuori $18$ palle, dove $17$ pesano lo stesso.
Esistono molte varianti di questo problema. Quello con cui sto lavorando è
Ci sono $17$ palline che pesano lo stesso, e $1$palla che potrebbe pesare o più pesante o più leggera dell'altra$17$. Di quante pesate hai bisogno su una bilancia per determinare quella dispari e se è più pesante o più leggera?
Il caso più semplice in cui sai se la palla dispari è più pesante o più leggera può essere trovata $3$pesa. L'idea è di dividere il file$18$ palline in gruppi di $6$, dì, $6A$, $6B$, $6C$. Pesare$6A$ e $6B$su una scala. Se si bilanciano a vicenda, allora$6C$ha fuori quello strano. Se non si bilanciano a vicenda, e$6A$ è più in basso sulla scala, quindi $6A$ ha la palla più pesante, e analogamente per $6B$. Quindi ci vuole un massimo di$1$ pesare per determinare il gruppo di $6$con la palla più pesante. Quindi puoi dividere questo gruppo di$6$ in $3$ gruppi di $2$e usando la stessa idea, puoi trovare il gruppo dispari di $2$ fuori con un massimo di $1$pesare. Quindi sei rimasto con un gruppo di$2$ e ci vuole $1$pesare per determinare la palla più pesante. Quindi, in totale, hai bisogno$3$ pesare in questo caso.
Ma la variante più difficile di questo problema è dove non sai se la strana palla fuori è più pesante o più leggera. In questo caso, ho scoperto che hai bisogno di un massimo di$5$ cerca di trovare quello dispari e di determinare se è più pesante o più leggero, ma non ho idea se sia corretto, o come giustificare che questo sia il numero minimo del numero massimo di tentativi.
L'idea è simile al problema precedente. Dividere$18$ palle in $6A$, $6B$, $6C$. Questa volta ci vuole un massimo di$2$ cerca di trovare il gruppo di $6$. cioè pesare$6A$ e $6B$ su una scala, se corrispondono, allora $6C$è lo strano gruppo fuori. Se$6A$ e $6B$non corrisponde, quindi abbiamo bisogno di un peso aggiuntivo per determinare quello dispari. Quindi,$2$ cerca.
Ora una volta che abbiamo trovato lo strano gruppo di $6$, applichiamo la stessa idea, che ne prende un'altra $2$tentativi (massimo). Poi siamo rimasti con un gruppo di$2$. Ci vuole esattamente$1$ pesare perché puoi prendere $1$ palla dal gruppo di $2$ e pesalo con uno degli altri $16$palle che sappiamo essere le. Se questa palla è la stessa, la palla rimanente è quella dispari. Quindi ci vuole un massimo di$2+2+1 = 5$cerca di trovare questa strana palla. Non abbiamo bisogno di un peso aggiuntivo per determinare se questa palla rimanente è più pesante o più leggera.
Questo perché quando abbiamo trovato il gruppo di $6$e il successivo gruppo di $2$, abbiamo preso il massimo di $2$cerca. Se ci vuole$2$ cerca di trovare il gruppo dispari di $6$ fuori, quindi significa che la seconda pesata del $2$ try ci permette di determinare se questa strana palla fuori è più pesante o più leggera.
Ad esempio, considera $6A$, $6B$, $6C$ancora. Diciamo che prima pesiamo$6A$ e $6B$e scoprire che non pesano lo stesso. Poi pesiamo$6C$ con entrambi $6A$ o $6B$. Se pesiamo$6A$ con $6C$ e trovalo $6A$ non corrisponde $6C$, poi $6A$ è quello strano fuori, ma anche se $6A < 6C (6A > 6C)$, allora lo sappiamo $6A$ ha una palla che pesa di meno (di più).
È questo l'approccio più ottimale o esiste un metodo che richiede solo $4$pesare dentro? Il mio istinto mi dice che dovrebbe esserci un file$4$ approccio di pesatura.
Il $12$-palla variante del problema e la sua soluzione è pubblicata in http://www.mytechinterviews.com/12-identical-balls-problem. Puoi vedere che applicano un approccio analogo rompendo il$12$ palle in $3$ gruppi di $4$, ma applicano un mix e un abbinamento interessanti per trovare solo quello dispari $3$ si sposta.
Risposte
Non ho controllato la soluzione per il classico $12$ versione palline http://www.mytechinterviews.com/12-identical-balls-problem. Ma se funziona, banalmente porta a un file$4$ soluzione di pesatura per il $18$ custodia per palline.
Davvero, visto il classico, c'è pochissimo lavoro extra da fare!
Per prima cosa pesate $3A$ vs $3B$. Se sono sbilanciati, diciamo$3A > 3B$, puoi scoprirlo con $3A$ vs $3C$ (tutti $3C$sono buone) se la palla cattiva è più pesante o più leggera. Quindi sicuramente puoi trovare il colpevole tra un gruppo di$3$con una sola pesata in più. Totale$3$ pesate.
E se $3A = 3B$, allora sei ridotto al classico $12$-palla problema che può essere risolto con $3$ pesate aggiuntive, per un totale di $4$.
Ulteriori considerazioni: infatti, $4$ le pesate possono risolvere $30$ palle, non solo $18$.
In precedenza, il $3A \neq 3B$ branch porta sempre a $3$pesate totali, il che è uno spreco. Immagina di averlo fatto$9+9+12 = 30$palle. La prima pesata può essere$9A$ vs $9B$. Se sono sbilanciati, ancora un secondo$9A$ vs $9C$ (tutto bene) ti dirà se quello cattivo è pesante o leggero, e poi potrai usarlo $2$ più pesate per trovare il colpevole $9$ (ricerca trinaria), per un totale di $4$ pesate.
Inoltre, anni fa ho risolto un caso (un'estensione del classico) dove $13$ le palle (sconosciute pesanti / leggere) possono essere risolte con $3$ pesate, a condizione che tu abbia accesso a palline extra note per essere buone - IIRC di cui hai bisogno $2$così buoni extra. Questo significa$9+9+13 = 31$ può essere risolto con $4$ pesate, coz in $9A=9B$ caso sei rimasto davvero $13$ sospetti ma molte palle extra note per essere buone.
Sospetto persino $31$ non è il limite (per $4$pesate). Quando pesi$9A$ vs $9C$, possono verificarsi solo due risultati (da $9A > 9B$). Questo è molto inefficiente e potrebbe essere possibile un ulteriore sfruttamento ...
Probabilmente conosci il classico legame che con $n$ pesate ci sono solo $3^n$ possibili risultati, quindi con $n=4, 3^n = 81$, non puoi risolvere $\ge 41$ palle ($\ge 82$risultati). non sto dicendo$40$ è realizzabile, ma c'è un ampio divario tra $31$ e $40$...
Pesata 1 : Pesata$1$-$6$ contro $7$-$12$. Se il risultato è equilibrato , allora sappiamo che la palla dispari è nel set$13$-$18$, che (effettivamente) prende $3$più misurazioni per un totale di 4 pesate.
Se la prima pesata è sbilanciata , supponiamo senza mancanza di generalità che$1$-$6$ è più pesante di $7$-$12$. Quindi eseguire ...
Pesata 2 : Pesata$1$-$3$ contro $7$-$9$. Se il risultato è equilibrato , la palla dispari è dentro$\{ 4, 5, 6, 10, 11, 12 \}$, che in effetti prende $3$più pesate, per un totale di 5 pesate.
Se invece il risultato è sbilanciato , supponiamo senza perdita di generalità che$1$-$3$ è più pesante di $7$-$9$. Allora sappiamo che la palla dispari è in quel set di sei, che effettivamente richiede altre due pesate per un totale di 5 pesate.