Найти формулу биекции N x N <-> N

[peg59]

Читаю Верещангина и Шеня "Начала теории множеств".

На с. 15 доказывается счетность счетного числа счетных множеств.

И тут же задача:

29. Описанный проход по диагоналям задаёт взаимно од-
нозначное соответствие между множеством всех пар нату-
ральных чисел (которое обозначается $\mathbb N \times \mathbb N$) и $\mathbb N$. Любопытно,
что это соответствие задаётся простой формулой (многочле-
ном второй степени с рациональными коэффициентами). Ука-
жите этот многочлен.

Чувствую себя совершенно тупым, но не пойму, что имеется в виду?
Надо указать такие рациональные $a$ $b$ $c$ $d$ $f$, что формула
$n=ai^2+bi+ck^2+dk+f$
дает уникальные $n$ для всех пар $i$ и $k$?

Тупым подбором ничего не выходит (всегда находятся разные пары, дающие одинаковый номер), а какое-то общее соображение от меня ускользает.
К тому же, если коэффициенты рациональные, как может в результате всегда получаться целое?

[Someone]

Нумеруйте пары $(i,j)$ по диагоналям. Количество полных диагоналей и суммарное число элементов в них легко определяется по сумме $i+j$, и в качестве номера пары можно взять $k=\text{число элементов в заполненных диагоналях}+i+k_0$, где $k_0$ подбирается так, чтобы номер самой первой пары (это либо $(0,0)$, либо $(1,1)$, в зависимости от того, начинается $\mathbb N$ с $0$ или с $1$) совпадал с первым натуральным числом (то есть, с $0$ или с $1$).

[arseniiv]

peg59 в сообщении #1451401 писал(а):

К тому же, если коэффициенты рациональные, как может в результате всегда получаться целое?

Например так: $\frac16 m^3 + \frac12 m^2 + \frac13 m$ (чтобы разгадать этот случай, разложите на множители). Для большего числа переменных возможностей будет не меньше.

[peg59]

Ага. Мы нумеруем диагонали (а также последний элемент диагонали) количеством всех элементов от угла до данной диагонали включительно.
Номер $k$-й диагонали
$n_k=\frac {(k+1)k}2$
и оставшихся натуральных между двумя "диагональными" номерами как раз хватает, чтобы занумеровать оставшиеся элементы текущей диагонали.

Индексы диагональных элементов имеют постоянную сумму, соответствующую номеру данной диагонали (Someone, Вы слишком много подсказали!), поэтому $k$ заменяем суммой $i+j$ и для элементов следующих строк уменьшаем сумму на этот номер:
$n_{ij}=\frac{(i+j-1)(i+j)}{2}-i+1$
Непосредственная проверка для нескольких элементов таблицы ошибок не выявляет.
Видимо, это ответ.

Но меня мучает сомнение: для биекции надо бы указать обратное соответствие? Или не надо? Раз мы все смогли занумеровать - биекция установлена?

На вопрос arseniiv:
$\frac16 m^3 + \frac12 m^2 + \frac13 m = \frac{1}{6}m(m+1)(m+2)$ - один из сомножителей делится на 2, один - на три, получится целое. Слишком просто (когда подсказано!).

[Someone]

peg59 в сообщении #1451733 писал(а):

Но меня мучает сомнение: для биекции надо бы указать обратное соответствие? Или не надо? Раз мы все смогли занумеровать - биекция установлена?

Если занумеровали всё и без повторений (в этом, может быть, стоит убедиться) — значит, биекция. Но при желании обратное отображение тоже можно построить. Оно должно по номеру пары восстанавливать оба компонента пары, так что обратное отображение будет парой функций.

[peg59]

Итак, вычислим обратную функцию для найденной нумерации.
Обозначим $i+j=m$, тогда для $m$ получаем квадратное уравнение:
$\frac{m(m+1)}2 - i+1 = n$
Его положительный корень имеет вид:
$m=\frac{1}{2}(1+\sqrt{1+8(n+i-1)})$
Подкоренное выражение всегда является точным квадратом, но нам неизвестно $i$.
Удалив из суммы в скобках неотрицательное число $i-1$, получим неравенство
$m\ge\frac{1}{2}\left(1+\sqrt{1+8n}\right)$, причем равенство достигается только при $i=1$,
а значит, можно написать
$m=\left\lceil\frac{1}{2}\left(1+\sqrt{1+8n}\right)\right\rceil$, откуда уже получаем $i=\frac{m(m-1)}2-n+1;\ j=m-i$

[arseniiv]

peg59 в сообщении #1451733 писал(а):

$\frac16 m^3 + \frac12 m^2 + \frac13 m = \frac{1}{6}m(m+1)(m+2)$ - один из сомножителей делится на 2, один - на три, получится целое. Слишком просто (когда подсказано!).

Ага.