Bulgarian National Mathematical Olympiad

Answer: 101. We shall prove the following more general assertion.

Lemma. Some of the squares of a table $P$ are colored blue. A partition of $P$ into rectangles of integer sides is called good if every rectangle contains exactly one blue square. Then $P$ possesses a unique good partition if and only if the blue squares form a rectangle.

Proof. It is easy to see that if the blue squares form a rectangle, there is only one good partition (there are unique choices for the angle squares of the blue rectangle, then for the remaining boundary squares and finally for the inner squares).

We now consider the other direction. Let us denote the unique good partition of $P$ by $S$. We call dividing any (vertical or horizontal) line which cuts the table into two rectangles each of them containing at least one blue square.

We first prove that every sub-rectangle $\Pi$ which contains at least one blue square possesses good partition. We go by induction on the number of the blue squares in $\Pi$. The assertion is obvious for a single blue square. For more blue squares we cut $\Pi$ into two smaller rectangles ${\Pi }_1$ and ${\Pi }_2$, each of them containing blue square(s) and apply the induction hypothesis.

It follows from the above that every dividing line $\ell$ determines good partition which includes the line $\ell$. Therefore every dividing line is included in the partition $S$.

Let ${\ell }_1,{\ell }_2,\dots ,{\ell }_p$ be all vertical dividing lines (from left to right end) and $m_1,m_2,\dots ,m_q$ are all horizontal dividing lines (from bottom to upper end). Then these lines divide the table into rectangles, each of them containing at most one blue square. Therefore $S$ does not include any lines different from these and, in fact, every rectangle contains exactly one blue square.

Let ${\ell }_0$ be the rightmost vertical line such that there are no blue squares on its left side, ${\ell }_{p+1}$ is the leftmost vertical line such that there are no blue squares on its right side, and $m_0$ and $m_{q+1}$ are defined analogously. It is clear that the distance between ${\ell }_i$ and ${\ell }_{i+1}$ equals 1 for every $0\le i\le p$ and, analogously, the distance between $m_j$ and $m_{j+1}$ equals 1 for every $0\le j\le q$ (otherwise further dividing lines could be added). Therefore the set of the blue squares coincides with the rectangle defined from the lines ${\ell }_0,{\ell }_{p+1},m_0$ and $m_{q+1}$, which completes the proof of the lemma.

In our problem, we see that the 101 blue squares form a rectangle. Moreover, one of the sides of this rectangle must be 1, and the other one, equal to 101, must be equal to $n$.