A piece of paper had the following diagram:

               o              o o o o
      From:   o o         To:  o o o
             o o o              o o
            o o o o              o

Below it, it read "Given the initial formation of ten coins, move exactly # coins to produce the end formation." It was pretty obvious that # stood for a digit, but it was smudged and couldn't be read. What possible numbers could it have been so the problem was solvable?

To allow explaining the solution, number the coins like this:

           0 
          1 2
         3 4 5
        6 7 8 9

Note: This problem was inspired by a forum question by Nicole.

The question asks more than just what is the minimum; the problem asks for which numbers could go into # and the question be answerable. For a given candidate of #, we want to be able to freeze 10-# coins that lie in some overlap of the "from" and "to" pics.
I find it fairly easy to see many arrangements of the pictures to get from 0 to 4 overlapping coins, corresponding to # being 10 through 6. There are also several straight forward ways of getting exactly 6 overlapping coins and the previous posters point out that when the diagrams are centered over each other, they have 7 overlapping coins. These correspond to # equal 4 and 3 respectively. I am convinced by an maximal area argument (but not a proof) that 7 overlapping coins is the maximum, so 3 is the minimum value of #.
What I don't see is how to get exactly 5 overlapping coins. I suppose we could pick 5 of a 6-coin overlap, but this seems a cheat to move a coin from a spot, only to replace it with another. I am stuck on this; perhaps #=5 is not possible.
A good added condition is given by Brianjn; all moved coins must remain in constant contact with at least one other coin. Can all of the above values of # be realized under this constraint?

Posted by owl on 2005-08-15 04:36:29