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

[E.K.]

Задачки про подземелья фанклуба и лампочку =>

 

1. Однажды злым админам фанклуба стало скучно, они забанили 4х (четырёх) фанлубней и заперли их в подземелье фанклуба в четырёх разных камерах без мобил и интернетов. А дальше они начали развлекаться: каждый день одного случайного фанклубня сажают на день в карцер на сутки, в карцере есть выключатель и лампочка, которую можно включить или выключить. Как только фанклубень понимает, что все остальные фанклубни хотя бы по разу побывали в карцере – он идёт к самому главному и злому админу и говорит об этом. Если угадал – всех выпускают и разбанивают, нет – пожизненный эцих без гвоздей.

 

Пока фанклубней тащили в подземелья фанклубья они успели договориться о стратегии и победили злых админов. Как они это сделали?

 

У этой задачки есть принципиально разные решения. Какие?

 

Но эта задачка простая.. Усложняю:

 

2. Сколько в среднем уйдёт времени у 10 фанклубней, чтобы вернуться в онлайн?

А у 100 фанклубней?

 

Удачи в размышлениях!
 

[E.K.]

А прикольная задачка!

Я пока ещё не знаю ответа, но примерно понимаю в какую сторону "копать".

[oit]

Тот, кто первый раз побывал в карцере, всегда оставляет свет включенным.

Если побывал второй раз - выключает свет.

Осталось посчитать минимальное количество дней

 

в первый день - свет включен

во второй - тоже включен, т.к. понятно что двое знают, что двое были.

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

 

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

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

[E.K.]

1. Это решение какой задачки? Первой?

2. А как оптимальнее работать при количестве фанклубней больше 10?

[oit]

 

 

Это решение какой задачки? Первой?

пока да

[E.K.]

Это решение какой задачки? Первой?

пока да

Давайте пройдёмся по всем логическим цепочкам. У нас 4 забаненных фанклубня: 1 "наблюдатель" и 3 "исполнителя". Они все знают стратегию. Давайте начнём с того, что в 1й день в админ-карцере оказался клубень-наблюдатель. А на следующий день один из "исполнителей". Что они должны сделать?

[Friend]

Все просто же: каждый кто побывал в карцере оставляет там какую-нибудь свою особенную вещь или пишет что-то на стене, например, здесь была Мария

[E.K.]

Все просто же: каждый кто побывал в карцере оставляет там какую-нибудь свою особенную вещь или пишет что-то на стене, например, здесь была Мария

Потом эту надпись видит злой админ, добавляет "здесь был Хуан, Ромео и Джульетта" - и тем вводит первого клубня в заблуждение. Тот радостно бежит с докладом к админу - и все торжественно получают пожизненный эцих. Хреновая стратегия..

[Fireman]

 

 

Все просто же: каждый кто побывал в карцере оставляет там какую-нибудь свою особенную вещь или пишет что-то на стене, например, здесь была Мария

 

Это как в задаче про 3 лампочки и 3 выключателя:

 

в одной комнате на столе установлены 3 лампочки (которые изначально не горят)

а в другой, изолированной от первой, комнате есть 3 выключателя (которые изначально выключены)

 

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

 

Задача: как определить какую выключателю соответствует какая лампочка за одно посещение комнаты с лампочками

 

Там тоже хочется "считить" и приходится читить

Но в отличии от этой задачи, злой админ такого не позволяет - заводят голыми, предварительно просканировав, стены с антивандальным нанопокрытием и под напряжением

[E.K.]

Это как в задаче про 3 лампочки и 3 выключателя:

в одной комнате на столе установлены 3 лампочки (которые изначально не горят)

а в другой, изолированной от первой, комнате есть 3 выключателя (которые изначально выключены)

Что интересно, эта задачка имела решение в прошлом веке. В наше время она уже далеко не всегда решаема.. Мне нужно объяснять почему?

[Xenon]

Светодиодные потому что лампочки сейчас

[E.K.]

Так точно! Не каждая лампочка в 21м веке нагревается от выключателя

 

Но давайте не саботировать предыдущую задачку. Или вам забаненных фанклубней в подземелье без вайфая не жалко??

[oit]

Придумал:

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

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

[E.K.]

В правильную сторону думаете! Ну, давайте уже.. Это же просто! Решение уже само напрашивается..

(сложнее придумать более оптимальные алгоритмы.. но наверняка тоже можно).

[E.K.]

Что-то опять нет движений в массах.. Ну, хорошо. Давайте посмотрим на задачку внимательнее и решим её для тривиальных случаев.

 

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

 

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

 

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

 

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

 

Первый день сидит клубень-1, второй день сидит клубень-2. С какой вероятностью клубень-3 окажется там в третий день? 1/2 - вот с такой, поскольку выбор будет случайный между клубнем-1 и клубнем-3. Может ли оказаться, что на четвёртый день клубень-3 опять не попадёт в карцер? Да, опять с вероятностью 1/2. Но чтобы этого не случилось и на третий, и на четвёртый день = вероятность этого равна 1/2 * 1/2 = 1/4. И так каждый день после третьего (включая третий) вероятность не-выхода на свободу и пива уменьшается в два раза. Когда вероятность станет меньше 1%? Когда степень двойки окажется больше ста! Ведь 100% мы делим на степени двойки. То есть, 128=2^7. То есть, 2 дня + 7 дней, то есть через 9 дней утром с вероятностью 99% они пойдут пить пиво.

 

И на лампочку с выключателем даже не посмотрели!

 

4. Забанены четыре клубня (как в условии задачки). Вот тут потребуется какая-то передача информации. А ничего кроме выключателя и лампочки нет. Что делать? (и вероятность тоже надо подсчитать).