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

[waxtep]

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

Стало интересно попробовать описать все не проколотые элементы при любом заданном количестве вилок. И не обязательно такими вилками, как в задаче.
Вот Вы показали, как можно описать все не проколотые клетки если вилка одна. Удобна ли такая запись при вычислении не проколотых элементов ?
Или вот задача: предположим, что у нас есть бесконечная полоска. И по ней прошлись первой и второй вилкой по два раза (как условие в задаче). Как выразить все не проколотые элементы на этой бесконечной полоске? Да так, чтобы такая запись была удобна для использования, например, вычисления всех не проколотых элементов на заданном интервале.
А если берётся только вторая и третья вилка с их двумя проходами ? Или только пятая, седьмая и восьмая ?
Было бы здорово записать общую формулу.

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

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

Но, скорее всего, не рассматривали отдельно, например, вилки 2 и 3 или вилки 3,4 и 6.

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

Ничего толкового пока для пяти и более вилок мне выжать не удалось, хотя старался я очень, в том числе, пытаясь жульничать и подглядывать Даже для четырех уже так себе: совсем быстро считающий вариант дает максимум $34$ клетки, а уже не очень-то быстрый - $38$; это при известной стратегии, позволяющей проколоть $41$ клетку подряд. Для пяти, шести вилок разница по сравнению с известными стратегиями, дающими $71, 126$ проколов, - еще драматичнее (хуже работает). Для семи и более вилок, соответственно, тоже ничего интересного (зато можно довольно быстро посчитать ). Хочется попробовать формализовать, что нужно максимизировать "на полпути" для достижения оптимального (или, по крайней мере, "очень хорошего") результата в конце, но пока не умею. А без разбиения на такие блоки, задача выглядит гробовой в силу астрономического количества вариантов уже для совсем малого количества (до десяти) вилок

[anahronizm]

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

придется вычислить все проколотые разными вилками клетки, и сказать, что "а не проколотые - это все остальные".

Это немного скучно...
Я придумал способ описания всех не проколотых клеток. Кривенько, косенько, но в виде формулы. Наверное, математики и так это знают, но попробую рассказать, чего я наворотил.
Для этого сначала нужно озвучить более простую задачу:
Задача про плохих стрелков
Два стрелка стреляют одновременно по одному ряду мишеней. Начинают оба с первой, крайней левой мишени. Целятся, стреляют. Независимо от результата, целятся и стреляют в следующую мишень, которая расположена правее. Вот только стреляют плохо: первый стрелок попадает только в каждую (a)-тую мишень, второй только в каждую (b)-тую мишень. Стрельба прекращается, когда оба стрелка попадут в одну и ту же мишень.
Требуется найти способ описания номеров тех мишеней, в которые не попал ни один стрелок. Известно, что а не равно b и они взаимно простые.
Возможно ли решение записать в виде некоего выражения (функции) ?
Например: первый попадает только в каждую 4-ю мишень, второй в каждую 5-ю. Стрельба прекратится на 20-й мишени, в которую попадут оба. Как можно описать номера
1,2,3,6,7,9,11,13,14,17,18,19 - по этим мишеням промахнулись оба стрелка ?
Намного ли усложнится задача, если стрелков будет 3, 4, 5 или...немного больше ?
Представьте, что при попадании в одну мишень одновременно, стрелки продолжают стрелять по мишеням дальше. Можно ли описать все мишени, по которым не попал ни один из стрелков ?
Да, можно записать выражение, которое описывает номера всех мишеней, в которые не попал ни один из стрелков, если представить, что ряд мишеней бесконечен.
Но для этого я рассмотрел вариант ещё проще, когда стрелок только один и он, например, попадает только в каждую пятую мишень. Конечно, легко описать все мишени, в которые он попал как 5х.
А вот как описать мишени под номером 1,2,3,4 ?
Для этого я ввёл понятие интервальной переменной $T_i$ которая принимает целые значения от 1 до i.
Тогда все мишени, в которые не попал стрелок можно описать как

$$5x+T_4$$

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

-- 01.03.2026, 11:18 --


Или в общем виде:

$$ax+T_{a-1}$$

-- 01.03.2026, 11:49 --

А если стреляют два стрелка, как в задаче про плохих стрелков? Т.е. первый попадает в каждую четвёртую мишень, второй попадает в каждую пятую мишень. Как описать те мишени, в которые не попал ни один из стрелков ?
Для этого можно использовать формулу:

