Maths Olympiad Prep

Library / /7 of 7

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Greece

Decide whether the integers 1,2,,1001, 2, \ldots, 100 can be arranged in the cells C(i,j)C(i,j) of a 10×1010 \times 10 matrix (where 1i,j101 \le i, j \le 10), such that the following conditions are satisfied:
(i) In every row, the entries add up to the same sum SS.
(ii) In every column, the entries also add up to this sum SS.
(iii) For every k=1,,10k = 1, \dots, 10 the ten entries C(i,j)C(i,j) with ijk(mod10)i-j \equiv k \pmod{10} add up to SS.

Solution

The problem essentially asks for a magic square that satisfies an additional constant-sum property along the wrap-around diagonals.
Suppose that such an arrangement of 1,2,,1001, 2, \ldots, 100 is possible. Since the sum of all entries is 12100101\frac{1}{2} \cdot 100 \cdot 101, we get that S=505S = 505 is an odd number. We partition the cells C(i,j)C(i,j) into four sets: Set AA contains the cells with ii and jj both odd; set BB contains the cells with odd ii and even jj; set CC contains the cells with even ii and odd jj; and set DD contains the remaining cells with ii and jj both even. We denote the sum of all entries in A,B,C,DA, B, C, D by SA,SB,SC,SDS_A, S_B, S_C, S_D, respectively.
* Since AA and BB contain all cells in the odd rows, we get SA+SB=5SS_A + S_B = 5S.
* Since BB and DD contain all cells in the even columns, we get SB+SD=5SS_B + S_D = 5S.
* Since AA and DD contain all cells C(i,j)C(i,j) with even iji-j, we get SA+SD=5SS_A + S_D = 5S.
Adding up these three equations yields 2(SA+SB+SD)=15S2(S_A + S_B + S_D) = 15S. Since in this equation the left hand side is even and the right hand side is odd, we have the desired contradiction.

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 and solution reproduced as published; topic and difficulty added by this site.