Maths Olympiad Prep

Library / /252 of 397

, 2021

Combinatorics Difficulty 6.2 National Olympiad Prove it Taiwan

C. Let nn and kk be positive integers satisfying k2n2k \le 2n^2. Lee and Sunny play a game with a 2n×2n2n \times 2n 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 kk. 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 MM be the final number of pieces. Lee wants to maximize MM, while Sunny wants to minimize MM. Find the value of MM when Lee and Sunny both play optimally.

Solution

The answer is 2k12k-1. Let us consider the strategies of the two players in order.

- For Lee, he can write 12+ϵ\frac{1}{2}+\epsilon in 2k12k-1 cells, write 12(2k1)ϵ\frac{1}{2}-(2k-1)\epsilon in one cell, and fill the rest with 0. Since each piece can contain at most one cell with 12+ϵ\frac{1}{2}+\epsilon written in it, Lee can use this strategy to guarantee M2k1M \ge 2k-1.

- 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 a1,a2,,a4n2a_1, a_2, \dots, a_{4n^2}. Sunny's strategy is as follows: starting from a1a_1, find the largest positive integer MM such that i=1Mai1\sum_{i=1}^M a_i \le 1, and cut a1a_1 through aMa_M into one piece. Then, starting from aM+1a_{M+1}, repeat the same action, until finished.
Let us prove that the above strategy will cut out at most 2k12k-1 pieces. Suppose that in the end t2kt \ge 2k pieces are cut out, and let the sum of the numbers on each piece be b1,b2,,btb_1, b_2, \dots, b_t. By the strategy, we know that bi+bi+1>1b_i + b_{i+1} > 1 (otherwise they would be placed in the same piece). But then,
k=t=1kbii=1k(b2i1+b2i)>k, k = \sum_{t=1}^{k} b_i \ge \sum_{i=1}^{k} (b_{2i-1} + b_{2i}) > k,
a contradiction! Hence Sunny can guarantee M2k1M \le 2k-1.

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 translated into English from zh; metadata (topic, difficulty) added by this project.