$$5*4*x+5T_3 +4T_4$$

Или в общем виде, чтобы было более понятно (если первый стрелок попадает только в каждую а-тую мишень, а второй стрелок в каждую b-тую мишень):

$$abx+aT_{b-1}+bT_{a-1}$$

Если же стрелков будет трое, и каждый из них попадает только в каждую a-тую,b-тую, с-тую мишень соответственно, то все не пробитые мишени можно описать так:

$$abcx+abT_{c-1}+acT_{b-1}+bcT_{a-1}$$

Эту формулу можно расширить на любое количество стрелков.
Так же можно описать номера тех мишеней, в которые не попал ни один из двух стрелков, если один попадает только в каждую, например, 5x+1 мишень, а второй только в каждую 7х+2 мишень.
Тогда формула будет выглядеть так:

$$5*7*x+5T_6+7T_4+16$$

Где 16 – значение левой или правой части диофантова уравнения 5x+1=7у+2 при верном его решении.
можно обратить внимание, что рисунок распределения мишеней при этом не изменился, а только сдвинулся.
Вообще, если первый стрелок попадает только в каждую ax+$f_1$ мишень, а второй в каждую bx+$f_2$ мишень, то в общем виде эту формулу можно записать так:

$$abx+aT_{b-1}+bT_{a-1}+Q_1$$

где $Q_1$ - значение левой или правой части диофантова уравнения ax+$f_1$= bу+$f_2$ при верном его решении.
Аналогично записывается формула для трёх стрелков:

$$abcx+abT_{c-1}+acT_{b-1}+bcT_{a-1} +Q_2$$

где $Q_2$ -значение левой или правой части диофантова уравнения abx+$Q_1$= сx+$f_3$ при верном его решении, если третий стрелок попадает только в каждую сx+$f_3$ мишень.
Наверное, будет своевременно пояснить, что в этих задачах мы имеем дело с пересечением множеств определенного вида – для удобства назову их множествами с интервальной переменной.
Немного позже продолжу - времени не хватает.

[anahronizm]

Вот теперь можно подойти к решению первой задачи с вилками.
Для этого можно представить, что вилка представляет из себя два зуба в отдельности и каждый такой «зуб» при прохождении по бесконечной полоске организует множество с интервальной переменной, вернее, образует сразу два одинаковых множества, но одно сдвинуто на размер (дырка +1).
Можно описать пересечение таких множеств, используя интервальную переменную, но теперь такая переменная будет «не полной».
Например, если мы рассмотрим вилку с дыркой 1 и шагом 5, а первый удар левым зубом попадёт в 0, то два получившиеся множества можно описать как
5x+$T_4$ и 5x+$T_4$+2
а пересечение этих множеств

$$5x+T_{1,3,4}$$

где $T_{1,3,4}$ интервальная переменная, которая принимает значения 1,3 и 4.
Теперь рассмотрим множества «не проколотых клеток», если вилки две, например:
первая вилка имеет дырку 1 и шаг 5, вторая имеет дырку 2 и шаг 7, и обе попадут левым зубом в «клетку» с номером 0 (это нужно для того, чтобы пока не заморачиваться с вычислением сдвига Q).
Такие множества можно записать как 5x+$T_{1,3,4}$ и 7x+$T_{1,2,4-6}$, а все элементы их пересечения будет определяться формулой:

$$35x+5T_{1,3-6}+7T_{2-4}$$

где интервальные переменные $T_{1,3-6}$ и $T_{2-4}$ принимают значения 1,3,4,5,6 и 2,3,4 соответственно.
Заметно, что в этой формуле в интервальных переменных отсутствует некоторые элементы, которые можно определить, решив диофантовы уравнения:
5х=7у+3 и 7х=5у+2
Значения х будут определять тот элемент, который будет исключён из интервальной переменной (соответственно).
Аналогичным образом записывается формула для любого количества «вилок». При этом «вилки» могут иметь разное количество «зубьев» и разный размер «дырок». В зависимости от того, что брать за «левый» зуб, формулы будут отличаться, будет появляться сдвиг Q, но все они будут описывать одну и ту же картину распределения.
Понятно, что картина распределения будет являться периодичной и зеркально симметричной.

-- 01.03.2026, 12:14 --

Наверное, всё это давно известно и оформлено как положено в математике, но я этого не знаю. Просю прощения у уважаемых людей.

