There's infinity of the following blocks on the table:$1*1 , 1*2 , 1*3 ,.., 1*n$. We have a $n*n$ table and Ali chooses some of these blocks so that the sum of their area is at least $n^2$. Then , Amir tries to cover the $n*n$ table so that none of blocks go out of the table and they don't overlap and he wanna maximize the covered area in the $n*n$ table with those blocks chosen by Ali. Let $k$ be the maximum coverable area independent of Ali's choice. Prove that: $$n^2 - \lceil \frac{n^2}{4} \rceil \leq k \leq n^2 - \lfloor \frac{n^2}{8} \rfloor$$ *Note : the blocks can be placed only vertically or horizontally.
Problem
Source: Iran MO 2023 3rd round , Combinatorics exam P3
Tags: combinatorics, ceiling function
Infinityfun
14.02.2024 15:41
Bump!!??
ayeen_izady
27.06.2024 20:08
Here is the official solution: Claim 1: $k\ge n^2-\lceil \frac{n^2}{4}\rceil$ Proof: Consider all blocks that have length at most $\frac{n}{2}$. Each time consider two of them and by taking them together, make a new block (if their length were $r$ and $s$, the new block will be $1\times (r+s)$). Continue this operation till there is at most $1$ block with length at most $\frac{n}{2}$. Then place the blocks in decreasing order from the top right corner, horizontally, till you reach the lowest row, then continue from the bottom left corner and place the blocks vertically till they overlap. If the last block that placed has length not more than $\frac{n}{2}$ we easily get that $k\ge n^2-\frac{n}{2}\ge n^2-\lceil\frac{n^2}{4}\rceil$. Assume otherwise, the block we could not place's length is $n>x\ge \frac{n}{2}$ and the last block's length is $y\ge x$, thus $k\ge ny+(n-y)x$. You can check that it gives the result. Claim 2: $k\le n^2-\lfloor\frac{n^2}{8}\rfloor$ Proof: if Ali gives Amir $\lfloor\frac{3n}{4}\rfloor$ of $1\times n$ blocks and $\lceil\frac{n}{2}\rceil$ of $1\times (\lfloor\frac{n}{2}\rfloor +1)$ blocks, WLOG assume that all $1\times n$ blocks should be placed horizontally, if we have at least one of the other type of blocks vertically, we get that we've placed at most $\lceil\frac{n}{2}\rceil -1$ numbers of $1\times n$ blocks. So$k\le n\times(\lceil\frac{n}{2}\rceil -1)+\lceil\frac{n}{2}\rceil\times(\lfloor\frac{n}{2}\rfloor +1)<n^2-\lfloor\frac{n^2}{8}\rfloor$. Otherwise, all blocks are placed horizontally, so $k\le \lfloor\frac{3n}{4}\rfloor\times n+(n-\lfloor\frac{3n}{4}\rfloor)\times(\lfloor\frac{n}{2}\rfloor +1)<n^2-\lfloor\frac{n^2}{8}\rfloor $ and we are done.