Перейти к содержанию

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


E.K.

Рекомендуемые сообщения

 

 


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

 

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

  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

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

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

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

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

Трёх раз - 3я.

И т.д.

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

  • Согласен 1
Ссылка на комментарий
Поделиться на другие сайты

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

 

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

 

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

 

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

 

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

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

 

 

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

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

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

Трёх раз - 3я.

 

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

  • Спасибо (+1) 1
Ссылка на комментарий
Поделиться на другие сайты

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

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

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

 

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

Ссылка на комментарий
Поделиться на другие сайты

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

 

Алгоритм:

 

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

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

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

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

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

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

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

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

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

 

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

 

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

 

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

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

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

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

 

 

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

 

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

(1 - (1-1/Nn)D/N) = p

 

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

 

D = N log(1-1/Nn)(1-p)

 

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

 

graph.png

 

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

Изменено пользователем Fireman
Ссылка на комментарий
Поделиться на другие сайты

 

 


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

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

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

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

 

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

 

 

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

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

 

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

Изменено пользователем oit
Ссылка на комментарий
Поделиться на другие сайты

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

 

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

 

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

 

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

 

 

 

 

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

 

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

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

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

Изменено пользователем Fireman
Ссылка на комментарий
Поделиться на другие сайты

 

 


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

 

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

 

 


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

 

конечно, причём если судить по формулам, то очень быстро падает в практически 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)2
  • а итоговая вероятность p соответственно равна p = qN-1(1 - (1-1/N)0.5r)2(N-1)

 

D = (N - 1) log(1-1/N)(1 - p0.5/(N-1))2

 

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

 

graph.png

 

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

Ссылка на комментарий
Поделиться на другие сайты

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
  • Похожий контент

    • E.K.
      От E.K.
      Всем привет!
       
      По ходу жизни мы все иногда сталкиваемся с разными визуальными несуразностями, которые можно сфотографировать - или которые уже существуют в виде фоток. Например, однажды в небольшом магазинчике на Гавайях я обнаружил... водку Камчатка!

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

       
      Или меня постоянно удивляет кофе "Georgia" в японских уличных магазинах и вендинговых автоматах:

       
      Процитирую себя
      "Каждый раз в Японии меня умиляет кофейный бренд "GEORGIA" со снежными вершинами на картинке.
      Никак не могу понять - если это американская Джорджия - то при чём здесь горы? Если же это Грузия - то при чём здесь кофе? Но в Японии эти несовместимые несовместимости вполне себя неплохо чувствуют в повсеместно расставленных вендинговых машинках. Хотя... Если посмотреть по сторонам.. Например, "Спартак" и "Динамо".. ... - какое отношение эти бренды имеют к футболу?"
       
      Кстати, а почему он на картинке в каске? Зачем это кофе надо пить в каске?..

       
      Так вот, картинок таких наверняка не только у меня достаточно - посему эта тема будет как раз посвящена разным фоткам с несуразностями, загадками - и разными прочими подобными тоже. Спасибо Борису за подсказку!
       
       
      Ну, можно начинать.
×
×
  • Создать...