Browse · MathNet
PrintArgentina_2018
Argentina 2018 counting and probability
Problem
Facu and Nico play the following game with a grid square. Facu cuts the square into rectangles having a side equal to , in any way he wishes. Then Nico chooses a number among and takes all the obtained rectangles . How many grid cells can he take with certainty?
Solution
Nico can always ensure cells. Suppose that there is a partition like in the statement so that no cells can be taken. Then this partition has at most rectangle for each ; at most such rectangles for ; at most such rectangles for ; at most such rectangles , at most rectangles and at most unit cells . Consequently the total area does not exceed
This is false because the square has area . Therefore cells can be taken regardless of how Facu plays.
On the other hand cells are not always achievable. Here is an example. The first row is untouched; the next are cut as follows:
Rows and are and ; row is cut into unit cells. In summary, the answer is cells.
This is false because the square has area . Therefore cells can be taken regardless of how Facu plays.
On the other hand cells are not always achievable. Here is an example. The first row is untouched; the next are cut as follows:
Rows and are and ; row is cut into unit cells. In summary, the answer is cells.
Final answer
16
Techniques
Counting two waysGames / greedy algorithms