[waxtep]

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

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

вилка $i$ в проходе $s$ не прокалывает клетки $b_i^s\pm i+n\cdot(6i+2s-3)+r$, где $b_i^s$ - положение середины этой вилки при каком-то уколе, $n$ - любое целое число, а $r$ - любое натуральное число от единицы до $6i+2s-4$

Здесь $r$ - как раз "интервальная переменная". При объединении проколов от нескольких вилок появятся "неполные интервальные переменные".

Я пока тему отложил, в связи с отсутствием видимого прогресса и потоком прочих дел. Честно сказать, больше верю в вещи более приземленные, типа получения хорошей оценки снизу, чем в главный приз, - получение точной аналитической формулы. Но я не спец в этой области, мало ли как выйдет. По поводу эвристик, потенциально ведущих к хорошей оценке, кое-какие идеи есть, однако они требуют заметного времени на обдумывание и програзм, а им я сейчас не обладаю

[anahronizm]

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

они требуют заметного времени на обдумывание и програзм, а им я сейчас не обладаю

Да, времени всегда не хватает, я тоже занимался этим безобразием в обеденный перерыв и перед сном - какое уж тут время...
Спасибо Вам и всем собеседникам за помощь - вы сделали задачку интереснее, чем она была изначально.
Конечно, формулы не могут являться доказательством, но некоторые явные выводы можно сделать:
- То, что рисунок распределения остаётся одинаковым при одинаковых вилках, но появляется сдвиг, который может быть вычислен.
- распределение элементов на бесконечной полоске обладает периодичностью (симметрию нужно доказывать отдельно, но это не должно вызвать затруднений)
- в случае бесконечной полоски, сколь бы большое количество вилок мы ни взяли, всегда будут не проколотые клетки (можно ли тут говорить о бесконечном количестве вилок, я говорить не компетентен). Пусть количество сколь угодно огромно, но конечно - тогда всегда будут оставаться непробитые клетки и их номера можно вычислить (хоть эта задача и будет трудоёмкой).
И вот вопрос, который очень заинтересовал меня в процессе обсуждения - вывести формулу длины максимальной полоски из забитых клеток при заданном количестве вилок.
Понятно, что при заданных вилках такая формула будет давать вполне определённый результат, вне зависимости от того, какую стратегию мы будем применять - на периоде проявят себя все возможные стратегии.
Даже не знаю, как к этому можно подойти.
Так же можно вывести формулы количества различных групп пробитых и не пробитых клеток различной длины и координаты их расположения...
Спасибо ещё раз - вы все крутые ! Интересно было - жуть !
Но моя интуиция говорит, что это ещё не конец.
О, во ещё что - кажется вопрос таких распределений может быть очень востребован. Не могу объяснить - интуиция...

[anahronizm]

Забыл сказать: данный способ описывает все не пробитые клетки без повторений. Т.е. каждая непробитая клетка описывается только один раз.
Доказывать это я тоже не умею.

[anahronizm]

Всем снова здравствуйте.
Попытаюсь подробно разобрать один пример, чтобы было понятнее (да и самому не забыть).
Заранее извиняюсь, что не умею правильно выражаться математически.
Предположим, что мы проходимся вилкой (делаем удар) по бесконечной полоске с клетками. У вилки два зуба, которые прокалывают одновременно две разные клетки. Отступаем на определённое расстояние и снова делаем удар вилкой. Таким образом получаются пробитые и не пробитые клетки.
Пусть у вилки два зуба и дырка между зубьями равна 1. Левым зубом вилки мы пробиваем клетку под номером 0. Тогда правый зуб пробьёт клетку под номером 2.
Левым зубом отступаем вправо (или влево) на пять клеток и снова делаем удар. Тогда пробьются клетки 5 и 7 (если влево, то -5 и -3). И т.д.
Как я уже упоминал ранее, множество всех непробитых клеток можно выразить с помощью неполной интервальной переменной. В данном случае

$$5x+T_{1,3,4}$$

где $T_{1,3,4}$ - интервальная переменная, которая принимает значения 1,3 и 4.
Таким же образом можно выразить все непробитые клетки, если дырка равна 3, а отступать мы будем на 11:

$$11x+T_{1-3,5-10}$$

