Задача из журнала «Квант» (2000 год, 1 выпуск)

Условие

В квадрате клетчатой бумаги размером $n\times n$ клеток отмечены $N$ клеток таким образом, что каждая клетка квадрата (отмеченная или не отмеченная) имеет хотя бы одну отмеченную соседнюю клетку. Определите наименьшее возможное значение $N$, если соседними считать клетки, имеющие общую сторону.

Решение

Рассмотрим случай четного $n$.

Сначала раскрасим доску в черный и белый цвета в шахматном порядке. Пусть $f\left(n\right)$ — это искомое число, а $f_{\omega}\left(n\right)$ — минимальное число белых клеток, которые должны быть отмечены таким образом, чтобы каждая черная клетка имела соседнюю отмеченную белую. Определим подобным образом $f_{b}\left(n\right).$ Благодаря симметричности шахматной доски $\left(n = 2k\right)$, мы имеем $f_{\omega}\left(n\right) = f_{b}\left(n\right)$; кроме этого, $f\left(n\right) = f_{\omega}\left(n\right) + f_{b}\left(n\right)$.

Было бы более удобно посмотреть на доску, развернув ее таким образом, чтобы главная черная диагональ (самая длинная) располагалась горизонтально. Тогда длины остальных черных диагоналей были бы $2, 4, \ldots, 2k, \ldots, 4, 2.$

Зачеркнем «нечетные» клетки белых диагоналей, расположенных под черными диагоналями длины $4i — 2$ в первом случае и под черными диагоналями длины $4i + 2$ во втором случае (см. рисунок).

В первом случае зачеркнутыми окажутся $2i$ белых клеток, а во втором случае $2i + 1$ белых клеток. Таким образом, всего мы зачеркнем
$$2 + 4 + \ldots + k + \ldots + 3 + 1 = \frac{k\left(k+1\right)}{2}$$
белых клеток. Легко видеть, что каждая черная клетка имеет белую зачеркнутую соседнюю клетку. Из этого следует, что
$$f_{\omega}\left(n\right) \leqslant \frac{k\left(k+1\right)}{2}.$$

Рассмотрим $\displaystyle\frac{k\left(k+1\right)}{2}$ зачеркнутых белых клеток: у них нет общих черных соседних клеток, следовательно, нам нужно по крайней мере $\displaystyle\frac{k\left(k+1\right)}{2}$ черных отмеченных клеток с тем, чтобы «охватить» все эти белые клетки. Поэтому
$$f_{b}\left(n\right) \geqslant \frac{k\left(k+1\right)}{2}.$$
Отсюда мы имеем
$$f_{\omega}\left(n\right) = f_{b}\left(n\right) = \frac{k\left(k+1\right)}{2},$$
$$f\left(n\right) = k\left(k+1\right).$$

Аналогично доказывается, что
\begin{equation*}
f\left(n\right) =
\begin{cases}
4k^2 — 1 &\text{при $n = 4k — 1$,}\\
\left(2k + 1\right)^2 &\text{при $n = 4k + 1$.}
\end{cases}
\end{equation*}

Е. Баранов, И. Воронович

Задача из журнала «Квант» (2000 год, 1 выпуск)

Условие

Последовательность $a_{1}$, $a_{2}$, $a_{3}$, $\ldots$ задана своим первым членом $a_{1} = 1$ и рекуррентной формулой $\displaystyle a_{n+1} = a_{n} + \frac{1}{a_{n}}$, где $n = 1, 2, 3, \ldots$

1. Докажите, что $a_{100} > 14$.
2. Найдите $\lbrack a_{1000}\rbrack$, то есть укажите такое целое число $m$, для которого $m \leqslant a_{1000} < m + 1$.
3. Докажите существование и найдите значение предела $\displaystyle\lim\limits_{n \to \infty} \frac{a_{n}}{\sqrt{n}}$.

Решение

