Задача с конкурса «Romanian Master of Mathematics - 2015»

[Ktina]

Red_Herring в сообщении #986747 писал(а):

Tall в сообщении #986697 писал(а):

Ну так давайте про последовательность, иначе тема разовьется в другую сторону.

Причём для олимпиадных задач есть другой форум, который ТС хорошо известен.

Существует ли бесконечная последовательность натуральных чисел $a_1, a_2, a_3, \dots$ такая, что числа $a_m$ и $a_n$ взаимно просты тогда и только тогда, когда $|m-n|=1$?

[ИСН]

Некогда объяснять; короче, на первое место ставим 6. Про второе пока ничего не загадываем, а со всех остальных берём обещание, что они будут делиться попеременно на 2 и 3.
На второе ставим 35. Про следующее пока ничего не загадываем, а со всех остальных берём обещание, что они будут делиться попеременно на 5 и 7.
На третье (там была обещана делимость на 2) ставим 22. На следующем ничего не делаем, дальше некоторые уже делятся на 2, а остальным подкидываем ещё множитель 11.
На четвёртое (там были обещаны 3 и 5) ставим $3\cdot5\cdot13$, потом проходим дальше и рассыпаем 13, где надо.
И так, нагребая впереди себя огромный и чудовищно растущий государственный долг, прём вперёд.
Я не вижу, что нас остановит.

[Ktina]

ИСН
Чуть-чуть напоминает вот эту задачу:
http://problems.ru/view_problem_details ... p?id=79286

[ИСН]

Аналогия в том, что мы накапливаем впереди колоссальный долг, но расплатиться по текущим обязанностям нам всегда хватит? Ну, есть такое.
А там бред написан, кстати.

Цитата:

Предположим, что мы построили конечную последовательность, обладающую следующими свойствами:

- все попарные разности между членами этой последовательности различны;
- числа $1, 2, ..., k$ можно представить в виде разности двух её членов.
- число $k + 1$ нельзя представить в виде разности двух её членов.

Пусть максимальный член этой последовательности равен $M$. "Допишем" теперь эту последовательность: добавим к ней числа $2M$ и $2M + k + 1$. Проверьте сами, что новая последовательность удовлетворяет свойствам 1, 2 (с заменой $k$ на $k + i$, где $i$ — некоторое натуральное число, зависящее от первоначально построенной последовательности, $i\ge1$) и свойству 3 (с заменой числа $k + 1$ на число $k + i + 1$). Применяя описанное "дописывание", например, к числам $1, 2$, получим бесконечную последовательность, удовлетворяющую условиям задачи.

Если $M=k+1$ (а ведь именно это происходит с затравкой $1,2$, да и дальше на каждом шагу), то получается хрень.
Так-то построить можно, если без лишних мудрствований: A005282.

[grizzly]

ИСН в сообщении #986919 писал(а):

А там бред написан, кстати... получается хрень.

Похоже, просто $k$ нужно пересчитывать заново после добавления $2M$. Думаю, что это и предполагалось.

ИСН в сообщении #986919 писал(а):

Так-то построить можно, если без лишних мудрствований: A005282.

А это точно оно? Здесь очевидно только, что все разности будут разные, но что среди них будут все, я так с ходу не соображу, как показать. Надеюсь, что это или не так, или сложно.

[grizzly]

grizzly в сообщении #986945 писал(а):

А это точно оно?

Нет, не точно. Нашёл про это и вообще по теме много интересного. В частности, действительно, 33, например, пока не нашли среди разностей этой последовательности.

[ИСН]

Ааааааа!!!

[guryev]

ИСН в сообщении #986814 писал(а):

...на первое место ставим 6. Про второе пока ничего не загадываем, а со всех остальных берём обещание, что они будут делиться попеременно на 2 и 3.
На второе ставим 35. Про следующее пока ничего не загадываем, а со всех остальных берём обещание, что они будут делиться попеременно на 5 и 7.
На третье (там была обещана делимость на 2) ставим 22. На следующем ничего не делаем, дальше некоторые уже делятся на 2, а остальным подкидываем ещё множитель 11.
На четвёртое (там были обещаны 3 и 5) ставим $3\cdot5\cdot13$, потом проходим дальше и рассыпаем 13, где надо.

Тогда пятое число должно делиться на 2, 7 и 11. Следовательно, шестое не должно делиться ни на одно из этих трёх чисел и тогда оно не будет иметь общих делителей с третьим.

Наверно, проще было бы представить последовательность в виде таблицы. Пишем кортеж различных простых чисел (неважно в каком порядке, пусть в возрастающем) и под ним заполняем галочками колонки таблицы, например, так:

$$\begin{tabular}{lllllllllllll}{} & p_1 & p_2 & p_3 & p_4 & p_5 & p_6 & p_7 & p_8 & p_9 & p_{10} & p_{11} & p_{12}\\ x_1 & $\surd$ & $\surd$ & {} & {} & {} & {} & {} & {} \\ x_2 & {} & {} & $\surd$ & $\surd$ & {} & {} & {} & {} \\ x_3 & $\surd$ & {} & {} & {} & $\surd$ & $\surd$ & {} & {} \\ x_4 & {} & $\surd$ & $\surd$ & {} & {} & {} & $\surd$ & $\surd$ \\ x_5 & $\surd$ & {} & {} & $\surd$ & $\surd$ & {} & {} & {} & $\surd$ & $\surd$ \\ x_6 & {} & $\surd$ & $\surd$ & {} & {} & $\surd$ & $\surd$ & {} & {} & {} & $\surd$ & $\surd$\\ \end{tabular}$$

То есть, в строке под первой парой простых пишем сначала две галочки подряд, потом строку пропускаем, в следующих строках галочки попеременно под первым и вторым числом из пары; под второй парой первую строку пропускаем, потом две галочки в строке, потом опять строку пропускаем, потом опять галочки попеременно, и т.д.

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

Например, для кортежа простых чисел $2,3,5,7,11,13,17,19,23,29,31,37$ получились бы элементы последовательности:

$$2\cdot 3, 5 \cdot 7, 2 \cdot 11 \cdot 13, 3 \cdot 5 \cdot 17 \cdot 19, 2 \cdot 7 \cdot 11 \cdot 23 \cdot 29, 3 \cdot 5 \cdot 13 \cdot 17 \cdot 31 \cdot 37 $$

[ИСН]

guryev в сообщении #988153 писал(а):

Тогда пятое число должно делиться на 2, 7 и 11.

ИСН в сообщении #986814 писал(а):

дальше некоторые уже делятся на 2, а остальным подкидываем ещё множитель 11.

Цитата:

остальным подкидываем

Цитата:

остальным

[guryev]

Зачем это? Напишите просто, чему равны пятое и шестое число.

[ИСН]

Пятое будет, по-видимому, $2\cdot7\cdot17$. Делиться на 11 оно не должно и не будет. Взаимную непростоту с несоседями слева обеспечивают 2 или 7, справа - 2 и 7 одновременно (у нечётных) или 17 (у чётных).
Шестое тогда - $3\cdot5\cdot11\cdot19$. По-моему, некоторая экономия по сравнению с Вашим методом налицо.
Какая, впрочем, разница.