MathDB

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 Statement