где $T_{1-3,5-10}$ - интервальная переменная, которая принимает значения 1,2,3,5,6,7,8,9,10.
А теперь рассмотрю составление формулы для всех непробитых клеток, которые будут оставаться при пересечении нескольких таких множеств (образно: словно несколько таких полосок "положили" друг на друга).
Пока не буду заморачиваться со "сдвигом" - пусть все вилки попадут левым зубом в клетку под номером 0.
И возьму несколько множеств с интервальной (неполной) переменной, пусть их будет три, например:

$$7x+T_{1,3-6}$$

$$10x+T_{1-5,7-9}$$

$$11x+T_{1-3,5-10}$$

Как я уже упоминал ранее, общая формула, которая определяет номера всех непробитых клеток на бесконечной полоске для трёх множеств будет выглядеть так:

$$abcx+abT_{c-}+acT_{b-}+cbT_{a-}+Q$$

где $T_{a-},T_{b-},T_{c-}$ неполные интервальные переменные, а Q - это "сдвиг", но пока он равен 0, т.к. все вилки левым зубом попали в 0.

-- 21.03.2026, 12:25 --

Теперь нам нужно определить, какие элементы отсутствуют в интервальных переменных в окончательной формуле.
Чтобы понять, какой элемент отсутствует в $T_{a-}$, необходимо решить уравнение:

$$110x=7y+2$$

где 2 это номер клетки, которую вилка пробьёт правым зубом при первом ударе, когда левый зуб попадёт в клетку под номером 0.
Решая данное уравнение, мы получим, что x равен 6. Именно этот элемент будет исключён из интервальной переменной в формуле.
Тогда интервальная переменная $T_{a-}$, примет вид $T_{1-5}$, т.е. будет принимать значения 1,2,3,4,5.
Чтобы понять, какой элемент отсутствует в $T_{b-}$, необходимо решить уравнение:

$$77x=10y+6$$

где 6 это номер клетки, которую вилка пробьёт правым зубом при первом ударе, когда левый зуб попадёт в клетку под номером 0.
Решая данное уравнение, мы получим, что x равен 8. Именно этот элемент будет исключён из интервальной переменной в формуле.
Тогда интервальная переменная $T_{b-}$, примет вид $T_{1-7,9}$, т.е. будет принимать значения 1,2,3,4,5,6,7,9.
Чтобы понять, какой элемент отсутствует в $T_{c-}$, необходимо решить уравнение:

$$70x=11y+4$$

где 4 это номер клетки, которую вилка пробьёт правым зубом при первом ударе, когда левый зуб попадёт в клетку под номером 0.
Решая данное уравнение, мы получим, что x равен 1. Именно этот элемент будет исключён из интервальной переменной в формуле.
Тогда интервальная переменная $T_{c-}$, примет вид $T_{2-10}$, т.е. будет принимать значения 2,3,4,5,6,7,8,9,10.
И формула номеров всех непробитых клеток на бесконечной полоске будет выглядеть так:

$$770x+70T_{2-10}+77T_{1-7,9}+110T_{1-5}$$

-- 21.03.2026, 12:47 --

Похожую формулу можно составить для любого количества множеств. Даже можно исключать несколько элементов в каждом множестве (это когда у вилки будет более двух зубов). Вот не думал пока, что будет происходить, если размеры "отступов" при ударах вилками будет не взаимно простыми числами.
Теперь по поводу "сдвига".
Дело в том, что куда бы ни попал левый зуб при первом ударе любой вилкой, общий рисунок забития на бесконечной полоске не изменится, а будет только сдвинут на некоторое Q. Если все вилки левым зубом попали в клетку с номером 0, то Q=0.
Ранее я уже показывал, каким образом можно вычислить сдвиг. Как я понимаю, за левый зуб можно принять правый, тогда изменится сдвиг, размер дырки и общий вид формулы, но она будет давать те же значения.
Надеюсь, ничего не перепутал. Написал, как мог. Понимаю, что математики сделали бы лучше.
Как подобраться к формуле, которая вычисляет размер максимально забитой группы при заданных множествах, пока не придумал.

[anahronizm]

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

И тогда размер максимальной проколотой полоски должен быть по идее похож на экспоненту, за счет такого лавинного объединения островков. Эксель для трех-шести вилок предлагает $\tilde M(k)=4,5355\exp{(0,5524k)}$, в принципе, хорошо ложится (одна-две вилки - ожидаемо плохо, потому исключил; надо бы больше точек, да где же их взять ):

