Задача про полоски с дырками

[waxtep]

Кстати, об оптимальной стратегии. Нас, кажется, явно автор темы не просил о прогрессиях, важно чтобы каждый следующий тык левым зубцом был достаточно далеко от предыдущего тыка правой. Т.е. вот эти последовательности не обязаны быть прогрессиями, а только чтоб каждый их член отличался от соответствующего члена прогрессии на неотрицательную монотонно неубывающую величину. Это, кажется, даёт ещё сколько-то свободы в поиске оптимальной тыкательной стратегии

[anahronizm]

waxtep в сообщении #1716528 писал(а):

отдельный вопрос, видимо: является ли такая наивная стратегия оптимальной

Я пробовал разрисовывать отдельные полоски, на каждой из которых проход только одной вилки. Потом накладывал несколько полосок "друг на друга": укладывал одну над другой и смотрел вертикальные результаты. Получалось, что "бить вилкой" в первую свободную ячейку не самый оптимальный путь. Но как найти оптимальный порядок вилок я, конечно, представить не смог.

[wrest]

anahronizm в сообщении #1716568 писал(а):

Получалось, что "бить вилкой" в первую свободную ячейку не самый оптимальный путь.

Тут хотелось бы увидеть пример, чтобы понять критерий "оптимальности". У нас же: либо данная полоска полностью в дырках, либо нет. Если одним способом осталась одна целая клетка, а другим - три, это не говорит нам какой способ лучше, они оба плохие.

[anahronizm]

wrest в сообщении #1716574 писал(а):

хотелось бы увидеть пример

Увы, примера не будет. Просто не помню уже, какие это были "вилки", с какими проходами и какой длины полоску я брал. Просто развлекался, перекладывая в разных положениях, вот и заметил такой момент. Так что строгого утверждения нет.

[waxtep]

wrest в сообщении #1716574 писал(а):

Тут хотелось бы увидеть пример, чтобы понять критерий "оптимальности".

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

anahronizm в сообщении #1716568 писал(а):

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

Верю, ведь без труда не выловишь и рыбки из пруда Спасибо за увлекательную задачку

[anahronizm]

waxtep в сообщении #1716580 писал(а):

Спасибо за увлекательную задачку

Рад, что смог дать повод для развлечения.
Если ещё что-то придумаю, напишу.

[waxtep]

waxtep в сообщении #1716555 писал(а):

Т.е. вот эти последовательности не обязаны быть прогрессиями, а только чтоб каждый их член отличался от соответствующего члена прогрессии на неотрицательную монотонно неубывающую величину. Это, кажется, даёт ещё сколько-то свободы в поиске оптимальной тыкательной стратегии

Если действовать не наивно, и забить на прогрессии, точно можно улучшить результат. Посмотрим на примере двух вилок.
I. Наивная стратегия:
- вилка 1, проход 1: (1,3), (6,8), (11,13), ...
- вилка 1, проход 2: (2,4), (9,11), ...
- вилка 2, проход 1: (5,9), ...
- вилка 2, проход 2: (7,11), ...

Мы покрыли 9 клеток подряд, но не 10-ую.

II. Коварно-беспринципная стратегия:
- вилка 1, проход 1: (1,3), (6,8), (11,13), ...
- вилка 1, проход 2: (2,4), ! (10,12), ...
- вилка 2, проход 1: (5,9), ...
- вилка 2, проход 2: (7,11), ...

За счет вольного расположения второго тыка первой вилки во втором проходе мы покрыли уже 13 клеток подряд, но не 14-ую.

Физически я таскаю в экселе группы клеток, где (вилка $i$, проход $s$) отображается полоской в $6i+2s-3$ клеток, из которых покрашены две клетки, находящиеся на расстоянии $i$ от центральной. Полоски одного вида (размера) не могут налегать друг на друга

-- 29.01.2026, 02:59 --

Тремя вилками могу покрыть $43$ клетки подряд в беспринципной стратегии, в сравнении с $13$ в наивной. В целом, стратегия тоже прямолинейная (и тоже не факт, что оптимальная!): пытаться заткнуть очередную дырку полоской наименьшего размера, не всегда придерживаясь максимально плотного расположения полосок одного размера. Её кстати вроде тоже легко запрогать.
Так, пока рука бойцов колоть устала, перерыв

[wrest]

waxtep в сообщении #1716607 писал(а):

- вилка 1, проход 2: (2,4), ! (10,12), ...

Так это же вроде против условий. Я так понял что "вилка" это сразу все дырки которые она делает обоими зубами вперёд и назад по полоске. То есть "интервал" (см. стартовое сообщение) фиксирован.

