Olympiad Maths Prep

Track / Stage 6 / 224 of 400 #1224 of 2000

Problem 1224

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

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\times10 matrix (where 1i,j101\le i,j\le 10), such that the following conditions are fullfiled:
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,2,,10k = 1, 2, \ldots, 10 the ten entries C(i,j)C(i, j) with ijkmod10i-j\equiv k\bmod{10} add up to SS.
[i](Proposed by Gerhard Woeginger, Austria)[/i]

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Sum of all entries:
The sum of all integers from 1 to 100 is given by the formula for the sum of an arithmetic series:
k=1100k=1001012=5050 \sum_{k=1}^{100} k = \frac{100 \cdot 101}{2} = 5050
Since there are 10 rows and 10 columns, the sum of the entries in each row and each column must be the same, denoted by S S . Therefore, we have:
10S=5050    S=505 10S = 5050 \implies S = 505

2. Partitioning the cells:
We partition the cells C(i,j) C(i, j) into four sets:
- Set A A contains cells where both i i and j j are odd.
- Set B B contains cells where i i is odd and j j is even.
- Set C C contains cells where i i is even and j j is odd.
- Set D D contains cells where both i i and j j are even.

3. Sum of entries in each set:
Let SA,SB,SC,SD S_A, S_B, S_C, S_D denote the sum of all entries in sets A,B,C,D A, B, C, D respectively.

4. Equations based on the conditions:
- Since A A and B B together contain all cells in the odd rows, we have:
SA+SB=5S S_A + S_B = 5S
- Since B B and D D together contain all cells in the even columns, we have:
SB+SD=5S S_B + S_D = 5S
- Since A A and D D together contain all cells C(i,j) C(i, j) with even ij i - j , we have:
SA+SD=5S S_A + S_D = 5S

5. Adding the equations:
Adding the three equations, we get:
(SA+SB)+(SB+SD)+(SA+SD)=15S (S_A + S_B) + (S_B + S_D) + (S_A + S_D) = 15S
Simplifying, we obtain:
2(SA+SB+SD)=15S 2(S_A + S_B + S_D) = 15S
Since S=505 S = 505 , which is an odd number, the right-hand side of the equation is odd:
15S=15505=7575 15S = 15 \cdot 505 = 7575
The left-hand side, 2(SA+SB+SD) 2(S_A + S_B + S_D) , is even because it is twice a sum of integers. This leads to a contradiction because an even number cannot equal an odd number.

Therefore, the assumption that such an arrangement is possible leads to a contradiction.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.