2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: задача на формулу включений-исключений ?
Сообщение15.10.2019, 07:38 


01/07/19
244
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$

 Профиль  
                  
 
 Re: задача на формулу включений-исключений ?
Сообщение15.10.2019, 12:55 


01/07/19
244
Yury_rsn в сообщении #1420764 писал(а):
запрограммировал в таблице эту задачку.
https://docs.google.com/spreadsheets/d/ ... edit#gid=0

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


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

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

Например, в периоде длины 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, а то и больше)

 Профиль  
                  
 
 Re: Posted automatically
Сообщение15.10.2019, 18:23 


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

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

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

 Профиль  
                  
 
 Re: задача на формулу включений-исключений ?
Сообщение15.10.2019, 19:53 
Заслуженный участник


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

 Профиль  
                  
 
 Re: задача на формулу включений-исключений ?
Сообщение15.10.2019, 22:24 


01/07/19
244
Pphantom в сообщении #1420960 писал(а):
что сложного вы нашли в задаче, решаемой за 5-10 минут максимум. В исходной формулировке она тривиальна, а какой-то внятной общей формулировки ..

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

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

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

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

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

 Профиль  
                  
 
 Re: задача на формулу включений-исключений ?
Сообщение16.10.2019, 15:23 


01/07/19
244
Pphantom в сообщении #1420586 писал(а):
Может быть, тогда стоит начать с более простой задачи: чему равен период идеально точного повторения расписания (в рамках исходных условий задачи)?

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

mihaild в сообщении #1402602 писал(а):
Yury_rsn в сообщении #1402598 писал(а):
А разве из метода построения решета Эратосфена нельзя увидеть бесконечность простых чисел?
А как? Вдруг после очередного простого все числа окажутся вычеркнуты?



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

 Профиль  
                  
 
 Re: задача на формулу включений-исключений ?
Сообщение17.10.2019, 10:34 


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

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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение17.10.2019, 12:02 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group