Competition problem — Combinatorics

Library / /170 of 397

Combinatorics Difficulty 5.6 AIME, harder Prove it Taiwan

There's a $6 \times 6$ chess board, which we label the squares in the first column by $(1,1), (1,2), \cdots, (1,6)$ , and label the other squares similarly. For every $k = 0,1,\cdots,5$ , all squares $(i-j)$ satisfying $i-j \equiv k \pmod 6$ form a diagonal; therefore, there are six diagonals. Decide whether we can write $1,2,\cdots,36$ on the chess board so that the all following conditions hold:
(1) The sums for each column are the same.
(2) The sums of each row are the same.
(3) The sums of each diagonal are the same.

Solution

Impossible. Proof by contradiction: suppose we can fill it successfully, then this sum must be
$S = \frac{1}{6}(1 + 2 + \cdots + 36) = 111.$
Divide the $6 \times 6$ squares into four categories:
1. A: squares whose coordinates are (odd, odd).
2. B: squares whose coordinates are (odd, even).
3. C: squares whose coordinates are (even, odd).
4. D: squares whose coordinates are (even, even).
Then by the assumption of the problem, $A + B = 3S$ , $B + D = 3S$ , $A + D = 3S$ , and adding them all together gives
$2(A + B + D) = 9S,$
but the left side is even while the right side is odd, a 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 translated into English from zh; metadata (topic, difficulty) added by this project.