$$\begin{tabular}{c|c|c|c|c|}$ k $ & 3 & 4 & 5 & 6\\ \hline $ M(k) $ & 24 & 41 & 71^{+} & 126^{+}\\ $ \tilde{M}(k) $ & 23,8 & 41,3 & 71,8 & 124,8\end{tabular}$$

Что-то мне подсказывает, что максимальная полоска для такой задачи всегда будет чётной. Может, я и ошибаюсь.
Да, вот ещё, я тут немного перефразировал задачу topic162875.html
мне показалось, в таком виде она легче для восприятия. Ну, дорога, грузовик...

[waxtep]

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

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

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

Кажется, для четырех вилок я считал честно, без каких-либо эвристик, и там максимальная длина проколотой полосы нечетная, $41$. Но мог конечно и ошибиться, тут очень желательно подтверждение (или опровержение) другого заинтересовавшегося задачей участника

[anahronizm]

mihaild в сообщении #1717527 писал(а):

anahronizm в сообщении #1717497

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

Уважаемый mihaild, представленные мной формулы говорят о том, что невозможно будет забить бесконечную полоску при сохранении условий задачи. Периодичность и симметрия тоже там. Можно оценить и плотность забития на периоде. Формулы-то я вывел, руководствуясь, возможно, слабыми доказательными основами. Но формулы верны и могут быть подвергнуты анализу.
Задачка действительно оказалась сложной, пока я не могу найти подходы к определению длины максимальной возможной полоски для произвольного количества вилок.
Можно было бы немного облегчить данный вопрос и попытаться определить минимальные и максимальные границы для длины таких максимальных забитых полосок.
Как я понял, математики определили такой интервал для ситуации, когда каждая вилка состоит лишь из одного зуба и если N - количество вилок, то длина максимально забитой полоски находится в пределах от N до 2N.

[anahronizm]

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

нужен какой-то серьезный прорыв в качественном понимании

Вот ещё возникла такая мысль: каждый раз, при добавлении вилки (с её двумя проходами), длина максимальной полоски будет увеличиваться, но прирост этого увеличения будет уменьшаться.
Как это выглядит:
первая вилка даёт непрерывную полоску = 4.
вторая вилка даёт непрерывную полоску = 10 (прирост в 2.5 раза)
третья вилка даёт непрерывную полоску = 24 (прирост в 2.4 раза)
Подозреваю, что прирост будет только уменьшаться и уже начиная с четвёртой вилки будет меньше двух.
Было бы здорово это доказать.

[waxtep]

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

Вот ещё возникла такая мысль: каждый раз, при добавлении вилки (с её двумя проходами), длина максимальной полоски будет увеличиваться, но прирост этого увеличения будет уменьшаться.
Как это выглядит:
первая вилка даёт непрерывную полоску = 4.
вторая вилка даёт непрерывную полоску = 10 (прирост в 2.5 раза)
третья вилка даёт непрерывную полоску = 24 (прирост в 2.4 раза)
Подозреваю, что прирост будет только уменьшаться и уже начиная с четвёртой вилки будет меньше двух.
Было бы здорово это доказать.

Интересное наблюдение, да. Мне лично кажется (доказать не берусь, чисто вопрос веры), что размер полоски зависит от числа вилок примерно экспоненциально, т.е. с увеличением числа вилок прирост будет приближаться к какой-то константе (монотонно или же будет колебаться туда-сюда вокруг нее). Какие-то соображения в пользу этого приводил здесь на 6-ой странице обсуждения. Эксель посчитал эту константу как $\approx1,7374$ при помощи МНК для 3-6 вилок. Может быть это $\sqrt{\operatorname{e}}\approx1,6487$? А может золотое сечение $\frac{\sqrt5+1}2\approx1,6180$? Корень из трех тоже неплох $\sqrt{3}\approx1,7320$. Да или еще что угодно.

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

[anahronizm]

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

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

