Quizzino della domenica: La moneta falsa

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

4 pensieri su “Quizzino della domenica: La moneta falsa

  1. thread

    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.

  2. Paolo C

    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.

  3. layos

    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.

I commenti sono chiusi.