Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /232 of 359

Taiwan IMO Selection Camp, 2021

Combinatorics Difficulty 6.2 National Olympiad Prove it Taiwan

C. Let nn and kk be positive integers satisfying k≤2n2k \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 2k−12k-1. Let us consider the strategies of the two players in order.

- For Lee, he can write 12+ϵ\frac{1}{2}+\epsilon in 2k−12k-1 cells, write 12−(2k−1)ϵ\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 M≥2k−1M \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=1Mai≤1\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 2k−12k-1 pieces. Suppose that in the end t≥2kt \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=1kbi≥∑i=1k(b2i−1+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 M≤2k−1M \le 2k-1.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge 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.