Нерешенные задачи, формулировка которых понятна школьникам.

[Stan Slapenarski]

Open Problems for Undergraduates

[Мастак]

Вот в Комбинаторике - и еж.. школьнику сразу понятно
"Количество незамкнутых маршрутов шахматного коня на произвольной доске"

Цитата:

В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня.
Количество всех замкнутых маршрутов коня (гамильтоновых циклов) известно и есть алгоритм вычисления для любой доски.
В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор. Известно, что количество незамкнутых маршрутов на доске 64х64 не превышает числа сочетаний из 168 по 63.
Доказано, что незамкнутые маршруты существуют на всех досках. Количество незамкнутых маршрутов коня на доске для n = 1, 2, … равно:
1, 0, 0, 0, 1728, 6637920, 165575218320, … (последовательность A165134 в OEIS).

[VAL]

Мастак в сообщении #817193 писал(а):

Вот в Комбинаторике - и еж.. школьнику сразу понятно
"Количество незамкнутых маршрутов шахматного коня на произвольной доске"

Цитата:

В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня.
Количество всех замкнутых маршрутов коня (гамильтоновых циклов) известно и есть алгоритм вычисления для любой доски.
В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор. Известно, что количество незамкнутых маршрутов на доске 64х64 не превышает числа сочетаний из 168 по 63.
Доказано, что незамкнутые маршруты существуют на всех досках. Количество незамкнутых маршрутов коня на доске для n = 1, 2, … равно:
1, 0, 0, 0, 1728, 6637920, 165575218320, … (последовательность A165134 в OEIS).

А как сочетается между собой подчеркнутое и... подчеркнутое?

[provincialka]

(О нуле)

VAL в сообщении #817206 писал(а):

А как сочетается между собой подчеркнутое и... подчеркнутое?

- Есть ли у крокодила крылья?
- Есть, но их количество равно нулю.

[r-aax]

Мне нравится эта.

Гипотеза Эрдеша-Секереша
Из любых $2^{n - 2} + 1$ точек общего положения на плоскости можно выбрать $n$, образующих выпуклый многоугольник.

[Мастак]

VAL в сообщении #817206 писал(а):

Мастак в сообщении #817193 писал(а):

Вот в Комбинаторике - и еж.. школьнику сразу понятно
"Количество незамкнутых маршрутов шахматного коня на произвольной доске"

Цитата:

А как сочетается между собой подчеркнутое и... подчеркнутое?

так-ыыы, формула нужна, а не копать отсюда и до обеда

ИМХО Ежупонятно говоря, все проблемы комбинаторики вроде формулируют так: "А можно
это сделать, не перебирая тупо все варианты?"

[tatkuz1990]

Проблема Кука (сформулирована в 1971 году)

Допустим, что вы, находясь в большой компании, хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то достаточно будет доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствие этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей. Это говорит о том, что решение какой-либо задачи часто занимает больше времени, чем проверка правильности решения.
Стивен Кук сформулировал проблему: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки. Эта проблема также является одной из нерешенных задач из области логики и информатики. Ее решение могло бы революционным образом изменить основы криптографии, используемой при передаче и хранении данных.

Интересно, школьник задачу поймет? За понимание и решение дают миллион долларов.

[Мастак]

r-aax в сообщении #817293 писал(а):

Мне нравится эта.

Гипотеза Эрдеша-Секереша
Из любых $2^{n - 2} + 1$ точек общего положения на плоскости можно выбрать $n$, образующих выпуклый многоугольник.

