Пять 1000-долларовых задач Конвея

[maxal]

На только что прошедшей конференции, посвященной анализу целочисленных последовательностей, Джон Конвей предложил пять задач, за решение каждой из которых он готов заплатить 1000 долларов США. Я постепенно выложу эти задачи тут в моем переводе, начав с пятой (возможно, самой простой по словам самого Конвея).

Видео со второй проблемной сессии, где Конвей и др. представляют свои задачи: http://vimeo.com/109815595

Задача 5. Добраться до простого: (гипотеза опровергнута)
Пусть $n$ - целое положительное число. Запишем его разложение на простые в традиционной форме (например, $60=2^2\cdot 3\cdot 5$), где простые идут в порядке возрастания, а экпоненты равные 1 опущены. Опустим экспоненты вниз к простым и уберём знаки умножения, получим число $f(n)$. Повторим с ним ту же операцию.

Так, например, $f(60)=f(2^2\cdot 3\cdot 5)=2235$. Далее, так как $2235 =3\cdot 5\cdot 149$, это число отображается в $f(2235)=35149$, и так как $35149$ является простым, то оно отображается в себя: $f(35149)=35149$. Таким образом мы добираемся до простого числа и останавливаемся на нём навсегда:

$$60\rightarrow 2235\rightarrow 35149\rightarrow 35149\rightarrow \dots.$$

Гипотеза, в которую, похоже, верю только я (Конвей), состоит в том, что любое число в конечном счёте достигает простого числа. Наименьшее число, судьба которого пока неизвестна - это 20, начиная с которого получаем $20\rightarrow 225\rightarrow 3252\rightarrow 223271\rightarrow \dots$ и вскоре добираемся до чисел из более чем 100 цифр, не встретя простого.

P.S. Конвей также добавил, что вполне возможно, что найдется контрпример уже в числах до миллиона -- особых численных проверок своей гипотезы он не проводил. См. также A195264. Известная траектория числа 20 описана тут.

• Задача 4. О "мертвых мухах"
• Задача 3. The Thrackle Problem
• Задача 2. 99-граф
• Задача 1. Игра в чеканку

[ivashenko_a_v]

Особо порадовал постскриптум. Я думаю, что если Вы все правильно перевели, то Конвей пошутил насчёт контрпримера :)

[maxal]

ivashenko_a_v в сообщении #918996 писал(а):

Особо порадовал постскриптум. Я думаю, что если Вы все правильно перевели, то Конвей пошутил насчёт контрпримера :)

Это было не похоже на шутку. Возможным наличием контрпримера он объяснил, почему эту задачу он считает проще остальных. При этом лично он не верит в существование контрпримера, причем настолько, что готов за него отдать $1000.

[ivashenko_a_v]

Контрпример его гипотезе найти невозможно, догадайтесь почему :)

[maxal]

ivashenko_a_v в сообщении #919048 писал(а):

Контрпример его гипотезе найти невозможно, догадайтесь почему :)

Ну-ка, ну-ка, или рассказывайте почему, или сами найдите ошибку в своих рассуждениях...

[ivashenko_a_v]

Чтобы найти контрпример, опровергающий его гипотезу, необходимо проверить этот контрпример на бесконечности или где- то рядышком с нею. Как Вы себе это представляете?

-- 15.10.2014, 00:46 --

Думаю если это и возможно сделать(опровергнуть или подтвердить гипотезу), то лишь развив какую - то общую теорию.

[venco]

ivashenko_a_v в сообщении #919058 писал(а):

Чтобы найти контрпример, опровергающий его гипотезу, необходимо проверить этот контрпример на бесконечности или где- то рядышком с нею. Как Вы себе это представляете?

Достаточно зацикливания.

[ivashenko_a_v]

Простите, а как Вы отличите, зацикливание от длительного вычисления? По- моему, чтоб точно определить, что это зацикливание, необходимо наблюдать за ним бесконечное время.

[ИСН]

Чтобы определить, что это зацикливание, достаточно пронаблюдать за ним в течение одного периода. Если повторится одно число, то повторится и всё, что после него.
(Мыслимы и другие варианты доказуемой расходимости, но здесь это вряд ли.)

[ivashenko_a_v]

Да, здесь зацикливание не может произойти, впрочем также как и остановка, если только из - за ошибки компьютера. Ведь контрпример для данной гипотезы, если он конечно существует, необходимо проверить на бесконечности! Получается все-таки, что Конвей пошутил? Не мог же он так тупануть? Или Вы что- то неправильно перевели!

[maxal]

ivashenko_a_v в сообщении #919086 писал(а):

Да, здесь зацикливание не может произойти, впрочем также как и остановка, если только из - за ошибки компьютера. Ведь контрпример для данной гипотезы, если он конечно существует, необходимо проверить на бесконечности! Получается все-таки, что Конвей пошутил? Не мог же он так тупануть? Или Вы что- то неправильно перевели!

Именно что зацикливание может в принципе произойти - например, что-то типа $q_1 \rightarrow q_2 \rightarrow q_3 \rightarrow q_1$. По крайней мере причин, почему подобных циклов не может быть, сразу не видно. В установлении наличия таких циклов или доказательстве их отсутствия как раз и состоит задача Конвея.

[ivashenko_a_v]

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

[Skeptic]

Числа, образуемые предложенным алгоритмом, могут как возрастать, так и уменьшаться. Т.о. есть предпосылки для образования цикла.

[maxal]

Раз уж начал в обратном порядке:

Задача 4. О "мёртвых мухах":
(название отсылает к орнаменту напоминающему мух, который Конвей наблюдал в своей комнате, будучи ребенком)

Если множество $M$ точек на плоскости таково, что каждый выпуклый регион площади 1 содержит одну точку из $M$, то верно ли, что в $M$ существуют пары точек на сколь угодно малом расстоянии друг от друга?

[Руст]

Мне кажется эта задача проще и решается от противного.
Только в условии чуть яснее станет, если писать:
каждый выпуклый регион площади 1 солержит хотя бы одну точку из М.
Иначе не будет выполнено условие - содержит ровно одну точку.