Математическое и загадочное

[Fireman]

 

 

  E.K. сказал:

Первый день сидит клубень-1, второй день сидит клубень-2. С какой вероятностью клубень-3 окажется там в третий день? 1/2 - вот с такой, поскольку выбор будет случайный между клубнем-1 и клубнем-3.

 

Но ведь никто не запрещает несколько раз одного и того же сажать.

[oit]

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

Необходимы исключения:

Клубни не могут вызываться более одного раза - 1я задача

Не более двух раз 2я задача

Трёх раз - 3я.

И т.д.

Тогда счётчик дней можно использовать

[E.K.]

  В 22.04.2019 в 07:15, Fireman сказал:

Но ведь никто не запрещает несколько раз одного и того же сажать.

 

Я недавно уже рассуждал на эту тему ->

 

  В 20.04.2019 в 19:36, E.K. сказал:

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

 

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

 

2 клубня. Второй знает, что он ни разу не был в карцере. И как только там оказывается - они на свободе.

3 клубня. А вот тут без лампочки не обойтись..

 

 

  В 22.04.2019 в 07:27, oit сказал:

Необходимы исключения:

Клубни не могут вызываться более одного раза - 1я задача

Не более двух раз 2я задача

Трёх раз - 3я.

 

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

[E.K.]

  В 22.04.2019 в 07:50, E.K. сказал:

  В 20.04.2019 в 19:36, E.K. сказал:

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

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

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

 

Итак, какова стратегия клубней, если их три или больше?

[E.K.]

Увы, "жаль подмога не пришла, подкрепленье не прислали, что ж обычные дела..." (с) ... да ладно, я шучу. Но, очень жаль, что решение задачки пришло не из фанклуба. А несчастных фанклубней, томящихся в казематах злобных админов, - опять спасать мне..

 

Алгоритм:

 

1) Забаненный фанклубень, который первым попадает в карцер (далее "первый фанклубень" = ПФК), в первый день своего заточения включает лампочку. И всё.

2) При последующих заточениях в карцере ПФК смотрит на лампочку:

- если она горит, то он ничего не делает вообще. Сидит и ждёт.

- если лампочка НЕ горит, то он делает "memory++" и включает лампочку.

3) Все остальные клубни знают, что они пропустили первый день; что не они считают задачку. У них другой алгоритм:

- каждый не-ПФК должен ОБЯЗАТЕЛЬНО выключить лампочку, но только ОДИН раз за всё время отсидки. То есть,

- если лампочка горит и он УЖЕ выключал её хоть раз, то он сидит и ничего не трогает.

- если лампочка горит, но он НЕ ВЫКЛЮЧАЛ её ни разу, то он её выключает. И больше не трогает никогда.

4) ПФК, каждый раз снова попадая в карцер, видит был ли новый фанклубень за время его отсутствия или же нет.

 

Так вот, вторая задачка: рассчитать примерное количество дней, когда они - ура!! - и пошли пить пиво.

 

Хе-хе, чмоки!

// но вижу, что задачка не понравилась...

[oit]

Мне понравилась

Я не подумал на счёт того, чтобы ПФК всех пересчитывал - интересное решение, Спасибо.

[Fireman]

Есть ещё самый быстрый (!!!!) в максимуме, но и наверное самый медленный в среднем способ вытащить клубней

 

Для удобства покажу это на 7 клубнях.

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

• если клубень-понедельник приходит в понедельник (т.е. в свой день), то он включает свет
• если любой из клубней приходит не в свой день - он выключает свет (если свет горит)
• если клубень-воскресенье приходит в свой день и видит, что свет горит - всё, значит все клубни побывали в помещении

Такой алгоритм даёт самый быстрый способ определить, что все клубни побывали в помещении - всего 7 дней и быстрее быть уже не может, но... это очень редкий случай.

 

 

Теперь давайте подсчитаем какая вероятность побывать всем клубням в помещении за определённое кол-во дней:

 

• пусть кол-во клубней - N
• вероятность того, что каждый клубень попадёт на свой день равна 1/Nⁿ (всего возможно Nⁿ комбинаций перемешивания N клубней в течении N дней, при этом один клубень может в течении N дней по нескольку раз бывать в помещении слез и печали ) 
• вероятность того, что ситуации, когда каждый клубень попадёт на свой день соответственно (1 - 1/Nⁿ)
• пусть всего было k циклов по N дней
• вероятность того, что за все k циклов клубни так и не побывали каждый в своем дне в течении одного цикла будет (1-1/Nⁿ)^k
• вероятность того, что за k циклов клубни таки побывают каждый в своем дне в течении одного цикла соответственно будет (1 - (1-1/Nⁿ)^k)
• пусть всего над клубнями издевались D дней, т.е. k = D/N циклов
• вероятность p выйти за D дней тогда будет

(1 - (1-1/Nⁿ)^D/N) = p

 

т.е. кол-во дней D за которые вероятность выйти N клубням на свободу составит p равна

 