у Эрдеша много такого (вот минимальное, известное то есть)
Гипотеза Эрдёша — Турана об арифметических прогрессиях в плотных множествах, 1936, совместно с Палом Тураном[hu] (доказана в 1975 году теоремой Семереди).
Гипотеза Эрдёша — Турана для аддитивных базисов[en], 1941, совместно с Палом Тураном (не доказана по состоянию на 2013 год).
Гипотеза Эрдёша об арифметических прогрессиях.
Гипотеза Эрдёша о минимальном числе различных расстояний между различными точками в Евклидовом пространстве (для плоскости доказана в 2010 году Ларри Гутом (англ. Larry Guth) и Нецем Кацем (англ. Nets Hawk Katz)).
Гипотеза Кэмерона — Эрдёша о количестве свободных от сумм подмножеств, 1988, совместно с Питером Кэмероном[en] ( доказана в 2003 году Беном Грином).
Гипотеза Эрдёша — Бура о числах Рамсея на графах.
Гипотеза Эрдёша — Фабера — Ловаса.
Гипотеза Эрдёша — Грэма[en] о представлении единицы одноцветной египетской дробью (доказана Эрнестом Крутом[en] в 2003 году).
Гипотеза Эрдёша — Дьярфаша о длине циклов в графе со степенью вершин не менее 3.
Гипотеза Эрдёша — Страуса[en] о египетской дроби .
Гипотеза Эрдёша — Моллина — Уолша о последовательных тройках полнократных чисел.
Гипотеза Эрдёша — Сэлфриджа о том, что покрывающее множество содержит по крайней мере одно нечётное число.
Гипотеза Эрдёша — Вуда о том, что чисел любого отрезка натурального ряда для любого достаточно большого фиксированного однозначно определяются списком своих различных простых делителей. С ней связано число Эрдёша — Вуда
Гипотеза Эрдёша — Секереша о числе точек в общем положении, обязательно включающих вершины выпуклого n-угольника.
Гипотеза Эрдёша — Хайналя о том, что в семействе графов, получаемом удалением порожденного подграфа, каждый граф либо является большой кликой, либо большим независимым множеством[3].
Гипотеза Эрдёша — Хейльбронна в комбинаторной теории чисел о числе сумм двух множеств вычетов по простому модулю (доказана Диашем да Силвой (J. A. Dias da Silva) и Хамидоне (Y. O. Hamidoune) в 1994 году).
Гипотеза Эрдёша — Менгера о разделяющих путях в бесконечных графах (доказана Роном Ахарони и Эли Бергером).
Гипотеза Эрдёша — Стюарта о диофантовом уравнении (доказана Люком[4]).
Гипотеза Эрдёша — Ловаса о слабых и сильных дельта-системах (доказана Мишелем Деза).
Проблема Нелсона — Эрдёша — Хадвигера или вопрос о хроматическом числе пространства.

[Munin]

Кстати, если известно разложение $n$ на простые множители, то известно ли хоть что-нибудь (или хотя бы гипотезы) о разложении на множители $n+1$?

[tatkuz1990]

Точно известно одно: если $n $ нечетно, то $ \, n+1 \, $ обязательно имеет множитель $ \, 2 \, $

[Munin]

(Я ещё знаю, что множества простых множителей $n$ и $n+1$ не пересекаются :-) Но речь-то шла не о таких банальностях.)

[Stan Slapenarski]

Munin в сообщении #817515 писал(а):

Кстати, если известно разложение $n$ на простые множители, то известно ли хоть что-нибудь (или хотя бы гипотезы) о разложении на множители $n+1$?

Сейчас ничего такого не припоминаю, но есть интересный частный случай: "Числа Ферма".

[nnosipov]

Munin в сообщении #817515 писал(а):

Кстати, если известно разложение $n$ на простые множители, то известно ли хоть что-нибудь (или хотя бы гипотезы) о разложении на множители $n+1$?

Есть так называемый $(N-1)$-метод, позволяющий на основе частичного разложения числа $N-1$ сделать вывод о простоте числа $N$ (естественно, при выполнении некоторых достаточных условий). В частности, так можно получить вполне практичный критерий простоты чисел Ферма. Есть также аналогичный $(N+1)$-метод, который в частности предоставляет критерий простоты чисел Мерсенна. Вот здесь можно найти примеры в популярном изложении:
Рудаков А.Н. Числа Фибоначчи и простота числа $2^{127}-1$ // Математическое просвещение. 2000. Сер. 3. Вып. 4. С. 127—139.

[Munin]

Спасибо!
Но я думал скорее не в сторону простоты, а в сторону дискретного логарифмирования... Впрочем, я всё равно эту теорию чисел абсолютно не знаю, так что не знаю даже, близки или далеки разные вещи друг к другу.

[svv]

r-aax в сообщении #817293 писал(а):

Из любых $2^{n - 2} + 1$ точек общего положения на плоскости можно выбрать $n$, образующих выпуклый многоугольник.

Впечатляло бы, если бы $n$ не было так мало по сравнению с $2^n$. Но тем страннее, что не доказано.