by dmbaggett on 6/1/20, 3:57 PM with 0 comments
You have 12 coins, one of which weighs more than the other 11. You have a balance, and wish to use it to find the heavier coin. You may only use the balance three times. How do you find the heavier coin?
This is a great puzzle for an early CS learning because it gives some intuition into the general strategy of divide-and-conquer. It also nicely extends to harder variants: can you do the same for 27 coins with three weighings? Is this the limit? Why? Can you prove your answer?
My question for HN is: can you recommend some puzzle books that focus on CS puzzles like this one that are suitable for a bright high schooler? (The bright high school in this case is my daughter.)