Let $n$ and $k$ be positive integers satisfying $k\leq2n^2$. Lee and Sunny play a game with a $2n\times2n$ grid paper. First, Lee writes a non-negative real number no greater than $1$ in each of the cells, so that the sum of all numbers on the paper is $k$. Then, Sunny divides the paper into few pieces such that each piece is constructed by several complete and connected cells, and the sum of all numbers on each piece is at most $1$. There are no restrictions on the shape of each piece. (Cells are connected if they share a common edge.) Let $M$ be the number of pieces. Lee wants to maximize $M$, while Sunny wants to minimize $M$. Find the value of $M$ when Lee and Sunny both play optimally.
Problem
Source: 2021 Taiwan TST Round 1 Independent Study 1-C
Tags: combinatorics, Game Theory, Taiwan
18.03.2021 09:13
Related problem: https://artofproblemsolving.com/community/c6h597127p3543383
22.03.2021 19:44
Just for convenience of the reader, let me put a solution to this problem here:
01.11.2021 06:41
A solution exploiting $2n$ is even (which unfortunately doesn't work if the grid was $\text{odd} \times \text{odd}$): The answer is $2k-1$. The construction is to put numbers $\frac{k}{2k-1}$ is some $2k-1$ cells and $0$ is all the other cells (here we require $2k - 1 \le 4n^2$). Note that any piece must contain at most one non-zero number, and hence there are at least $2k-1$ pieces. Now we prove that $2k-1$ pieces always suffice. Claim (Optimization) : We may Wlog assume that if sum of numbers in some piece is $\le 1$, then it contains at most one non-zero number. Proof: Otherwise, we iterate the numbers in the grid a bit: we put sum of all numbers of that piece in some particular cell of that and put $0$ at other places. It is not hard to note that if we can solve this new problem, then the old problem can also be solved. $\square$ Now denote by $f(i)$ the number of non-zero cells in the $i$-th row and $s(i)$ the sum of numbers in the $i$-th row. Claim: For any $1 \le i \le 2n-1$, we have $s(i) + s(i+1) > \frac{f(i) + f(i+1)}{2}$. Proof: Fix any $i \in \{1,2,\ldots,2n-1\}$. Let $a_1,a_2,\ldots,a_k ; b_1,b_2,\ldots,b_l$ be the non-zero numbers of the $i$-th , $(i+1)$-th row (respectively), from left to right. Note that there is a connnected piece containing the only non-zero numbers $a_j$ and $a_{j+1}$ for any $1 \le j \le k-1$. $b_j$ and $b_{j+1}$ for any $1 \le j \le l-1$. $a_1$ and $b_1$. $a_k,b_l$. Hence we obtain \begin{align*} 2 \Big( s(i) + s(i+1) \Big) &= 2 \Big( (a_1 + a_2 + \cdots a_k) + (b_1 + b_2 + \ldots + b_l) \Big) \\ &= \sum_{j=1}^{k-1} (a_j + a_{j+1}) + \sum_{j=1}^{l-1} (b_j + b_{j+1}) + (a_1 + b_1) + (a_k + b_l) \\ &> \sum_{j=1}^{k-1} 1 + \sum_{j=1}^{l-1} 1 + 1 + 1 = (k-1) + (l-1) + 1 + 1 = k+l = f(i) + f(i+1) \end{align*}This proves our claim. $\square$ Hence we obtain \begin{align*} k &= \Big( s(1) + s(2) \Big) + \Big(s(3) + s(4) \Big) + \cdots + \Big(s(2n-1) + s(2n) \Big) \\ &> \left( \frac{f(1) + f(2)}{2} \right) + \left( \frac{f(3) + f(4)}{2} \right) + \cdots + \left( \frac{f(2n-1) + f(2n)}{2} \right) \\ & = \frac{f(1) + f(2) + \cdots f(2n)}{2} = \frac{\# \text{ non-zero numbers in the table}}{2} \end{align*}It follows that $\# \text{ non-zero numbers in the table}$ is at most $2k-1$. So clearly $2k-1$ pieces suffice. This completes the proof of the problem. $\blacksquare$
26.02.2024 10:10
My solution. $2k-1$ is the solution. Note that Lee can always choose to put $\frac{k}{2k-1}$ on $2k-1$ grids, that way, sunny must divide the paper into at least $2k-1$ pieces, as if two of these grids are in one piece then the sum of which is at least $\frac{2k}{2k-1} > 1$. We now claim that no matter $n, k$, Lee cannot force Sunny to divide the paper into more than $2k-1$ pieces. Choose a connected path that visits all grid- we can further require that the last visited grid connects to the first. For any setup Lee gives, we perform the following algorithm: We keep visiting new grids until the sum of numbers on the grids exceeds $1$, then we cut the visited grids into a full piece of paper, then perform the same steps until we visit all grids. We claim the algorithm terminates before cutting $2k$ pieces, which finishes the problem. If we are left with more than $2k$ pieces, then consider the sum of the grids on the odd # of pieces that was cut, in addition to all the next grids of which the algorithm detects that the sum along with the piece exceeds $1$. This sum is greater than $1 \times k = k$, with all grids counted as most once, a contradiction.