Sunday, December 16, 2007

Solution to Vandal Puzzle

This is the solution to the puzzle The Vandal Puzzle - The Ug and the Mug published on 20th November. Those who haven't yet tried the puzzle Click here!!

And here goes the Solution/Answer to the Puzzle:
There is no way that Ug and Mug can produce 2000 pieces of glass starting from one piece, and smashing any piece into 7 or 10 pieces.

We can show this by showing that there is a special property that one piece of glass has, which is not changed by being struck by Mug or Ug, or more precisely, which is also a property of the number of pieces of glass resulting after a strike.

To understand how this argument works, suppose a simpler case, that a single vandal named Bug can smash one piece of glass into 3. Now can he ever create 100 pieces of glass? If he takes one of the 3 pieces of glass and smashes it into 3, then he has now a total of 5 pieces. Choosing any one of these pieces and smashing it yields a total of 7, and so on. Every one of these numbers is odd. This is no accident. If you start with an odd number of pieces (which we did), take one and make it three, you have increased your original number by 2, which leaves it odd. Since you can't get from 1 to 100 by hops of size 2, Bug can't make 100 pieces by starting from 1.

Now we note the Ug and Mug have a similar problem. Each strike by Ug increases the number of pieces by 6, while Mug increases the number by 9. Both of these numbers are divisible by 3. That means that adding them to the current total of pieces cannot change the remainder of the total, when it is divided by 3. This remainder is called an invariant. The number 1 has a remainder of 1 when divided by 3. Therefore, at any time during Ug and Mug's spree, the total number of pieces of glass must have a remainder of 1 when divided by 3. The number 2000 does not have this property, and so it is not possible for them to create this number of pieces.