1. Возводим равенство $\displaystyle a_{n+1} = a_{n} + \frac{1}{a_{n}}$ в квадрат и «отбрасываем лишнее»: $$a_{n+1}^{2} = a_{n}^{2} + 2 + \frac{1}{a_{n}^{2}} > {a_{n}^{2}} + 2.$$ Вспомнив, что $a_{1}^{2} = 1$, получаем одно за другим неравенства $a_{2}^{2} > a_{1}^{2} + 2 = 3$, $a_{3}^{2} > a_{2}^{2} + 2 > 3 + 2 = 5$, и вообще (при $n > 1$), $$\begin{equation}\label{m1719_first} a_{n}^{2} > 2n — 1\end{equation}.$$ В частности, $a_{100}^{2} > 199 > 196 > 14^{2}$, что и требовалось.
2. Ответ: $\lbrack a_{1000}\rbrack = 44$.

   При $n = 1000$ неравенство $\eqref{m1719_first}$ дает $a_{1000}^{2} > 1999 > 44^{2}$, так что $\lbrack a_{1000}\rbrack \geqslant 44$. Чтобы получить оценку сверху, введем величины $b_{n}$, такие что $a_{n}^{2} = 2n — 1 + b_{n}$. В силу неравенства $\eqref{m1719_first}$, имеем $b_{n} > 0$ при $n > 1$. Далее, запишем формулу $\displaystyle a_{n+1}^{2} = a_{n}^{2} + 2 + \frac{1}{a_{n}^{2}}$ в виде
   $$2n + 1 + b_{n+1} = 2n — 1 + b_{n} + 2 + \frac{1}{2n — 1 + b_{n}},$$
   откуда
   $$b_{n+1} = b_{n} + \frac{1}{2n — 1 + b_{n}} \leqslant b_{n} + \frac{1}{2n — 1}.$$

   По индукции из последнего неравенства следует, что
   $$b_{n+1} \leqslant b_{1} + \frac{1}{1} + \frac{1}{3} + \ldots + \frac{1}{2n — 3} + \frac{1}{2n — 1}. $$
   Поскольку $b_{1} = 0$, имеем, в частности,
   $$b_{1000} \leqslant 1 + \frac{1}{3} + \frac{1}{5} + \ldots + \frac{1}{1995} + \frac{1}{1997}.$$
   Осталось оценить сумму, оказавшуюся в правой части последнего неравенства. Сгруппируем слагаемые:
   $$b_{1000} \leqslant 1 + \left(\frac{1}{3} + \frac{1}{5} + \frac{1}{7}\right) + \left(\frac{1}{9} + \frac{1}{11} + \frac{1}{13} + \frac{1}{15} + \ldots + \frac{1}{25}\right) + \\ + \left(\frac{1}{27} + \frac{1}{29} + \frac{1}{31} + \frac{1}{33} + \ldots + \frac{1}{79}\right) + \left(\frac{1}{81} + \frac{1}{83} + \ldots + \frac{1}{241}\right) + \\ + \left(\frac{1}{243} + \frac{1}{245} + \ldots + \frac{1}{727}\right) + \left(\frac{1}{729} + \frac{1}{731} + \ldots + \frac{1}{1997}\right).$$
   (Принцип очень простой: в первой скобке три слагаемых, наибольшее из которых равно $\displaystyle\frac{1}{3}$; во второй — девять, наибольшее из которых $\displaystyle\frac{1}{9}$; …; в пятой — $243$ слагаемых, наибольшее $\displaystyle\frac{1}{243}$; наконец, в шестой скобке наибольшее слагаемое равно $\displaystyle\frac{1}{729}$, а слагаемых всего лишь $635$.) Следовательно, $b_{1000} < 7$. Это позволяет утверждать, что $$a_{1000}^{2} < 2000 - 1 + 7 < 2025 = 45^2,$$ откуда $a_{1000} < 45$.

3. Использованный при решении пункта б) прием позволяет доказать, что $\displaystyle\lim\limits_{n\to \infty}\frac{b_{n}}{n} = 0.$ Поскольку $a_{n} = \sqrt{2n — 1 + b_{n}}$, получаем ответ:
   $$\displaystyle\lim_{n \to \infty} \frac{a_{n}}{\sqrt{n}} = \sqrt{2}.$$

А. Спивак