как стать умнее кошки

[green_fr]

Интересная задачка:
Перед вами семь дверей. За одной из них сидит кошка

Comments

[xxxxx]

вот тебе решение, подробности напиши на питоне сам. Раскрасим двери в шахматном порядке и предположим сперва, что кошка в чёрной двери. Зная это её легко поймать, зажав в угол. Но если вдруг она не поймалась, это лишь означает, что изначальное предположение было неверно и она была сперва таки не в чёрной, но в белой двери. Но мы знаем сколько было ходов, значит теперь мы наверняка знаем какого цвета кошка, а зная это --- легко загнать в угол.

[green_fr]

Я примерно это пытался описать в п.4, но заткнулся на том, что ты элегантно обошёл словами "легко поймать". Покажи, как?

[zlyuk]

если знать, в чётной или нечётной двери кошка в данный момент, то её просто поймать, двигаясь с одного края на другой.
например, пусть она в нечётной двери. откроем дверь №1. если там её нет, то она была в 3, 5 или 7. значит, следующим ходом переместится в 2, 4 или 6.
откроем дверь №2. Если её там нет, значит она в 4 или 6. следующим ходом - будет в 3, 5 или 7.
откроем дверь №3. опять нет! значит она в 5 или 7 и будет теперь в 4 или 6. и так до конца.
если в последнем шаге кошку не нашли - значит она была изначально в чётной двери. меняем предположение о чётности нынешней двери и начиаем сначала.
в чётном случае - открываем вначале дверь №2 два раза, и убеждаемся, что кошка в двери с большим номером.
(извините, что влез в чужой тред)

[green_fr]

Точно! Спасибо, теперь ясно.
Переформулирую:
1. Предположим, что кошка за чётной дверью. Ловим её слева направо по указанному методу. В худшем случае это занимает 5 ходов.
2. Если не поймали, значит в первом ходу она была за нечётной дверью. Значит теперь она за чётной. Начинаем сначала - и через ещё 5 ходов ловим кошку.
Отлично :-)

[m_ag_us]

У задачи очень красивое решение.

Надо визуализировать процесс.
Рассадить кошек за каждой дверью. Открыть одну. Если там кошки нет, представить, куда могли переместиться кошки за оставшимися дверьми. Открыть следующую.
И так далее.
Важно решить, с какой двери начать. Постепенно исключаются места, где кошка может быть. И мы открываем ту единственную дверь, за которой может оказаться кошка.

[green_fr]

Ок. Я открыл первую дверь. За ней нет кошки. Но на следующем ходу она может быть где угодно, включая первую дверь (была за второй) и вторую (да, её не было за первой, но она могла быть за третьей). Итого, что мне дал первый ход? Небольшое смещение вероятностей, но нуля нигде нет.

[m_ag_us]

1. Никто не говорил, что первый ход даст окончательный ответ.
2. Никто не говорил, что надо открыть первую дверь.

Вы хотите ответ, или хотите подумать?
Я например сломал мосхх и пошёл искать ответ.
Нашёл. Ответ красивый.

[green_fr]

Я хотел понять ваше предложение :-) Чуть выше я разобрался с решением, в котором мы разбиваем ситуацию на две гипотезы, а потом решаем каждую из них по-отдельности. А у вас какое решение получилось?

[anna_porshneva]

Вот вы математики! Да взять кусок мяса и положить перед дверью - сама придет.

[green_fr]

Было бы у нас другое мясо - нафига бы нам была нужна та кошка?!

[anna_porshneva]

Так тогда тег нужно "Кулинария" или "Как выжить в кризис".

[green_fr]

Да, не подумал. А ведь у меня уже есть таг стратегии эволюции!

[anonymous]

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

[green_fr]

Это был мой п.2. Проблема в потенциальной бесконечности времени, через которое кошка там окажется.

[xxxxx]

Потому что ты скопипастил у копипастера неправильное условие. Правильное условие: кошка ходит не "случайно", а злобно чтоб не попасться. Слово "случайно" типа намекает на вероятностный алгоритм, тогда как требуется совершенно детерминистический алгоритм. (ну ладна "алгоритм" это громко сказано, всё решение состоит из последовательности дверей №№12345671234567 --- ну формально конечно чем не алгоритм :)

[cross_join]

Это я из ФБ.
Если непрерывно, а не в серии попыток, то ОК.

[green_fr]

Да, я понял. Я вот тут пошагово расписал в нотации m_ag_us.