Множество всех натуральных чисел является объединением двух непересекающихся подмножеств $\{f(1),f(2),\ldots,f(n),\ldots\}$, $\{g(1),g(2),\ldots,g(n),\ldots\}$, где $f(1)\lt f(2)\lt\ldots\lt f(n)\lt\ldots$, $g(1)\lt g(2)\lt\ldots\lt g(n)\lt\ldots$ и $g(n)=f(f(n))+1$ для всех $n\ge1$. Определите $f(240)$.
Международная математическая олимпиада школьников (XX, 1978 год)
Обозначим множества $\{f(n)\}$ и $\{g(n)\}$ через $F$ и $G$ (по условию $F\cap G=\varnothing$ и $F\cup G=\mathbb{N}$). Начав с первых натуральных чисел 1, 2, 3, $\ldots$, легко последовательно выяснить, к какому из множеств $F$ или $G$ следует отнести очередное натуральное число и какому номеру $n$ оно соответствует в своём множестве: ясно, что $1=f(1)$, поэтому $2=f(f(1))+1=g(1)$; далее, $3=f(2)$, $4=f(3)$, $5=f(f(2))+1=g(2)$, $\ldots$ (таблица 1). При этом мы пользуемся условием $g(n)=f(f(n))+1$ — очередное $g(n)$ ставим сразу после того, как поставлено $f(f(n))$.
Таким образом, $f(n)$ и $g(n)$ определяются однозначно, и в принципе можно решить задачу, просто продолжив таблицу до 240-й строки. Однако это утомительно и неинтересно. Можно сэкономить время, подметив появившиеся закономерности:
разность$f(n+1)-f(n)$ равна всегда 1 или 2, причём
$$
f(n+1)-f(n)=\begin{cases}
1,&\text{если}~n\in G, \\
2,&\text{если}~n\in F
\end{cases}
$$
(если $n=f(k)$, то $f(n)+1\ne g(k)$).
$g(n)=f(n)+n$ при любом$n$. В самом деле, среди чисел 1, 2, $\ldots$, $f(f(n))$, $g(n)$ имеется $f(n)$ чисел $f(1)$, $f(2)$, $\ldots$, $f(f(n))$ из $F$ и $n$ чисел $g(1)$, $g(2)$, $\ldots$, $g(n)$ из $G$. Таким образом, $g(n)=f(n)+n$.
Свойства 1° и 2° дают нам возможность составить «ускоренную» таблицу 2. Теперь остаётся, пользуясь свойством 1°, перейти от 234 к 240 (таблица 3). Ещё проще, как догадался наш читатель А. Балинский, предусмотрительно сделать лишний шаг раньше (используя равенство $f(f(n))=f(n)+n-1$):
$$\begin{gather*}
f(57)=90+2\quad (56\in F), \qquad f(92)=92+56=148,\\
f(148)=148+91,\\
f(239)=239+147=386,\qquad f(240)=386+2=388\quad (239\in F).
\end{gather*}$$
Итак, ответ на конкретный вопрос задачи М538 получен: $f(240)=388$. Однако оказывается, что здесь можно продвинуться существенно дальше — найти замечательные простые формулы, сразу дающие ответ для любого $n$:
$$
f(n)=\left[\dfrac{1+\sqrt5}2n\right],\quad g(n)=\left[\dfrac{3+\sqrt5}2n\right]\tag{*}
$$
(здесь $[x]$ — целая часть $x$). До формул (*) додумались несколько наших читателей, но не всем удалось их аккуратно доказать. Алгебраическое доказательство довольно громоздко (хотя и не очень сложно); мы вместо него приведём наглядную картинку, из которой будут ясны и формулы (*), и ход построения последовательностей $\{f(n)\}$, $\{g(n)\}$. Но прежде объясним «на пальцах», откуда в этой задаче появляется иррациональное число $\dfrac{\sqrt5+1}{2}$.
Глядя на таблицу 1, естественно предположить, что последовательность $\{f(n)\}$ растёт примерно как линейная функция от $n$: $f(n)\approx \gamma n$. Тогда при больших $n$ должно быть $g(n)\approx f(f(n))\approx\gamma(\gamma n)=\gamma^2n$. Но согласно 2°, $g(n)=f(n)+n$, так что $\gamma^2n\approx\gamma n+n$, а это возможно лишь при $\gamma^2=\gamma+1$, откуда (если $\gamma\gt0$) $\gamma=\dfrac{\sqrt5+1}2$. Из дальнейшего будет видно, что наши множества $F$ и $G$ из первых $n$ натуральных чисел действительно содержат примерно по $\dfrac n\gamma$ и $\dfrac n{\gamma^2}$ чисел соответственно $\Big($как говорят, они имеют плотности$\dfrac1\gamma$ и $\dfrac1{\gamma^2}\Big)$.
Число $\gamma$ и его ближайшие «родственники»
$$
\dfrac1\gamma=\gamma-1=\dfrac{\sqrt5-1}2,\quad\gamma^2=\gamma+1=\dfrac{\sqrt5+3}2,\quad\dfrac1{\gamma^2}=\dfrac{3-\sqrt5}2
$$
возникают в самых разнообразных задачах, в частности, при исследовании чисел Фибоначчи 1, 2, 3, 5, 8, 13, $\ldots$, $\Phi_{n+1}=\Phi_{n-1}+\Phi_n$, $\ldots$ (любопытно, что эти числа на 1 меньше чисел $n$ из таблицы 2; подумайте, почему), в теории чисел, в геометрии. В частности, легко проверить, что при отрезании квадрата от прямоугольника с «золотым» отношением длин сторон $\gamma$ остаётся прямоугольник, подобный первоначальному, — отсюда следует, что на рисунке 1, где такое отрезание проделано дважды, точки $O$, $K$ и $M$ лежат на одной прямой. Это свойство числа $\gamma$ нам пригодится.
Рис. 1
Приведём теперь простой способ построения чисел $f(n)$ и $g(n)$. На клетчатой бумаге как на координатной плоскости (рис. 2) проведём прямую $l$, определяемую уравнением $y=\gamma x-c$ с «золотым» угловым коэффициентом $\gamma=\dfrac{\sqrt5+1}2$. (Как это сделать с помощью циркуля и линейки?) Занумеруем подряд все те «красные» клетки (рис. 2), которые пересекает прямая $l$, начиная с нулевой клетки, содержащей начало координат $O$. Поскольку $\gamma$ иррационально, $l$ не проходит через узлы сетки, т. е. входит в очередную клетку, пересекая либо прямую $y=n$, либо прямую $x=n$ ($n\in\mathbb{Z}$). Заметим, что номер клетки $\{(x;y)\colon [x]=i{,}~[y]=j\}$ равен $i+j$ (почему?). Мы утверждаем, что если номер клетки $m$, то соответственно либо $m=f(n)$, либо $m=g(n)$. Другими словами, если занумеровать по порядку отрезки координатных лучей $Ox$ и $Oy$, то над$n$-м отрезком оси $x$ лежит клетка номер $g(n)$, а справа от $n$-го отрезка оси $y$ лежит клетка номер $f(n)$. Проверьте это по таблице 1 и рисунку 2!
Рис. 2
Доказательство, что построенные таким образом, с помощью клетчатой бумаги, числа $f(n)$ и $g(n)$ в самом деле те, которые нам нужны, состоит в проверке того, что номера клеток удовлетворяют всем свойствам последовательностей $f$ и $g$ из условия задачи. Тот факт, что мы получаем разбиение всего натурального ряда $\mathbb{N}$ на две непересекающиеся возрастающие последовательности, ясен. Остаётся проверить, что $g(k)=f(f(k))+1$. «Распространим» нумерацию красных клеток на всю плоскость: каждой клетке плоскости $\{(x;y)\colon[x]=i{,}~[y]=j\}$ присвоим номер $i+j$ (синие цифры на рисунке 2); при этом номера отрезков на осях совпадают с номерами содержащих их клеток.
Для произвольного $n$ отметим точки $K{\left(\dfrac n\gamma;n\right)}$ и $M(n;\gamma n)$ пересечения прямой $l$ с прямыми $y=n$ и $x=n$ (рис. 3). Тогда левая клетка, содержащая точку $K$, имеет номер $f(n)$, а нижняя клетка, содержащая точку $M$, — номер $g(n)$. Отметим проекции $K'$ и $M'$ точек $K$ и $M$ на ось $y$. Заметим, что $\widehat{KKM'}=45^\circ$ (вспомните рисунок 1), поэтому клетки, содержащие точки $K$ и $M'$, имеют один и тот же номер $f(n)$. В точке $M$, таким образом, прямая $l$ переходит из клетки номер $f(f(n))$ в клетку номер $g(n)$, т. е. $f(f(n))+1=g(n)$.
Рис. 3
Заодно, подсчитав номера клеток, содержащих $K$ и $M$, мы получим и основные формулы (*):
$$
\begin{gather*}
f(n)=\left[\dfrac n\gamma\right]+n=\left[n\dfrac{\sqrt5-1}2\right]+n=\left[\dfrac{\sqrt5+1}{2}n\right],\\
g(n)=n+[\gamma n]=n+\left[n\dfrac{\sqrt5+1}{2}\right]=\left[\dfrac{\sqrt5+3}{2}n\right].
\end{gather*}
$$
Заметим, что точно таким же образом можно доказать следующий интересный факт: среди чисел$[\alpha n+\mu]$, $[\beta(n-\mu)+\mu]$, где$\alpha$ и$\beta$ — иррациональные числа, связанные условием$\alpha\beta=\alpha+\beta$ ($\mu$ — любое фиксированное число, а $n$ пробегает всё множество целых чисел$\mathbb{Z}$), встречается каждое целое число, причём ровно один раз. (Для доказательства рассмотрите прямую $y=\lambda x+u$ с $\lambda=\alpha-1=\dfrac1{\beta-1}$ и выпишите номера клеток, содержащих эту прямую.) То же соотношение между $\alpha$ и $\beta$ можно записать и так: $\dfrac1\alpha+\dfrac1\beta=1$ — плотности множеств
$$
\{[\alpha n+\mu],~n\in\mathbb{Z}\}\quad\text{и}\quad\{[\beta(n-\mu)+u],~n\in \mathbb{Z}\}
$$
в сумме, естественно, дают 1.