[waxtep]

wrest в сообщении #1716615 писал(а):

Так это же вроде против условий. Я так понял что "вилка" это сразу все дырки которые она делает обоими зубами вперёд и назад по полоске. То есть "интервал" (см. стартовое сообщение) фиксирован.

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

[wrest]

waxtep в сообщении #1716619 писал(а):

Творческая интерпретация условий что интервал не меньше указанного.

С произвольным переменным интервалом (но "не меньше указанного") внутри прохода одной вилки, как мне кажется, можно покрыть все числа конечным (небольшим - единицы) количеством "вилок". А если можно ещё поворачивать назад (т.е. квадрат/модуль переменного интервала не меньше указанного), то и одной

[waxtep]

wrest в сообщении #1716635 писал(а):

С произвольным переменным интервалом (но "не меньше указанного") внутри прохода одной вилки, как мне кажется, можно покрыть все числа конечным (небольшим - единицы) количеством "вилок". А если можно ещё поворачивать назад (т.е. квадрат/модуль переменного интервала не меньше указанного), то и одной

Мне с ходу не очевидно, наверное, не поленюсь попробовать запрогать в выходные. Отрицательный интервал (наложение, или противоестественный его расчет), наверное, уж чересчур

[waxtep]

wrest в сообщении #1716635 писал(а):

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

Да, похоже, Вы правы: если презирать прогрессии, кажется, достаточно четырех вилок, чтобы покрыть $\mathbb{N}$. Даже трех с половиной: длина покрытой полосы уже перевалила сотню тысяч, а программа и не пытается совершить второй проход четвертой вилкой. Значит, это скучно, и лучше вернуться к прогрессиям.
Но как изобразить... этот танец полосок? Или, может быть, лучше, подбор комбинации на замке сейфа. Тут думать надо, однако (над стратегией, более оптимальной, чем наивная, - если она существует). Можно устроить тупой перебор всех взаимных расположений, но это же зверская комбинаторика полезет, годно только для единичных количеств вилок...

[waxtep]

anahronizm в сообщении #1716568 писал(а):

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

В общем, уже для двух вилок есть стратегия лучше наивной, позволяющая покрыть $10$ клеток подряд, вместо $9$ (в исходной постановке задачи, с прогрессиями). Нагляднее посмотреть на оптимальную стратегию для трех вилок, она дает покрытие полосы в $24$ клетки, вместо $13$ в наивной:

- вилка 1, проход 1: (1), (4, 6), (9, 11), (14, 16), (19, 21), (24)
- вилка 1, проход 2: (1, 3), (8, 10), (15, 17), (22, 24)
- вилка 2, проход 1: (1), (8, 12), (19, 23)
- вилка 2, проход 2: (5, 9), (18, 22)
- вилка 3, проход 1: (2), (13, 19)
- вилка 3, проход 2: (1, 7), (20)

Для четырех вилок максимальное покрытие $33$ клеток вместо $16$ в наивной стратегии. И это считается уже минут 5, поскольку максимальное покрытие ищется в общем периоде размера $\operatorname{lcm}(5,7,11,13,17,19,23,25) =185\,910\,725$

Дааа... ну и ну!

[waxtep]

waxtep в сообщении #1716716 писал(а):

Для четырех вилок максимальное покрытие $33$ клеток вместо $16$ в наивной стратегии.

Поправка: четырьмя вилками можно больше, по крайней мере, $34$. Не учитываю, что период второго прохода четвертой вилки $25$ кратен периоду первого прохода первой $5$; тут надо чуть аккуратнее

[waxtep]

Ммм, четырьмя вилками можно аж $41$. Вот необлагороженный вывод программы:

[1, 2, 6, 1, 7, 1, 0, 4, 1, 5, 1, 4, 3, 1, 0, 1, 3, 2, 1, 7, 1, 6, 2, 1, 2, 1, 5, 3, 1, 2, 1, 2, 5, 1, 3, 1, 2, 4, 1, 0, 1]

где 1 - следы от уколов первого прохода первой вилки, 2 - от второго прохода первой вилки, ..., 7 - от первого прохода четвертой вилки, 0 - от второго прохода четвертой вилки. Если какая-то клетка проткнута несколько раз, отображен самый ранний укол.

Последовательность $4,10,24,41$ OEIS знает один раз, и она кажется не о том. Но в общем четырьмя вилками уже можно разорвать в клочья полоску длины $41$, а заданной исходно длины $36$ - и подавно.
Пять вилок текущая версия программы на моем нотике будет считать несколько дней, а шесть - несколько лет, хм. Нужны свежие идеи, коллеги