Пусть дано конечное или счетное число конечных или счетных множеств. Расположив элементы каждого множества в последовательности и поместив эти последовательности друг под другом, получим таблицу, в которой проходим по очереди диагонали и получаем алгоритм счета элементов этой таблицы. Далее задача:

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

Все что я придумал - это уравнение вида $%ax^2+by^2+cxy+dx+ey = n$%, в котором x,y - координаты элементов полученного "массива", a,b,c,d - некоторые рациональные коэффициенты, а n - получаемое натуральное число, которое ставится в соответствие паре x,y. Далее как-то я продвинуться не могу. Соответственно, хотел бы получить подсказку куда думать. Спасибо

задан 8 Июл 16:56

изменен 8 Июл 17:05

10|600 символов нужно символов осталось
2

Там есть простая явная формула. Давайте точно опишем процесс заполнения таблицы и способ нумерации, а потом её выведем.

Таблицу мыслим как матрицу с бесконечным числом строк и столбцов. Строки нумеруем числами 1, 2, 3, ... сверху вниз. Столбцы -- тем же числами слева направо.

Далее нумеруем клетки таблицы. Каждая клетка имеет координаты (x,y). Их сумма принимает значения 2, 3, 4, ... . Будем последовательно рассматривать такие клетки, а для клеток с одной и той же суммой (на одной диагонали) будем нумеровать пары в порядке увеличения координаты y.

Пары расположатся в таком порядке: (1,1); (2,1), (1,2); (3,1), (2,2), (1,3); ... . Закономерность понятна. Нумеруем эти пары по порядку, и пусть N(x,y) есть номер пары (x,y). Например, N(2,2)=5. Нужно вывести формулу для этой функции.

Обратим внимание на пары вида (1,1), (2,1), (3,1), ... . Их номерами будут 1, 2, 4, 7, ... . Легко заметить, что это треугольные числа 0, 1, 3, 6, ... , увеличенные на единицу. Отсюда видно, что N(a,1)=(a-1)a/2+1.

Теперь рассмотрим произвольную пару (x,y). Она является частью диагонали, на которой последовательно расположены пары с одной и той же суммой координат: (x+y-1,1), (x+y-2,2), ... , (x,y), ... , (1,x+y-1). Номер пары (x+y-1,1) мы уже знаем: он равен (x+y-2)(x+y-1)/2+1. Это первая пара списка для данной диагонали. У этих пар координата y увеличивается на 1, и номер также увеличивается на 1. Это значит, что для пары со второй координатой y нужно в конце прибавить не 1, а y. И получается окончательная формула N(x,y)=(x+y-2)(x+y-1)/2+y. Это многочлен второй степени от двух переменных. Скобки можно при желании раскрыть, но в таком виде считать проще. Например, N(7,10)=15*16/2+10=130.

Заметим, что более удобный вид формула приобрела бы в случае рассмотрения целых неотрицательных чисел 0, 1, 2, ... вместо целых положительных.

Представляет интерес обратная задача: дан номер пары (например, 2018), и надо найти её координаты. Пусть n -- известный нам номер пары. Стратегия такова: сначала мы найдём число m=x+y, затем через него выразим y, и далее выразим x.

Номера пар с заданной суммой координат принимают значения от (m-2)(m-1)/2+1 до (m-2)(m-1)/2+m-1=(m-1)m/2 включительно. Поэтому (m-2)(m-1)/2 < n <= (m-1)m/2, то есть m оказывается наименьшим числом, которое удовлетворяет второму неравенству. Решаем его как квадратичное относительно m:

m^2-m >= 2n

4m^2-4m+1 >= 8n+1

(2m-1)^2 >= 8n+1

2m-1 >= sqrt(8n+1)

m > = (sqrt(8n+1)+1)/2

Отсюда следует, что m=Round((sqrt(8n+1)+1)/2), где функция Round округляет действительное число в сторону увеличения до ближайшего целого. Например, Round(7)=7, Round(3,14)=4.

Далее получаем y=n-(m-2)(m-1)/2 из основной формулы, и x=m-y.

Пример: пусть n=2018. Тогда 8n+1=16145 находится между точными квадратами 127^2=161129 и 128^2=16384. При этом 64 < (sqrt(8n+1)+1)/2 < 65, что даёт m=65. Далее y=2018-2016=2 и x=65-2=63. То есть искомой парой с номером 2018 будет (63;2). Аналогичным путём можно убедиться в том, что под номером 1000 идёт пара (36;10) и т.п.

ссылка

отвечен 8 Июл 19:43

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×492
×191

задан
8 Июл 16:56

показан
85 раз

обновлен
8 Июл 19:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru