Skip to main content
OlympiadHQ

Browse · MathNet

Print

TST

Vietnam counting and probability

Problem

In a board of grids, we pick unit squares such that every picked square shares at least one vertex with at most one other picked square. Determine the maximum of .

problem
Solution
We say two squares are connected if they share at least one vertex. The condition states that every picked square is connected to at most one other picked square. Hence, the set of picked squares can be partitioned into many connected components, where each component contains at most two squares that are connected to each other, and any two different components are totally disconnected. Note that this is true since it's impossible to have a connected component that has at least three picked squares, since then there will be a picked square that is connected to at least two other ones, which gives a contradiction.

Since each component contains at most two squares that are connected, we can easily see that there are only three possible chances for a connected component, up to reflection and rotation, displayed as in the below figure.



Denote the number of components of the first, second, and third forms from the left to the right by , and . For each component, we extend the area of it to each side of the squares by a length of (displayed by the light blue region in the figure). The extended area of the three components will be , , and respectively. Since any different components are disconnected, it's impossible to have any overlapping between the extended components, and all the extended components will cover the whole board extended by to each side, which has a total area of . Hence, we have

implying that . To show that it's possible to achieve , we pick the squares of the form

for , , where denotes the grid at row , column . Therefore, the maximum value of is .
Final answer
2022^2/3

Techniques

Coloring schemes, extremal argumentsInvariants / monovariants