Competition problem — Combinatorics

Library / /102 of 158

Combinatorics Difficulty 6.2 National Olympiad Prove it Estonia

The teacher drew a $3 \times 3$ table in Juku's exercise book and wrote a number in every position of the table. Then he gave Juku the following task.

1. Turn the next page and draw a similar table. Write in the first row the numbers obtained by subtracting the numbers in the third row of the corresponding column from the numbers in the second row of the corresponding column in the previous table. Similarly, the numbers in the second and third row are obtained as differences of the third and the first, and the first and the second row.

2. Turn the next page and draw a new table. Write in the first column the numbers obtained by subtracting the numbers in the third column from the numbers in the second column in the corresponding row in the previous table. Similarly, the numbers in the second and third column are obtained as differences of the third and the first, and the first and the second column.

Repeat in turns steps 1 and 2 until you reach a table where all the numbers are zeroes. Juku has reached the end of the third page and has not yet reached the table with all zeroes in it. Prove that his task never ends.

Solution

First note that after step 1 we get a table where the column sums of the table are $0$ , and after step 2 we get a table where the row sums of the table are $0$ . Suppose that after some steps we reach the table with all zeroes in it. By symmetry we can consider the case where we get this table after step 2. Then the table on the previous step was
$\begin{array}{ccc} a & a & a \\ b & b & b \\ c & c & c \end{array}$
where at least one of the numbers $a$ , $b$ , $c$ is not zero. This table was obtained after step 1, hence $a + b + c = 0$ . The table on the previous step was
$\begin{array}{ccc} d & e & f \\ d-c & e-c & f-c \\ d+b & g+b & f+b \end{array}$
$c + f - c = d + b + g + b + f + b = 0$ . From the first equality it follows that $c = 0$ , from the equality of the first and third expression $b = 0$ , and since $a + b + c = 0$ , we have $a = 0$ , which contradicts the assumption that at least one of the numbers $a, b, c$ is not zero.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.