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

[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.
Ранее я уже показывал, каким образом можно вычислить сдвиг. Как я понимаю, за левый зуб можно принять правый, тогда изменится сдвиг, размер дырки и общий вид формулы, но она будет давать те же значения.
Надеюсь, ничего не перепутал. Написал, как мог. Понимаю, что математики сделали бы лучше.
Как подобраться к формуле, которая вычисляет размер максимально забитой группы при заданных множествах, пока не придумал.