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.)
| Buy this applet What if applet does not run? |
References
- A. Engel, Problem-Solving Strategies, Springer, 1998
|Activities| |Contact| |Front page| |Contents| |Algebra| |Eye opener| |Store|
Copyright © 1996-2015 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| |Store|
Copyright © 1996-2015 Alexander Bogomolny
| 49552170 |
