Avete 42 monete, tutte apparentemente simili tra loro: però una di esse è falsa, e ha un peso diverso dalle altre. Avete inoltre una bilancia a due piatti. Non dovete scoprire qual è la moneta falsa, tanto riuscite a sbolognarla lo stesso: dovete semplicemente dire se è più pesante o più leggera. Quante pesate vi servono come minimo? E se le monete fossero state 41?
(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p061.html; la risposta verrà postata lì il prossimo mercoledì. Il problema è tratto da Anany e Maria Levitin, Algorithmic Puzzles)
Ultimo aggiornamento: 2016-05-31 13:01
Con 42 è facile, due pesate, tre gruppi di 14 monete. Con 41 ora ci penso.
Dovrebbero bastare 2 pesate.
Con 42 monete: le divido in 3 gruppi da 14 (A, B, C); confronto il peso di A e B, ho tre casi:
1) A pesa come B –> tolgo B dalla bilancia e aggiungo C –> se C è più pesante di A, la moneta falsa è più pesante e viceversa.
2) A è meno pesante di B –> tolgo B dalla bilancia e aggiungo C –> se C pesa come A, la moneta falsa è più pesante, altrimenti è più leggera.
3) A è più pesante di B –> tolgo B dalla bilancia e aggiungo C –> se C pesa come A, la moneta falsa è più leggera, altrimenti è più pesante.
Con 41 monete il procedimento dovrebbe essere analogo, soltanto che in questo caso ho 2 gruppi da 14 e 1 gruppo da 13. Quando devo pesare il gruppo da 13, gli aggiungo una moneta che recupero dal gruppo che non sto pesando.
Se sono 42, bastano 2 pesate.
Se sono 41, ne tolgo 2 e faccio 2 pesate con le restanti 39. Da queste 2 pesate puo’ risultare che la moneta falsa e’ uno delle due che ho tolto. Allora ripeto l’algoritmo usando le 2 monete tolte all’inizio e una a caso delle 39. La risposta e’ 4.
Con 42 sono 2 pesate perché è divisible per 3.
Con 41 posso fare in tre pesate: dieci e dieci se sono pari passo all’altro gruppo dieci e dieci se sono ancora pari prendo una qualunque moneta e la confronto con lo scarto.