Al Zimmermann's: AP Math

[dimkadimon]

Стартовал новый конкурс Ал Зиммерманн: http://azspcs.com/Contest/APMath

На этот раз задача сложная и за несколько часов не решится. Задача похожа на эту: https://en.wikipedia.org/wiki/No-three-in-line_problem. Но тут несколько добавочных условий:

1. Решетка шестигранная.
2. Можно иметь 3 точки в линию если одна точка не лежит ровно по середине других двух.

[traffic_lights]

Потрясающе: начиная с n=27 пока лучшие решения нашли не более одного человека. Такого на моей памяти еще не происходило. Заодно очевиден и алгоритм поиска ответа для n=6 (подсказка кроется в опубликованном "Best Raw Score").

[traffic_lights]

Из ответа мне в дискуссионной группе Tim'ом Foden'ом (он продемонстрировали самый впечатляющий результат в конкурсе "Non-Coplanar Points". По уникальности его достижения пока к нему никто не приблизился за все время проведения конкурсов) можно извлечь очень ценную информацию: хотя занимающий первое место участник и значительно оторвался от остальной группы, его результаты все еще далеки от оптимальных. А так как состав лидирующей группы очень сильный, то нас ждет впереди захватывающее зрелище.

[traffic_lights]

traffic_lights в сообщении #1533009 писал(а):

Потрясающе: начиная с n=27 пока лучшие решения нашли не более одного человека. Такого на моей памяти еще не происходило.

Вывод из этого только один: даже для малых n искать оптимальные решения - это пустая трата времени.

[dimkadimon]

traffic_lights в сообщении #1533073 писал(а):

его результаты все еще далеки от оптимальных

От куда вы знаете какие должны быть оптимальные результаты?

Я думаю в этом конкурсе очень важно хорошо использовать симметрию чтобы уменьшить область поиска.

[zykov]

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

[dimkadimon]

Не согласен. Симметрии там очень много. Я нашел 5 разных типов симметричных решений и уверен что их еще больше. Полный перебор возможен только для малых n. Для меня даже отжиг слишком медленный и не дает хороших результатов. Поэтому мне кажется задача наоборот интересная.

-- 30.09.2021, 21:22 --

Кстати можно решать 1D версию задачи: сколько можно выбрать точек в отрезке $[1,n]$ чтобы не было трех точек в арифметической прогрессии? Оказывается эту задачу уже изучали:

https://en.wikipedia.org/wiki/Salem%E2%80%93Spencer_set
https://oeis.org/A065825

Кстати недавно доказали что количество таких точек должно быть меньше $n/log(n)$ (смотрите тут https://arxiv.org/pdf/2007.03528.pdf).

Можно разделить наш шестиугольник на отдельные ряды и заполнить каждый ряд отдельно. Это нам даст верхнюю границу оптимального решения для нашей задачи.

[traffic_lights]

dimkadimon в сообщении #1533293 писал(а):

От куда вы знаете какие должны быть оптимальные результаты?

Я такого не говорил: мой анализ основан на том очевидном факте, что, начиная с n=27, все лучшие результаты единичны. При этом лидеру конкурса, отрыв которого огромен, лучший результат для малых n не принадлежал, что следует из ответа Tim'а Foden'а.

-- 30.09.2021, 15:49 --

dimkadimon в сообщении #1533293 писал(а):

Я думаю в этом конкурсе очень важно хорошо использовать симметрию чтобы уменьшить область поиска.

Это очевидный факт, следующий из постановки задачи.

[traffic_lights]

dimkadimon в сообщении #1533305 писал(а):

Я нашел 5 разных типов симметричных решений и уверен что их еще больше.

Если на подмножествах исходной фигуры, не обладающих ее симметрией, то да.

[Herbert Kociemba]

dimkadimon в сообщении #1533305 писал(а):

Я нашел 5 разных типов симметричных решений и уверен что их еще больше.

I think there are exactly 9 types of symmetries a regular hexagon can have.

0: no symmetry
1,2,3: No reflectional symmetry but rotational symmetry by 60°, 120° or 180°.
4,5: Reflectional symmetry (one axis through vertices or one axis through centers of edges) and no rotational symmetry
6: Reflectional symmetry (one axis through vertices and one orthogonal axis through center of edges) and rotational symmetry by 180°
7: Reflectional symmetry (three axes through vertices and three axes through center of edges) and rotational symmetry by 60°
8,9: Reflectional symmetry (three axes through vertices or three axes through center of edges) and rotational symmetry by 120°

[traffic_lights]

traffic_lights в сообщении #1533009 писал(а):

Заодно очевиден и алгоритм поиска ответа для n=6 (подсказка кроется в опубликованном "Best Raw Score").

dimkadimon, Вы мне ответили в дискуссионной группе у Al'а, что связи решения для n=6 с "Best Raw Score" не нашли. А я как раз и намекал на симметрию. Или я ошибался?

[dimkadimon]

traffic_lights Я нашел $n=6$, но без симметрии. Возможно есть симметричное решение,.

-- 01.10.2021, 19:39 --

Thank you Herbert Kociemba. That's very useful. Some of these are difficult to construct though. My brain struggles with hexagonal grids.

[traffic_lights]

dimkadimon
Спасибо: кажется, я понял причину внушительного отрыва "Paulsen / Paulsen" от остальных.

[dimkadimon]

traffic_lights, тогда жду от вас хороших результатов!

[Herbert Kociemba]

With a quite stupid program I now can find the solutions for small N and took a look at the symmetry. The N=2 (6 cells) solution obviously has symmetry type 7, N=3 (12 cells) has symmetry type 8, my N=4 (18 cells) solution has symmetry type 4, the N=5 (27 cells) solution has symmetry type 9, the nice N=7 (42 cells) solution also has symmetry type 7, the full symmetry group D6 of the hexagon. My solutions to N=6 and N=11 also have some symmetry, but there are parts of the contest and so I will not give details here.
Nevertheless it is all but sure if for larger N the optimal solutions have some sort of symmetry.