Solution:
Let a1,a2,a3,…,a2024 be the number of red dots in rows 1,2,3,…,2024 respectively. So 0⩽ai⩽40 for each i.
For each of the (240)=780 pairs of columns, there can be at most one row with a red dot in both columns. Therefore we must have
(2a1)+(2a2)+(2a3)+⋯+(2a2024)≤(240)=780.
And hence there is always guaranteed to be at least 2024−780 indices with ai⩽1—i.e. at least 2024−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 aj⩾3 for some index j. Let c1, c2 and c3 be three of the columns where row j has a red dot. Let r1 and r2 be any two rows which each currently contain one red dot. Consider the following operation:
- Remove the dot in row j and column c3.
- Remove the dots in rows r1 and r2 (at most two dots removed).
- Add dots in columns c1 and c3 in row r1.
- Add dots in columns c2 and c3 in row r2.
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 ai⩽2 for all i. Now if there were more than 780 rows with two red dots in it (i.e. ai=2 for more than 780 indices i), 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.
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.