A Constructive Combinatorics Proof – Mattia Giuri's bizarre blog

There is a positive integer in each square of a rectangular table. In each move, you may double each number in a row or subtract 1 from each number in a column. Can you arrive to a situation where there are only zeros on the table?

How Should These Kind Of Problems Be Approached

In this case, you should try to show a particular situation that can be generalized to solve the problem by finding an algorithm that destroys our table.

The Idea

If we want to get all numbers to zero, this means that each column must become zero at the same time, or, in other words, we have to make all the numbers become a positive integer n and then subtract 1 n times.

A Sort Of Induction

Also, we can consider a $1\cdot n$ table and then generalize to $k \cdot n$ because when we double a number in a column the value of the numbers in its row increases, so there’s no risk of making it negative.

Further Making The Problem Easy

Finally, we can consider only two numbers because when they become equal, then it’s like we eliminated a number from our column and we just make the same moves for both of them (It’s important to notice that we MUST keep the other numbers positive, but it’s not a problem since you can double a number in a column as you like, so let’s assume that we are keeping all of our numbers positive).

Proof

If we have equal integers, we don’t mind, we just make the same move for each of them, so let’s assume we have two integers $a,2^n + b$ . What we want to do is making them equal, so let’s increase the second one until $2^k \cdot b > a$ . By doing so, we can do this algorithm: we subtract one from the column (with the right attention) until $a$ becomes 1. Then we can multiply it by 2 and subtract 1 again, and basically what we obtain is that we can lower the value of $2^k \cdot b$ as much as we like. Once $2^k\cdot b$ becomes 0, $a$ will still be 1, but the other integer will be of the form $2^{n+k}$ , so we can make the two of them equal by multiplying $a$ by $2^{n+k}$ . So by doing so, we have the proof that we can make all the numbers in a column zeros. But once you move to another column, the numbers in the previous column will keep being 0 as $2\cdot0 = 0$ , so we can cut the first column and the proof is complete by induction.