7! точек

[Ktina]

$7!$ точек делят окружность на $7!$ равных частей. Из этих $7!$ точек 2015 точек покрасили в красный цвет. Обязательно ли найдутся три красные точки, образующие равнобедренный треугольник?

[hippie]

Ответ: обязательно.


Доказательство можно провести в 4 этапа. Первые 3 делаются простым перебором; четвёртый — простая дирихлятина.

I) В правильном семиугольнике можно единственным (с точностью до поворота и симметрии) способом выбрать 3 вершины, которые не лежат в вершинах равнобедренного треугольника;
II) В правильном четырнадцатиугольнике можно единственным (с точностью до поворота и симметрии) способом выбрать 6 вершин, никакие 3 из которых не лежат в вершинах равнобедренного треугольника;
III) В правильном двадцативосьмиугольнике невозможно выбрать более 10 вершин, никакие 3 из которых не лежат в вершинах равнобедренного треугольника;
IV) В правильном пятитысячсорокаугольнике невозможно выбрать более 1800 вершин, никакие 3 из которых не лежат в вершинах равнобедренного треугольника.

[worm2]

Если моя программа не врёт, то довольно любопытные факты вскрываются. Например, в правильном 15-угольнике нельзя выбрать более 4 вершин, хотя в 14-угольнике помещалось аж 6. Так что оценку можно опустить до $5040/15\cdot 4=1344$.

Вдвойне любопытно, что последовательность максимального числа вершин, которые можно выбрать, отсутствует в OEIS! Это верно, даже если врёт моя программа, поскольку первые 7 членов (1,2,2,2,2,4,3) легко вычисляются вручную.

Есть некая похожая последовательность A003002, которая задаёт максимальное число элементов из [1...N], свободных от арифметической прогрессии (информативнее обратная к ней, A065825). Нам нужно то же самое, но с "закольцованным" списком [1, 2, ..., N, 1, 2, ...], а нету. Из "незакольцованного" варианта тоже, конечно, можно получить слабые оценки. Например, в 168-угольнике нельзя выбрать более 38 вершин, значит, в 5040-угольнике нельзя выбрать более 1140.

Ktina, где Вы взяли эту задачу?

[TOTAL]

worm2 в сообщении #969925 писал(а):

Если моя программа не врёт, то довольно любопытные факты вскрываются. Например, в правильном 15-угольнике нельзя выбрать более 4 вершин

$1,2,4,5,10$ - вот пять вершин

(Оффтоп)

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

[grizzly]

hippie в сообщении #969747 писал(а):

В правильном четырнадцатиугольнике можно единственным (с точностью до поворота и симметрии) способом выбрать 6 вершин, никакие 3 из которых не лежат в вершинах равнобедренного треугольника;

Ну это навряд. На девятнадцатиугольник с шестью вершинами я бы ещё согласился, но не меньше. Может, я что-то недопонял?
Впрочем, на идею решения моё замечание не влияет, конечно.
Удивительно: хотел найти эту последовательность у Слоана (сколько вершин можно покрасить в правильном $n$-угольнике без равнобедренных треугольников, или наоборот), но не нашёл. А вопрос сколько-то изучался, я был наслышан.

Задача соответствует рамсеевскому вопросу об отсутствии арифметических прогрессий длины 3 в числовой последовательности с периодом 5040. 2015 это с огромным запасом -- подобную задачу можно было запросто формулировать ещё в древнем мире, скажем, середине 3 столетья н.э. Но раз Ktina так долго ждала, то одно из двух: либо нужно было компьютеров дождаться, либо есть красивое решение, которое учитывает, что 7! это ровно в 2.5 раза больше, чем 2016, а значит, ещё чуть больше по сравнению с 2015.

Я красивого решения не придумал. Из приведенных выше вычислений следует, что найдётся 30 точек подряд, среди которых покрашено 13. Из 10 можно покрасить без (незакольцованных) 3-прогрессий только 5. Значит, нужно искать варианты 5+4+4 или 5+3+5 (края симметричны, а в центре 5 заведомо невыгодно). Вариантов там не та уж много, уже в двух десятках подряд можно покрасить только 9 точек (примерно одним вариантом), а из 30 -- максимум 12.

Должно быть красивое решение. Если не будет идей, ждём от Ktina :)

UPD. Многое сказали выше, но что-то противоречит моим наблюдениям и лень уже переформатировать весь текст.

-- 28.01.2015, 14:09 --

worm2 в сообщении #969925 писал(а):