Вот прям беда-беда!
Для меня лично. Я тут, по глупости, поспорил с коллегами (на огромную сумму в 1 рубль и прилюдный поджопник), что представлю доказательства, что при добавлении вилки прирост будет уменьшаться и, начиная с некоторой вилки, будет меньше 2-х. (я всем уже надоел разрисованными полосками)
У меня была такая мысль, что прирост снижается, быстро становится меньше двух и стремится к некоторому пределу. Вот и поспорил, что докажу, вернее, представлю доказательство.
Но как-то страшно. Поджопник получать совсем не хочется.
Люди, хорошие мои, помогите мне, остолопу, не получить поджопник и доказать, что прирост будет всегда меньше 2, начиная с некоторой вилки. Это минимальное условие, чтобы мне не опозориться.
Если доберётесь до значения предела (с доказательством), было бы вообще шикарно !
Коллегам честно скажу, что доказал не я - мне нужно только представить доказательство.
Спасите!!! У меня времени до Нового Года.
Сам я, конечно, подумаю чего-нибудь, но что-то сомнения меня берут...
Косвенно можно подойти к этому вопросу через плотность не проколотых клеток на периоде. Согласно формуле, которую я представил (с неполными интервальными переменными), плотность не проколотых клеток будет расти и приближаться к некоторому пределу.

[anahronizm]

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

Надо дальше копать

Задачка преподнесла новый сюрприз! По крайней мере, мне.
Сейчас расскажу:
Должен упомянуть немного о формулах, которые я представил - они верны и обладают некоторыми плюсами и минусами. Они описывают каждый "не проколотый" элемент на бесконечной полоске, причём только единожды, дают возможность точно определить плотность "проколотых" и "не проколотых" элементов на периоде. Показывают периодичность и симметрию. Но главное - они верны, когда периоды проходов вилок взаимно просты.
Мельком я упоминал об этом, но, видимо, на этом нужно было сделать акцент ещё раз в процессе озвучивания формул.
И вот тут и вылезает сюрприз, который приводит к хитрому раздвоению в задаче.
Если бы все периоды проходов вилок были взаимно простыми, то было бы совершенно безразлично, с какого места на бесконечной полоске начинать очередной проход новой вилкой. На полном периоде была бы реализована любая ситуация, любая стратегия.
Но когда появляется новый, не взаимно простой период, и центры всех дырок вилок никогда вместе не совпадают, то ломаются и формулы и рисунок забития (пока ещё не думал над этой ситуацией, возможно ли при этом полное забитие бесконечной полоски, у меня есть подозрение, что и тогда будут оставаться не пробитые элементы).
А вот если наложить условие, что центры дырок всех вилок будут иногда совпадать, то происходит удивительная штука - все последующие проходы вилкой, периоды которых не будут являться взаимно простыми с предыдущими (условие задачи о размерах дырки при этом сохраняется), будут всегда бить по уже проколотым клеткам.
(начал это проверять, но кажется, если сохранять условие задачи о размерах вилок, это будет происходить обязательно!)
Таким образом, если период прохода вилки НЕ взаимно простой с предыдущими проходами, и центр этой вилки иногда совпадает с центром не взаимно простой вилки, то этот данный проход вилкой вообще можно исключить из рассмотрения.
Например, рассмотрим проход вилки с периодом 25 (это будет на четвёртой вилке) и ударами зубьев на клетки номер 3 и 11. Тогда удары будут приходиться на те клетки, куда уже ударили зубья вилки с периодом 5 и ударами зубьев на клетки номер 1 и 3.
Здесь как раз происходит совпадение центров не взаимно простых вилок: у вилки с периодом 25 центр находится в клетке 7 и у вилки с периодом 5 там же. И тогда вилка с периодом 25 вообще перестаёт создавать новые пробитые клетки!
Вот тогда вопрос задачи о приросте длины для максимальной забитой полоски можно рассмотреть в двух вариантах:
1. Когда центры дырок всех вилок иногда совпадают (тогда можно учитывать только проходы вилок с простыми периодами)
2. Когда взаимно простые периоды не совпадают центрами вилок.
Предполагаю, что для первого варианта уменьшение прироста максимально забитой полоски будет постоянным (в смысле - уменьшаться постоянно) и стремиться к некоторому пределу, который можно красиво описать. Возможно, при этом варианте и максимально забитые полоски будут чётными, о чём я ранее упоминал.
А при втором варианте (при появлении не взаимно простого периода) будет происходить ... понятия не имею, что будет происходить. Дичь всякая.
Да уж, вот так задачка...

[anahronizm]

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

2. Когда взаимно простые периоды не совпадают центрами вилок.

Здесь следует читать: 2. Когда проходы с НЕ взаимно простыми периодами не совпадают (иногда) центрами вилок.
Извиняюсь за корявость.