Subtraction in a Rectangular Array

Here is a problem from a lovely Russian book Mathematical Temptations by the master math popularizer B. A. Kordemsky (Publishing House ONIKS, 2000):

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:

3x3 bird cages

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.

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag!

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Subtraction in a Rectangular Array


What if applet does not run?

My question is to find the necessary and sufficient conditions for the solvability of an N×M configuration of non-negative integers.

|Contact| |Front page| |Contents| |Arithmetic |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny

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.

  1. 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:

    3x3 bird cages

  2. 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:

unsolvable 4x4 bird cages

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

unsolvable 4x4 bird cages that does not satisfy the necessary conditions

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|

Copyright © 1996-2018 Alexander Bogomolny

71471404