хотя в 14-угольнике помещалось аж 6

Где же вы все такое находите?! :)

-- 28.01.2015, 14:17 --

Эта ссылка здесь будет уместна, я думаю. Надеюсь табличка будет понятна или несложно выйти на уровни выше с объяснениями. (Там только первые значения точные -- остальное оценки и компьютерные рекорды.)

[hippie]

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

worm2 в сообщении #969925 писал(а):

хотя в 14-угольнике помещалось аж 6

Где же вы все такое находите?! :)

Если обозначать вершины четырнадцатиугольника буквами русского алфавита от А до М, то требуемые 6 вершин: А, В, Ё, Ж, И, М.

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

Эта ссылка здесь будет уместна, я думаю. Надеюсь табличка будет понятна или несложно выйти на уровни выше с объяснениями. (Там только первые значения точные -- остальное оценки и компьютерные рекорды.)

Если я правильно понял смысл этой таблички, то в ней точнОе только первОе значение. В действительности начало должно выглядеть так:
1 — 1;
2 — 2;
3 — 6;
4 — 6;
…
(В шестиугольнике можно взять две пары противоположных вершин.)

Думаю, что в программе Вы забываете проверить, нет ли у "равнобедренного треугольника" совпадающих вершин.

[grizzly]

hippie
Вы совершенно правы -- я неправильно построил модель задачи. Я раньше много интересовался прогрессиями в периодических последовательностях, а здесь не учёл, что эта задача отличается от многоугольника в точности на:

hippie в сообщении #969994 писал(а):

Думаю, что в программе Вы забываете проверить, нет ли у "равнобедренного треугольника" совпадающих вершин.

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

Из приведенных выше вычислений следует, что найдётся 30 точек подряд, среди которых покрашено 13.

Это тоже неверно (не в ту сторону единичку учёл -- такое решение только через 2 года подойдёт).
Значит, решение без компьютерного перебора я привести не смог.

[Ktina]

worm2 в сообщении #969925 писал(а):

Ktina, где Вы взяли эту задачу?

Кацечка во сне нашептала.

(Оффтоп)

Знал бы кто, как мне без неё плохо

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

[hippie]

Записал подробно перебор, о котором писал выше.

hippie в сообщении #969747 писал(а):

Доказательство можно провести в 4 этапа. Первые 3 делаются простым перебором.

I) Обозначим вершины правильного семиугольника буквами А, Б, В, Г, Д, Е, Ё.
Пусть из них выбрано не менее трёх, таким образом, чтобы среди них не было лежащих в вершинах равнобедренного треугольника.
Предположим, что среди выбранных вершин нет пары соседних. Тогда обязательно есть пара вершин, лежащих через одну. Для определённости будем считать, что это вершины А и В. Тогда вершины Б, Д и Е не могут быть выбраны, т.к. образуется равнобедренный треугольник; а вершины Г и Ё — потому что нет пары соседних вершин. Противоречие.
Следовательно, среди выбранных вершин обязательно есть пара соседних. Для определённости будем считать, что это вершины А и Б. Тогда вершины В, Д и Ё не могут быть выбраны, т.к. образуется равнобедренный треугольник. Также, не могут быть ОДНОВРЕМЕННО выбраны вершины Г и Е. Следовательно выбрана только одна из вершин Г или Е. Заметим, что конфигурации АБГ и АБЕ переходят друг в друга при симметрии.
Таким образом, в правильном семиугольнике можно отметить не более трёх вершин, причём все допустимые тройки вершин конгруэнтны (переходят друг в друга при повороте или симметрии).

II) Обозначим вершины правильного четырнадцатиугольника буквами от А до М.
Эти вершины можно разбить на наборы вершин двух правильных семиугольников: «нечётного» (А, В, Д, Ё, З, Й, Л) и «чётного» (Б, Г, Е, Ж, И, К, М). Если в четырнадцатиугольнике отмечено 6 точек, то в каждом из указанных семиугольников отмечено по 3 точки.
Не уменьшая общности можно считать, что в «нечётном» семиугольнике отмечены точки А, В и Ё. Тогда в «чётном» не могут быть отмечены вершины Б, Г и К, т.е. отмечены 3 из вершин Е, Ж, И, М. Тройки ЕЖИ, ЕЖМ и ЕИМ являются вершинами равнобедренных треугольников. Следовательно, выбраны точки Ж, И, М.
Таким образом, если в правильном четырнадцатиугольнике отметили 6 допустимых вершин, то эта конфигурация конгруэнтна набору А, В, Ё, Ж, И, М.

