Problem of the Week 1150

Magic Coins

You are arrested and imprisoned in a country with an unusual judicial system. When you arrive at the prison, you are given 8 coins and told that 4 of them are magic coins. To you, the magic coins are indistinguishable from the others, but your jailers can immediately detect which is which.

Each evening you are allowed to partition all of the coins into two piles (not necessarily of the same size). If each pile contains exactly 2 magic coins, you are released.

Find the smallest n such that you can ensure you will be released in n days.

Extra credit: Same problem with 100 coins, 50 of which are magic, and you must get each of your two piles to contain 25 magic coins. Show that you can guarantee your release in 50 days.

Source: Problem by Gregory Galperin. Suggested by Joe Buhler and Larry Carter. It appeared in the spring issue of MSRI's Emissary, available for download (5.7MB).

© Copyright 2011 Stan Wagon. Reproduced with permission.

23 November 2011