Problem #PRU-109937

Problems Methods Invariants and semi-invariants Invariants Pigeonhole principle Pigeonhole principle (finite number of poits, lines etc.) Algebraic methods Processes and operations Proof by exhaustion

14–16 4.0

Problem

We are given a table of size $n \times n$ . $n - 1$ of the cells in the table contain the number $1$ . The remainder contain the number $0$ . We are allowed to carry out the following operation on the table:

1. Pick a cell.

2. Subtract 1 from the number in that cell.

3. Add 1 to every other cell in the same row or column as the chosen cell.

Is it possible, using only this operation, to create a table in which all the cells contain the same number?

To see the solution register and get verified.