C. Let and be positive integers satisfying . Lee and Sunny play a game with a grid paper. First, Lee writes a non-negative real number no greater than 1 in each of the cell, so that the sum of all numbers on the paper is . Then, Sunny divides the paper into few pieces such that each piece is constructed by several complete cells, and the sum of all numbers on each piece is at most 1. There are no other restrictions on the shape of each piece.
Let be the final number of pieces. Lee wants to maximize , while Sunny wants to minimize . Find the value of when Lee and Sunny both play optimally.
, 2021
Solution
The answer is . Let us consider the strategies of the two players in order.
- For Lee, he can write in cells, write in one cell, and fill the rest with 0. Since each piece can contain at most one cell with written in it, Lee can use this strategy to guarantee .
- For Sunny, he first chooses a path that passes through all the cells in one stroke, and suppose the numbers on this path, in order, are . Sunny's strategy is as follows: starting from , find the largest positive integer such that , and cut through into one piece. Then, starting from , repeat the same action, until finished.
Let us prove that the above strategy will cut out at most pieces. Suppose that in the end pieces are cut out, and let the sum of the numbers on each piece be . By the strategy, we know that (otherwise they would be placed in the same piece). But then,
a contradiction! Hence Sunny can guarantee .