Browse · MathNet
PrintEstonian Math Competitions
Estonia counting and probability
Problem
A field is a grid with a positive integer written into each cell, such that no number repeats in any row or column. An onion consists of consecutive cells in a row or column, whose numbers add up to exactly . Find the largest possible number of onions on the field.
Solution
Answer: .
In a column of length there are potential onions. However there cannot be two consecutive onions, as they share cells, meaning their fourth numbers would have to be equal. So a column can have at most onions. Analogously a row of length can also have at most onions. As there are rows and columns in total, there can be at most onions.
We will show there exists a field with onions. We will first construct a 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 .
We obtain the desired field by adding to all negative numbers in the grid.
In a column of length there are potential onions. However there cannot be two consecutive onions, as they share cells, meaning their fourth numbers would have to be equal. So a column can have at most onions. Analogously a row of length can also have at most onions. As there are rows and columns in total, there can be at most onions.
We will show there exists a field with onions. We will first construct a 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 .
We obtain the desired field by adding to all negative numbers in the grid.
Final answer
1009 * 4041
Techniques
Coloring schemes, extremal arguments