D = N log_(1-1/Nⁿ)(1-p)

 

вот так это выглядит на графике

 

 

т.е. 4 бедных клубней при такой системе выйдет с вероятностью 50% только через 708 дней   , а 7 "недельных" клубней очутятся на свободе всего через 10952 года

Изменено 23 апреля, 2019 пользователем Fireman

[oit]

 

 

  Fireman сказал:

если клубень-воскресенье приходит в свой день и видит, что свет горит - всё, значит все клубни побывали в помещении

тоже интересное решение, но частное. По логике немного совпадает с логикой Е.К.

@Fireman, для клубней больше 7ми не годится, т.к. лампочка может уже остаться включенной на 7м, но при этом 8й и дальше могут и не побывать

[E.K.]

  В 23.04.2019 в 07:28, Fireman сказал:

Для удобства покажу это на 7 клубнях.

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

• если клубень-понедельник приходит в понедельник (т.е. в свой день), то он включает свет
• если любой из клубней приходит не в свой день - он выключает свет (если свет горит)
• если клубень-воскресенье приходит в свой день и видит, что свет горит - всё, значит все клубни побывали в помещении

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

 

Что-то не так в алгоритме.

 

 

  В 23.04.2019 в 07:28, Fireman сказал:

Теперь давайте подсчитаем какая вероятность побывать всем клубням в помещении за определённое кол-во дней:

2. А давайте подсчитаем вероятность 50% выхода для моего "линейного" решения.

• пусть кол-во клубней - N
• вероятность попадания клубня в карцер равна 1/N

... ой, мне пора по делам бежать. Считайте без меня пока!

[oit]

  E.K. сказал:

в субботу в карцер попадает клубень-суббота, включает свет

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

 

А вот если все в фан-клубе пересчитаются и у каждого будет свой индивидуальный порядковый номер - тут может и можно что-то придумать

Изменено 23 апреля, 2019 пользователем oit

[Fireman]

  E.K. сказал:

Что-то не так в алгоритме.

 

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

 

например, если у нас есть 365 клубней, то мы ждём ситуацию, когда каждый клубень будет выбран в свой день, если это не произошло и клубень выключил свет, все - свет сможет включить только первый клубень 1 января (если на него падёт жребий)

 

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

 

 

 

 

  oit сказал:

Тоже интересное решение, но частное.

 

не совсем частное - 

в первом случае первый клубень выступает в роли счётчика (есть даже термин для такой ситуации - "битовый счётчик")

во втором - счётчика как такового нет, последний клубень просто устанавливает факт, что начальное состояние системы так и не было изменено (т.е. система развивалась в установленном направлении.

Изменено 23 апреля, 2019 пользователем Fireman

[oit]

@Fireman, вы же по дням недели раскладывали клубней ...

[Fireman]

 

 

  oit сказал:

Тоже интересное решение, но частное.

 

не совсем частное -

в первом случае первый клубень выступает в роли счётчика (есть даже термин для такой ситуации - "битовый счётчик")

во втором - счётчика как такового нет, последний клубень просто устанавливает факт, что начальное состояние системы так и не было изменено (т.е. система развивалась в установленном направлении.

[oit]

Вероятность конечно же есть, но чем больше клубней, тем ниже вероятность

[Fireman]

 

 

  oit сказал:

Вероятность конечно же есть, но чем больше клубней, тем ниже вероятность

 

конечно, причём если судить по формулам, то очень быстро падает в практически 0.

 

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

Для первого метода с вероятностью p выйти за D дней получается следующее (если я не ошибся):

 

• весь процесс с выходом клубней на свободу можно разбить на (N - 1) циклов, в каждом цикле один из клубней выбирается впервые, в клубень #1 подсчитывает его
• таким образом на каждый цикл затрачивается r = D / (N - 1) дней
• каждый цикл можно разбить на 2 этапа - на первом этапе (скажем в течении x дней ожидаем выбора очередного клубня #i, а в течении следующих (r - x) дней ожидаем выбора клубня #1, чтобы он подсчитал клубня #i
• вероятность выбора любого клубня в любой день 1/N
• вероятность не выбрать клубня в любой день (1 - 1/N)
• вероятность не выбрать клубня в течении x дней (1-1/N)^x
• вероятность выбрать клубня в течении x дней (1 - (1-1/N)^x)
• вероятность выбрать клубня #i в течении х дней и клубня #1 в течении (r - x) дней соответственно  q = (1 - (1-1/N)^x)*(1 - (1-1/N)^r-x)
• максимальная вероятность этого события при x = r/2 и равна q = (1 - (1-1/N)^0.5r)²
• а итоговая вероятность p соответственно равна p = q^N-1= (1 - (1-1/N)^0.5r)^2(N-1)

 

D = (N - 1) log_(1-1/N)(1 - p^0.5/(N-1))²

 

тут вероятность получается гораздо приятнее

 

 

Т.е. с вероятностью 50% 100 клубней обретут свободу всего за 300 лет