XXXIII OM - I - Problem 9

In a chessboard created by dividing a square of side length $ n $ into unit squares using lines parallel to the sides of the square, we consider all squares whose sides are contained in the lines forming the chessboard. Let $ 1 \leq k \leq n $ and $ P(k,n) $ denote the number of these squares whose side lengths do not exceed $ k $. Let $ k(n) $ be the largest of such numbers $ k $ for which $ P(k, n) \leq \frac{1}{2} P(n, n) $. Calculate $ \lim_{n\to \infty} \frac{k(n)}{n} $.
On the side of the chessboard, there are $ n - k + 1 $ segments of length $ k $ with endpoints at the division points. Hence, the total number of squares of side length $ k $ contained in the lines forming the chessboard is $ (n - k + 1)^2 $. Therefore, we have the following formulas:

The number $ k(n) $ satisfies the inequality

Thus

Multiplying by $ - \frac{1}{n^3} $ the difference of the obtained inequality and $ n(n + 1)(2n + 1) $, we have:

The above inequality takes the form

where $ a_n = 1 - \frac{k(n)}{n} $.
We will prove that the sequence $ \left( 2a_n \left( a_n + \frac{1}{n} \right) \left( a_n + \frac{1}{2n} \right) \right) $ converges to the number $ 1 $. If this were not the case, then in view of inequality (*) and the fact that $ \displaystyle \lim_{n \to \infty} \left( 1 + \frac{1}{n} \right) \left( 1 + \frac{1}{2n} \right) = 1 $, we would have

Let us take $ n_0 $ so large that for every $ n \geq n_0 $ the conditions

are satisfied.
Since

we have the inequality

Based on the last inequality and (***), we obtain

This is contradictory to condition (**). The contradiction arose from the assumption that the number $ 1 $ is not the limit of the sequence $ 2a_n \left( a_n + \frac{1}{n} \right) \left( a_n + \frac{1}{2n} \right) $. Therefore, the limit of this sequence exists and is equal to $ 1 $. Similarly, we conclude that the sequence $ \left( 2a_n \left( a_n - \frac{1}{n} \right) \left( a_n - \frac{1}{2n} \right) \right) $ also converges to $ 1 $. Given the obvious inequality

we obtain, based on the theorem of three sequences, that

Since $ \frac{k(n)}{n} = 1 - a_n $ and $ \displaystyle \lim_{n \to \infty} a_n = \frac{1}{\sqrt[3]{2}} $, we have