Make It All Zeros

There is a positive integer in every cell of a rectangular array. In each move, you may double every number in a row or subtract 1 from each number in a column. Prove that you can reach a table of zeros by a sequence of the permitted moves [Engel, p. 9].

The applet below is to assist you in getting insight into the problem. To perform a move click to the left (or right) of a row or below (or above) a column. Since multiplying by 2 repeated causes the numbers to grow pretty fast so that reducing them back to a small size becomes a tedious task, you may want to check the "Speed up" box. The effect is then that the applet automatically will subtract as many 1s so as to make the smallest number in the column 1 (unless there was already at least one 1.)

 

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.

Make It All Zeros


What if applet does not run?

Solution

References

  1. A. Engel, Problem-Solving Strategies, Springer, 1998

Related material
Read more...

  • Expansion of Integers in an Integer Base
  • Base (Binary, Decimal, etc.) Converter
  • Base Converter
  • Implementation of Base Conversion Algorithms
  • Conversion of Fractions in Various Bases
  • Scoring: the simplest of the impartial games
  • History of the Binary System
  • Calculation of the Digits of pi by the Spigot Algorithm of Rabinowitz and Wagon
  • Addition and Multiplication Tables in Various Bases
  • |Activities| |Contact| |Front page| |Contents| |Algebra| |Eye opener|

    Copyright © 1996-2018 Alexander Bogomolny

    Solution

    On first impulse, you may want to get a 0 successively in one cell after another. But this of course does not work. If in a column there are a zero and a non-zero integer, you are stuck because a subsequent subtraction of 1s in this column will turn 0 into -1 and there is no provision to get rid of negative numbers.

    This difficulty suggests that in order to solve the problem you have to vanish all the elements in a column simultaneously; one column at a time. The way to do that is to first get a 1 in the column of your choice. If there happen to be a few of them (in that column) that's just as well. Next, multiply the rows that contain the 1s in that column by 2 and again subtract 1 from the integers in the column. This operation will reduce all the values in the column except for the 1s that were already there. Repeat this pair of operations (perhaps, multiple) multiplications and the subtraction until all zeros emerge.

    After a column has been converted to all zeros you may forget about it and start working on another one.

    (Note that the applet allows you shortcuts to make achieving the goal easier.)

    |Activities| |Contact| |Front page| |Contents| |Algebra| |Eye opener|

    Copyright © 1996-2018 Alexander Bogomolny

    71471575