Olympiad Maths Prep

Library / /24 of 30

Combinatorics Difficulty 6.8 National olympiad Prove it Belarus

Exactly one integer number is written in each cell of an 8×88 \times 8 square table. Per move it is allowed to choose any n×nn \times n square, 1<n<81 < n < 8, and either to increase by 1 or to decrease by 1 all numbers in the cells of the chosen square.
Is it possible to get the table with zeros in all its cells from the arbitrary initial table?
(V. Kaskevich)

Solution

We separate the table into five parts: the central 4×44 \times 4 square, two 2×82 \times 8 rectangles, and two 4×24 \times 2 rectangles (see Fig. 1).
We can obtain the 0's in all cells of the 2×82 \times 8 rectangles. It suffices to show how we can change (increase by 1 or decrease by 1) the value in any cell of the rectangle so that all other cells of this rectangle keep their value. The corresponding procedures using 2×22 \times 2 and 3×33 \times 3 squares are shown in Fig. 2 and Fig. 3.

Figure 1

Figure 2
Fig. 3

In similar way we can change (increase by 1 or decrease by 1) the value in any cell of the 2×42 \times 4 rectangles. It suffices to show how we can change the value in any cell of these rectangles so that all other cells of these rectangles and all cells of the 2×82 \times 8 rectangles keep their value. The corresponding procedures are shown in Fig. 4 (see, in addition, Fig 3).

Figure 3

It remains to change the numbers in the cells of the central 4×44 \times 4 square. It suffices to show how we can change the value of any cell of this square so that all other cells of the table keep their value. The corresponding procedures are shown in Fig. 5.

Figure 4
Fig. 5

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.