Maths Olympiad Prep

Library / /33 of 48

, 2013

Combinatorics Difficulty 6.1 National Olympiad Prove it Baltic Way

For which positive integers kk can the integers 1,2,3,,(2k)21, 2, 3, \dots, (2k)^2 be arranged as a 2k×2k2k \times 2k table in such a way that all row sums and column sums were of the same parity, opposite to that of kk?

Solution

Answer: for all k2k \ge 2.

Solution:
Such an arrangement is impossible for k=1k = 1. In order to make all row sums and column sums even, both odd numbers should occur in the same row and also in the same column, which is impossible. In the rest, let 00 and 11 denote any even and odd number, respectively. For k=2k = 2, one suitable arrangement is shown below:
1110110110000100 \begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}
We now show how to obtain a suitable arrangement for k+1k + 1 from any suitable arrangement for kk. Add 00, 11 to the end of the first k1k - 1 rows and add 11, 00 to the end of the following k+1k + 1 rows. This fills the 2k×22k \times 2 strip appearing in the right end of the table. Fill the 2×2k2 \times 2k strip below the original part of the table similarly. Let the remaining 2×22 \times 2 corner be 0110\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}. Then the parity of the sum of each old row and column is inverted. Each new column or row contains either kk or k+2k + 2 odd numbers, whence the parity of the row and column sums is the opposite to that of k+1k + 1. Hence the extended table meets the requirements.

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.