Competition problem — Combinatorics

Library / /47 of 86

Combinatorics Difficulty 6.0 AIME, harder Prove it Estonia

A field is a $2020 \times 2021$ grid with a positive integer written into each cell, such that no number repeats in any row or column. An onion consists of $4$ consecutive cells in a row or column, whose numbers add up to exactly $4 \cdot 2021$ . Find the largest possible number of onions on the field.

Solution

*Answer:* $1009 \cdot 4041$ .

In a column of length $2020$ there are $2017$ potential onions. However there cannot be two consecutive onions, as they share $3$ cells, meaning their fourth numbers would have to be equal. So a column can have at most $1009$ onions. Analogously a row of length $2021$ can also have at most $1009$ onions. As there are $2020 + 2021 = 4041$ rows and columns in total, there can be at most $1009 \cdot 4041$ onions.

We will show there exists a field with $1009 \cdot 4041$ onions. We will first construct a $2020 \times 2020$ grid, choosing the first two rows to be

1, -1, 2, -2, 3, -3, ..., 1009, -1009, 1010, -1010,
-1, 1, -2, 2, -3, 3, ..., -1009, 1009, -1010, 1010.

The next two rows will be shifted the cells to the left:

2, -2, 3, -3, ..., 1009, -1009, 1010, -1010, 1, -1,
-2, 2, -3, 3, ..., -1009, 1009, -1010, 1010, -1, 1.

Similarly we construct the other rows. Finally we add the rightmost column consisting of the numbers
$1011, -1011, 1012, -1012, \dots, 2019, -2019, 2020, -2020$ .

We obtain the desired field by adding $2 \cdot 2021$ to all negative numbers in the grid.

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 and solution reproduced as published; topic and difficulty added by this site.