III) Обозначим вершины правильного двадцативосьмиугольника буквами от А до Ъ.
Эти вершины можно разбить на наборы вершин двух правильных четырнадцатиугольников: «нечётного» (А, В, Д, Ё, … , Щ) и «чётного» (Б, Г, Е, Ж, … , Ъ).
Предположим, что из вершин двадцативосьмиугольника удалось выбрать допустимый набор из более чем десяти точек. Тогда в одном из четырнадцатиугольников (для определённости будем считать, что в «нечётном») выбрано 6 вершин.
При этом не уменьшая общности можно считать, что выбраны вершины А, Д, Л, Н, С, Щ.
Тогда в «чётном» четырнадцатиугольнике не могут быть выбраны вершины, лежащие на серединных перпендикулярах к парам вершин из «нечётного» четырнадцатиугольника, т.е. вершины Б, Е, Ж, И, К, М, О, Т, Ф, Ц, Ш и Ъ. Т.е. в «чётном» четырнадцатиугольнике, в этом случае, могут быть отмечены только вершины Г и Р.

[grizzly]

Я не планировал заниматься плагиатом, а пытался только дальше смотреть на $7! = 2.5\cdot 2016.$ Но в итоге получился плагиат идеи hippie. Долго сомневался, привести здесь это рассуждение или нет, и таки решил оставить.

Я рассматриваю правильные 5-угольники. В них можно выбрать только 2 вершины без равнобедренного треугольника (далее РТ). Это уже даёт оценку 2016 (думаю, где-то здесь зарыта авторская задумка).

Дальше, как у hippie:
Выделяем в нашем 7!-угольнике правильный 15-угольник. Легко видеть, что должен найтись такой, у которого каждый из трёх 5-угольников (здесь строим не по чётности, а по модулю 3: 1-4-7-10-12, и т.п.) должен иметь 2 красные вершины.
Выберем 2 вершины у первого. Не уменьшая общности можно считать, что это подряд идущие вершины 1--4 (здесь мы пользуемся тем, что перестановка вершин с произвольным шагом по циклу сохраняет РТ как инвариант).
Далее можно расписать весь перебор невозможности выбрать ещё по 2 вершины в остальных треугольниках. Этот перебор я честно проделал руками за несколько минут -- он совсем небольшой, поскольку рамсеевская теория болезненно переносит всякую равномерность.
В итоге получаем не более 5 точек на каждый правильный 15-угольник.
Ну и там ещё точка #2016 оставалась, так я уже про неё не вспоминаю за ненадобностью.

-- 28.01.2015, 22:57 --

worm2 в сообщении #969925 писал(а):

Если моя программа не врёт, то довольно любопытные факты вскрываются. Например, в правильном 15-угольнике нельзя выбрать более 4 вершин, хотя в 14-угольнике помещалось аж 6. Так что оценку можно опустить до $5040/15\cdot 4=1344$.

Программа не врёт. А если учесть, что первые 2 точки можно выбирать подряд (поскольку проход по вершинам правильного $n$-угольника по циклу с шагом не кратным $n$ сохраняет равнобедренные треугольники), то сделать этот перебор вручную не так уж сложно (где-то полчаса, я попробовал :)

[Evgenjy]

Ktina, у Вас есть хорошее математическое решение для 2015 красных точек, или может быть красных точек не 2015, а 2017?

[Ktina]

Evgenjy
Если бы было 2017, задача решалась бы на уровне маткружка 7-го класса.
Разбили бы все точки на пятиугольники, в одном из которых три точки оказались бы красными. Вот и вся любовь.

[Evgenjy]

Существует плохое решение этой задачи. Вот оно.
Разобьем окружность на 140 дуг: по 36 точек на каждой дуге. Найдется дуга на которой лежит не менее $15$ красных точек ($14\cdot140=1960<2015$). Согласно последовательности $A003002$ среди номеров точек на выбранной дуге найдется трехчленная арифметическая прогрессия. Соответствующие точки составят равнобедренный треугольник.
Ktina, у Вас есть хорошее математическое решение этой задачи?

[Deggial]

Evgenjy в сообщении #971600 писал(а):

Согласно последовательности $A003002$

Если что, есть специальный тег oeis.

[Ktina]

Evgenjy в сообщении #971600 писал(а):

Ktina, у Вас есть хорошее математическое решение этой задачи?

Мне очень жаль.