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

[Yury_rsn]

Есть три бригады технического сопровождения, которые обслуживают некоторое учреждение.
Так получилось, что у всех трех бригад разные периоды вахты.
Первая бригада работает с периодом 5 дней, вторая - 7, третья - 9.
В каждой бригаде по два человека. И они могут работать только по одному дню в период.
Например, в первой бригаде один сотрудник работает в первый день от начала вахты, а второй, допустим в четвертый. И через каждые пять дней всё повторяется.
Во второй бригаде тоже самое - один может работать в каждый второй день из семи, а второй в каждый пятый из семи.
В третьей аналогично. Каждый сотрудник работает в один из дней, из девяти.

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

Вопросы:
- как посчитать количество дней за какой-то достаточно длинный промежуток времени, когда на вахте не было ни одного из сотрудников ни из одной бригады? (подходит ли нижеприведенная формула вкл-искл?)
- зависит ли от начальной расстановки номеров в периодах количество "пустых" дней, как это можно доказать?
---
Похоже что эта задача из раздела про формулу включений-исключений.
Но как учесть наличие двух чисел в периодах?
Допустим, возьмем достаточно большой интервал времени $N$.
Можно предположить, что количество пустых дней считается по формуле
$[N] - [N/(2\cdot5)] - [N/(2\cdot7)] - [N/(2\cdot9)] + [N/(2\cdot5\cdot2\cdot7)] +[N/(2\cdot5 \cdot 2\cdot9)] + [N/(2\cdot7 \cdot 2\cdot9)] - [N/(2\cdot5 \cdot 2\cdot7 \cdot 2\cdot9)]$
Однако, можно ли использовать формулу в таком виде с учетом того, что номера внутри периодов можно выбирать произвольно?

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

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

-- 13.10.2019, 16:12 --

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

[Yury_rsn]

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

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

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

Тот вопрос, который я убрал - он на самом деле звучит так:
а если внутри каждого периода не два числа, а больше? И если взять другие знаменатели, а не 5,7,9; и знаменателей больше, а не три?
- при каком соотношении этих параметров количество незаполненных дней может быть
равно нулю?
Можно ли это увидеть с помощью формулы включений и исключений, или это доказывается другими методами?

[Pphantom]

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

Пробовал и проверял. Но это же не доказательство.

Но способ не задавать вопросы с очевидными ответами.

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

Количество вычеркнутых остается примерно одинаковым, независимо от выбора номеров внутри периодов.

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

[Yury_rsn]

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

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

Да

На вложенной картинке:
- вверху нарисована диаграмма по условиям задачи, без выделения пустых дней;
- на второй диаграмме уже обозначены пропуски - 11 штук желтых вертикальных линий;
- на третьей наугад изменены два числа внутри каждого периода - 11 желтых;
- на четвертой еще раз наугад сдвинуты числа внутри периодов, но теперь уже 12 желтых.

https://docs.google.com/document/d/1I7n ... -VP6N/edit

[Pphantom]

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

[Yury_rsn]

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

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

НОК=315.

-- 14.10.2019, 09:24 --

уточню. Эта задача сформулирована упрощенно.
Чтобы подсказали тему в учебнике, где такие задачи рассматриваются подробнее.
Меня интересует общий случай. Например, если количество "бригад" бесконечно.
И если варьировать количество "работников" внутри каждой бригады.

Увидел ошибку в формуле в стартовом посте. Там двойки должны быть не в знаменателе, а в числителе.
$[N] - [2N/5] - [2N/7] - [2N/9] + [4N/(5\cdot7)] +[4N/(5\cdot9)] + [4N/(7\cdot9)] - [8N/(5\cdot7\cdot9)]$
В данном случае. если взять $N=35$, как на картинке, то количество пустых дней
$35- 14-10-7 +4+3+2 - 0 =13 $
Хотя во взятых наугад расстановках получается то 11, то 12.

[Someone]

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

Например, если количество "бригад" бесконечно.

Дык, формулу надо применять к полному периоду.

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

Хотя во взятых наугад расстановках получается то 11, то 12.

Боюсь, получится нечто бессмысленное. Впрочем, это смотря как сформулировать.

[Yury_rsn]

Someone в сообщении #1420658 писал(а):

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

Например, если количество "бригад" бесконечно.

Дык, формулу надо применять к полному периоду.

Полный период - это наименьшее общее кратное трех чисел 5, 7 и 9?
А если количество этих "знаменателей" неограниченно возрастает?

.

Цитата:

Боюсь, получится нечто бессмысленное. Впрочем, это смотря как сформулировать.

Прошу прощения, у вас получилось посмотреть ссылку с графикой - два коммента назад?

[Someone]

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

у вас получилось посмотреть ссылку с графикой - два коммента назад?

Получилось.
Я неудачно вставил цитаты в своё сообщение, в результате получилась путаница. Первый мой ответ относится ко второй цитате, а второй ответ — к первой цитате. Сейчас исправлю.

Исправление сообщения #1420658 писал(а):

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

Хотя во взятых наугад расстановках получается то 11, то 12.

Дык, формулу надо применять к полному периоду.

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

Например, если количество "бригад" бесконечно.

Боюсь, получится нечто бессмысленное. Впрочем, это смотря как сформулировать.

[Yury_rsn]

Цитата:

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

Например, если количество "бригад" бесконечно.

Боюсь, получится нечто бессмысленное. Впрочем, это смотря как сформулировать.

правильно ли я понимаю, что эта задача не является достаточно известной?
и даже у гуру в памяти сразу не возникают аналоги?

Я более подробно поэкспериментировал при длине $N=35$ .
Даже для трех "бригад" количество вариантов слишком велико. Всех не перебрать.
Наиболее часто получалось количество пустых дней, равное 11 и 12.
Несколько раз выпадало 10. И только один раз получилось 13.

Сейчас попробую поклацать при длине $N=315$

[Yury_rsn]

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

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

Количество пустых дней считается для интервала 35, и для интервала 315.

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

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

[Someone]

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

Наиболее часто получалось количество пустых дней, равное 11 и 12.
Несколько раз выпадало 10. И только один раз получилось 13.

Ваша формула не учитывает выбор дней. Поэтому при интервале, не кратном общему периоду, даёт результат, не совпадающий с "экспериментальным".

[Yury_rsn]

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

Есть как бы похожесть на решето, поэтому и возникла формула включений-исключений, но может есть более подходящий метод?