A MATCH MYSTERY.
(
Puzzle Games.)
Here is a little game that is childishly simple in its conditions. But
it is well worth investigation.
Mr. Stubbs pulled a small table between himself and his friend, Mr.
Wilson, and took a box of matches, from which he counted out thirty.
"Here are thirty matches," he said. "I divide them into three unequal
heaps. Let me see. We have 14, 11, and 5, as it happens. Now, the two
players draw alternately any number from any one heap, and he who draws
the last match loses the game. That's all! I will play with you, Wilson.
I have formed the heaps, so you have the first draw."
"As I can draw any number," Mr. Wilson said, "suppose I exhibit my usual
moderation and take all the 14 heap."
"That is the worst you could do, for it loses right away. I take 6 from
the 11, leaving two equal heaps of 5, and to leave two equal heaps is a
certain win (with the single exception of 1, 1), because whatever you do
in one heap I can repeat in the other. If you leave 4 in one heap, I
leave 4 in the other. If you then leave 2 in one heap, I leave 2 in the
other. If you leave only 1 in one heap, then I take all the other heap.
If you take all one heap, I take all but one in the other. No, you must
never leave two heaps, unless they are equal heaps and more than 1, 1.
Let's begin again."
"Very well, then," said Mr. Wilson. "I will take 6 from the 14, and
leave you 8, 11, 5."
Mr. Stubbs then left 8, 11, 3; Mr. Wilson, 8, 5, 3; Mr. Stubbs, 6, 5, 3;
Mr. Wilson,4, 5, 3; Mr. Stubbs, 4, 5, 1; Mr. Wilson, 4, 3, 1; Mr.
Stubbs, 2, 3, 1; Mr. Wilson, 2, 1, 1; which Mr. Stubbs reduced to 1, 1,
1.
"It is now quite clear that I must win," said Mr. Stubbs, because you
must take 1, and then I take 1, leaving you the last match. You never
had a chance. There are just thirteen different ways in which the
matches may be grouped at the start for a certain win. In fact, the
groups selected, 14, 11, 5, are a certain win, because for whatever your
opponent may play there is another winning group you can secure, and so
on and on down to the last match."
Answer:
If you form the three heaps (and are therefore the second to draw), any
one of the following thirteen groupings will give you a win if you play
correctly: 15, 14, 1; 15, 13, 2; 15, 12, 3; 15, 11, 4; 15, 10, 5; 15, 9,
6; 15, 8, 7; 14, 13, 3; 14, 11, 5; 14, 9, 7; 13, 11, 6; 13, 10, 7; 12,
11, 7.
The beautiful general solution of this problem is as follows. Express
the number in every heap in powers of 2, avoiding repetitions and
remembering that 2^0 = 1. Then if you so leave the matches to your
opponent that there is an even number of every power, you can win. And
if at the start you leave the powers even, you can always continue to do
so throughout the game. Take, as example, the last grouping given
above--12, 11, 7. Expressed in powers of 2 we have--
12 = 8 4 - -
11 = 8 - 2 1
7 = - 4 2 1
-------
2 2 2 2
-------
As there are thus two of every power, you must win. Say your opponent
takes 7 from the 12 heap. He then leaves--
5 = - 4 - 1
11 = 8 - 2 1
7 = - 4 2 1
-------
1 2 2 3
-------
Here the powers are not all even in number, but by taking 9 from the 11
heap you immediately restore your winning position, thus--
5 = - 4 - 1
2 = - - 2 -
7 = - 4 2 1
-------
- 2 2 2
-------
And so on to the end. This solution is quite general, and applies to any
number of matches and any number of heaps. A correspondent informs me
that this puzzle game was first propounded by Mr. W.M.F. Mellor, but
when or where it was published I have not been able to ascertain.
