Maths Olympiad Prep

Library / /11 of 18

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Determine whether there exists a 2011×20112011 \times 2011 matrix with the following properties:
- Every cell is filled with an integer from 11 to 40214021.
- For every integer ii (1i20111 \leq i \leq 2011), the iith row and the iith column together contain every integer from 11 to 40214021.

Solution

Solution:

Answer: no. Fix an integer kk from 11 to 40214021. Let us say that an index ii "hits" a cell containing the number kk if the cell is in either the iith row or the iith column. The conditions stipulate that each index hits exactly one instance of kk, so the total number of hits is 40214021. On the other hand, every cell not lying on the main diagonal is hit by exactly two indices (its row number and its column number), while those on the diagonal are hit only once. In particular, to create an odd total number of hits, kk must appear on the diagonal. This is a contradiction since there are 40214021 permissible values of kk and only 20112011 spots on the diagonal.

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.