задача на формулу включений-исключений ?

[Yury_rsn]

Yury_rsn в сообщении #1420764 писал(а):

запрограммировал в таблице эту задачку.
https://docs.google.com/spreadsheets/d/ ... edit#gid=0

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

Кстати, для $N=$НОК$=315$ можно отбросить прямые скобки в формуле и получить количество невычеркнутых в виде $N(1-2/5)(1-2/7)(1-2/9)$, т.е., 105.

А для $N=35$ просто по пропорции, прикидочно - $105/9=11,67$

[Yury_rsn]

Yury_rsn в сообщении #1420764 писал(а):

запрограммировал в таблице эту задачку.
https://docs.google.com/spreadsheets/d/ ... edit#gid=0

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

Ок. Попробую задать еще один вопрос, который меня в этой ситуации интересует.
Если рассматривать аналогию с решетом, то "пустые дни" - это как бы аналог простых чисел.
В решете Эратосфена они называются невычеркнутыми числами.

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

Например, в периоде длины 5 вычеркнем первое и второе число. Мы вычеркнули классы чисел, сравнимых с 1 и 2 по модулю 5. Обозначу это так - $5(1,2,-,-,-)$
Естественно, во всех остальных пятерках будет видна та же самая картина. Поэтому, нам надо теперь вычеркнуть в периодах по 7 и 9 оставшиеся числа - 3, 4, 5. Числа 6 и 7 - уже вычеркнуты в периоде по 5.
Т.е., первая очевидная расстановка, которая позволяет вычеркнуть сплошной интервал длиной 8, это:
$5(1,2,-,-,-)$
$7(-,-,3,4,-,-,-)$
$9(-,-,-,-,5,-,-,8,-)$
Девятое число уже невычеркнутое.

Еще вариант длиной 8:
$5(1,2,-,-,-)$
$7(-,-,3,-,5,-,-)$
$9(-,-,-,4,-,-,-,8,-)$

А вот эта расстановка дает интервал длиной 9
$5(1,-,3,-,-)$
$7(-,2,-,4,-,-,-)$
$9(-,-,-,-,5,-,7,-,-)$

Какая возможна максимальная длина сплошного интервала невычеркнутых чисел?

Интересует именно общая закономерность -
Как это зависит от длин периодов и от их количества?

(К примеру, если мы возьмем периоды длиной 7, 11 и 13, то понятно, что вычеркивая по два числа в каждой строке мы никак не сможем вычеркнуть семь чисел подряд с начала интервала.
Но если добавить еще одну строку, например с длиной 17, то появляются варианты удлинения сразу до 9 или 10, а то и больше)

[Yury_rsn]

Pphantom в сообщении #1420505 писал(а):

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

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

Я, наверное, ошибся?

[Pphantom]

В первой части - не ошиблись. Я просто до сих пор не понимаю, что сложного вы нашли в задаче, решаемой за 5-10 минут максимум. В исходной формулировке она тривиальна, а какой-то внятной общей формулировки так и не появилось (как следствие, и обсуждать пока нечего).

[Yury_rsn]

Pphantom в сообщении #1420960 писал(а):

что сложного вы нашли в задаче, решаемой за 5-10 минут максимум. В исходной формулировке она тривиальна, а какой-то внятной общей формулировки ..

Ок. Постараюсь еще раз сформулировать.
1. У меня в памяти осталось такое впечатление, что я где-то, в каких-то книжках по комбинаторике, видел задачи подобного типа. Но вспомнить или найти где именно, сейчас не получилось. Вроде бы есть похожие темы, но как-то не то. (Формула включений-исключений, например)

2. Подумалось, что может кто-то на форуме подскажет. Типа, помощь зала.

3. Я специально сформулировал задачу в самом примитивном виде, причем примерно в том же стиле, как такие задачи пишут в учебниках по комбинаторике (или даже в школьных учебниках) - как она мне запомнилась. И еще для того, чтобы максимально натолкнуть на мысль.

Поэтому. Решать ее не надо. Сложного там ничего нет по определению.
Тот материал, который я ищу, как раз и нужен для того, чтобы корректно и правильно сформулировать "в общем". Потому что многие нюансы мне самому непонятны.

Если никто ничего не вспомнил, или не имеет желания напрягать память - ну, ничего страшного.
Отрицательный результат - тоже результат.
Спасибо, в любом случае

[Yury_rsn]

Pphantom в сообщении #1420586 писал(а):

Может быть, тогда стоит начать с более простой задачи: чему равен период идеально точного повторения расписания (в рамках исходных условий задачи)?

Кстати, именно с помощью этой идеи можно доказать бесконечность простых чисел в решете Эрастосфена.
Я как раз ее имел в виду, когда задавал вопрос в ветке post1402598.html#p1402598 :

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

Yury_rsn в сообщении #1402598 писал(а):

А разве из метода построения решета Эратосфена нельзя увидеть бесконечность простых чисел?

А как? Вдруг после очередного простого все числа окажутся вычеркнуты?

(просьба сильно не ругаться, я в той ветке тоже продублирую этот коммент)

[Yury_rsn]

Наверное, это доказательство "в решете" слишком тривиальное, и достаточно очевидное, что никто не видит необходимости обсуждать?

Только для меня странно, что в Википедии:

Yury_rsn в сообщении #1402982 писал(а):

Вот в Википедии https://ru.wikipedia.org/wiki/%D0%A2%D0 ... %B4%D0%B0#Пинаско
дано доказательство Пинаско (где-то в середине страницы)

перечислены все достаточно простые доказательства, от Евклида до сегодняшних дней, но еще одно элементарное доказательство, которое гораздо проще рассуждений Пинаско, не упомянуто.

Имеет смысл написать это доказательство, или оно так очевидно, что говорить не о чем?

[Pphantom]

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