On a warm spring morning a group of kids decided to set free their pet birds. They stacked the birds' cages a 3×3 arrangement, with the number of birds per cage was as shown:
Being in a playful mood, the children decided to proceed in steps, letting out on every step the same number of birds from any two adjacent cages. The kids managed to free all the birds in 5 steps. How did they do that?
The two empty cages make the problem appear overly artificial. Their presence may be looked at as an invitation to generalize. The applet below presents such a generalization.
N×M non-negative integers are arranged in N rows and M columns. At any step you may subtract the same number from any two adjacent cells. Is it always possible to reach the state where all the displayed integers are zero?
To perform a prescribed step click on any cell and then on any adjacent cell. The number that is going to be subtracted is defined by the D spin control at the bottom of the applet. If the numbers in the selected cells are not less than D then D will be subtracted from both. (If you wish this operation repeated automatically check the "Speed subtraction" box.) If any of the two numbers is smaller than D, the smallest of the two will be subtracted instead.
The Necessary and Sufficient Conditions
A property of a N×M arrangement is necessary for the solvability of the puzzle, if any solvable configuration possesses this property. I property if sufficient for the solvability of the puzzle, if every arrangement with this property is solvable.
Two necessary property are practically obvious.
Color the cells in a chessboard-like manner and observe that on every step the same number is subtracted from one black and from one white cell. It follows that, if the configuration is solvable, the totals of the numbers in white and black cells must be equal.
The condition is necessary but not sufficient as the following example shows:
A cell may have 2 (for a corner cell), 3 (for a midside cell), or (otherwise) 4 adjacent neighbors. For a cell in row n and column m, let an,m and sn,m be the number in the cell itself and the sum the numbers a in the adjacent cells. If the puzzle is solvable then necessarily an,m ≤ sn,m, for any n and m.
By itself this condition is not sufficient because it does not enforce the first necessary condition.
Question: Are the two conditions together sufficient for the solvability of a given configuration?
Answer: No, they are not. Here is a counterexample. The following configuration is unsolvable, although it does satisfy the two necessary conditions:
Indeed, to remove the 5 in the upper right corner one should use either 4 or 3 from the adjacent cell on the right. Even assuming it's 3, we arrive at the configuration
that does not satisfy the second necessary condition (it fails it for the 6 in the upper row.)
|Contact|
|Front page|
|Contents|
|Arithmetic
|Eye opener|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
