Докажите, что каждое целое неотрицательное число можно представить в виде $\dfrac{(x+y)^2+3x+y}2$, где $x$ и $y$ — целые неотрицательные числа, и что такое представление единственно.
Обозначим сумму $x+y$ через $s$ и перепишем данную формулу так:
$$
n=\dfrac{(x+y)^2+3x+y}2=\dfrac{s^2+s}2+x.\tag1
$$
Условия, что $x$ и $y$ — целые числа, $x\ge0$ и $y\ge0$, эквивалентны таким: $x$ и $s$ — целые числа, $x\ge0$, $s\ge x$. При заданном $s$ величина $x$ может принимать значения: 0, 1, $\ldots$, $s$; соответственно величина $n$, определяемая формулой (1), принимает значения: $\dfrac{s^2+s}2$, $\dfrac{s^2+s}2+1$, $\ldots$, $\dfrac{s^2+s}2+s$. Итак, каждому $s=0$, 1, 2, $\ldots$ соответствует отрезок из $s+1$ целых неотрицательных чисел $n$. Заметим, что последнее число отрезка, соответствующего $s$, как раз на единицу меньше первого числа отрезка, соответствующего $s+1$:
$$
\dfrac{s^2+s}2+s+1=\dfrac{(s+1)^2+(s+1)}2.
$$
Поэтому такие отрезки будут содержать все целые неотрицательные числа $n$, причём каждое $n$ попадает только в один отрезок, т. е. ему будет соответствовать ровно одна пара значений $s$ и $x$ (рис. 4).
Рис. 4Рис. 5
Задача решена. Мы доказали, что формула (1) позволяет «занумеровать» все точки $(x,y)$ с целыми неотрицательными координатами числами $n=0$, 1, 2, $\ldots$. На рисунке 5 показано, как расположены эти номера по порядку.
Некоторые из тех, кто доказывал утверждение задачи по индукции, забыли, что не всегда можно переходить от точки $(x,y)$ к $(x+1,y-1)$: если $y=0$, то нужно в качестве следующей за $(x,0)$ точки брать $(0,x+1)$.
Э. Туркевич приводит в своём решении формулу, аналогичную (1), которая позволяет занумеровать наборы не из двух, а из $k$ целых неотрицательных чисел $(x_1,x_2,{\ldots},x_k)$:
$$
n=C_{s_k+k-1}^k+C_{s_{k-1}+k-2}^{k-1}+\ldots+C_{s_2+1}^2+C_{s_1}^1,
$$
где $s_i=x_1+x_2+\ldots+x_i$,
$$
C_p^q=\dfrac{p(p-1)\ldots(p-q+1)}{1\cdot2\cdot\ldots\cdot q}.
$$
Например, для $k=3$ получается формула
$$
\begin{gather*}
n=\dfrac{s_3(s_3+1)(s_3+2)}6+\dfrac{s_2(s_2+1)}2+s_1=\\
=\dfrac16[(x_1+x_2+x_3)^3+3(x_1+x_2+x_3)^2+3(x_1+x_2)^2+11x_1+5x_2+2x_3].
\end{gather*}
$$
Попробуйте обобщить задачу в другом направлении: найти формулу, которая устанавливает соответствие между всеми точками $(x,y)$ на плоскости с целочисленными координатами и всеми целыми (или целыми неотрицательными) числами $n$. Может ли такая формула записываться многочленом второй степени $n=f(x,y)$, как формула (1)?
