Maths Olympiad Prep

Library / /29 of 41

Combinatorics Difficulty 6.2 National Olympiad Prove it New Zealand

Problem:

Some of the 80960 lattice points in a 40×202440 \times 2024 lattice are coloured red. It is known that no four red lattice points are vertices of a rectangle with sides parallel to the axes of the lattice. What is the maximum possible number of red points in the lattice?

Solution

Solution:

Let a1,a2,a3,,a2024a_{1}, a_{2}, a_{3}, \ldots, a_{2024} be the number of red dots in rows 1,2,3,,20241, 2, 3, \ldots, 2024 respectively. So 0ai400 \leqslant a_{i} \leqslant 40 for each ii.

For each of the (402)=780\binom{40}{2} = 780 pairs of columns, there can be at most one row with a red dot in both columns. Therefore we must have

(a12)+(a22)+(a32)++(a20242)(402)=780. \binom{a_{1}}{2} + \binom{a_{2}}{2} + \binom{a_{3}}{2} + \cdots + \binom{a_{2024}}{2} \leq \binom{40}{2} = 780.

And hence there is always guaranteed to be at least 20247802024 - 780 indices with ai1a_{i} \leqslant 1—i.e. at least 2024780=12442024 - 780 = 1244 rows have at most one red dot in it.

Now consider an arrangement in which the total number of red dots is maximised, and suppose for the sake of contradiction that aj3a_{j} \geqslant 3 for some index jj. Let c1c_{1}, c2c_{2} and c3c_{3} be three of the columns where row jj has a red dot. Let r1r_{1} and r2r_{2} be any two rows which each currently contain one red dot. Consider the following operation:

- Remove the dot in row jj and column c3c_{3}.
- Remove the dots in rows r1r_{1} and r2r_{2} (at most two dots removed).
- Add dots in columns c1c_{1} and c3c_{3} in row r1r_{1}.
- Add dots in columns c2c_{2} and c3c_{3} in row r2r_{2}.

This operation will increase the total number of dots, which contradicts the assumption that a row with at least 3 dots exists in a maximal arrangement.

Henceforth we assume ai2a_{i} \leqslant 2 for all ii. Now if there were more than 780 rows with two red dots in it (i.e. ai=2a_{i} = 2 for more than 780 indices ii), then by the pigeonhole principle, there would be two rows with dots in the same pair of columns and this would be a contradiction. Therefore there are at most 780 rows with two dots in it. Hence the total number of dots is at most

780×2+1244×1=2804. 780 \times 2 + 1244 \times 1 = 2804.

To achieve this, let the first 780 rows each have a unique pair of columns in which their red dots lie. And the remaining 1244 rows each contain a single dot in the first column only.

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.