Мне вот тут подумалось, что блоггинга мне не хватает. Причем не очень хочется писать чего-то длинное и сильно умное. Для этого, у меня теперь на английском блог есть. Хочется чего-то простого и легковесного, типа журнала живого. Вроде бы есть всякие Г+ и фейсбуки, но их формат мне все равно не нравится. Если захочешь чего-нить своего потом найти там, заморишься.
Так что я решил восстановить блог, но в формате, о чем пишется, о том и буду писать. В основном о технологиях, о книжках читаемых и мыслях при этом в голову приходящих.
Вот и сейчас просто хочется поделиться загадкой, которую вчера решал:
Есть пять нор, расположенных в ряд. В одной из них сидит лиса. Каждую ночь лиса перебирается в соседнюю норму слева или справа. Каждое утро вы можете проверить одну нору на выбор. Какая должна быть стратегия проверки нор, чтобы в конечном итоге лиса была поймана?
Нельзя такое с утра пораньше!
ОтветитьУдалитьНоры 1-2-3-4-5
Ловим 2-2-3-4-3-3-2-3-4
Почему
Лиса может быть чётной или не чётной. То есть, находиться в чётной или нечётной норе перед первой проверкой. Сначала ловим нечётную лису. (чётная/нечётная - проверяемая нора).
Н-2
Ч-2 (лиса сейчас в 4 норе)
Н-3 (лиса сейчас в 5 норе)
Ч-4 (поймали нечётную лису либо она чётная).
Если лиса была чётная, то сейчас она в нечётной норе вместо чётной.
Н-3 (ага, или в 1 или в 5)
Ч-2 (сидит в четвёртой рыжая редиска)
Н-3 (залезла в пятую)
Ч-4 (готова).
Таким образом мы поймали лису произвольной чётности. ;)
Наверняка есть какая-то умная теорема на этот счёт. Но иногда перебор проще.
Протупил. После того, как выяснили, что лиса чётная, третью нору надо проверить дважды, чтобы выйти на нужный режим.
УдалитьВелком бэк :) Очень не хватало обзора книжек и вообще всяких хороших и свежих мыслей на проф тематику и просто.
ОтветитьУдалитьС точки зрения теории вероятности достаточно проверять одну и ту же нору, ведь в условии сказано "в конечном итоге", т.е. время у нас не ограничено :)
ОтветитьУдалить:) Но ведь и не сказано, что у лисы нет тактики и она не прыгает постоянно влева-вправо на одну нору.
УдалитьДа, я думал об этом. Тут надежда на то, что лиса ведет себя природно непредсказуемо :) А если лиса с тактикой...интересно, сможет ли она придумать как обойти любую тактику охотника? :)
УдалитьЛюбая стратегия упирается в стратегию лисы. Поэтому оптимальнее всего проверять какую-то одну нору. Правда и на это лиса имеет контрстратегию. Она просто скачет по двум соседним норам. Какую вы стратегию придумали?
Удалить@Андрей, Igor: тут в комментариях уже есть ответы.
УдалитьЯ думал так:
1. Проверяю вторую слева нору (после этого есть гарантия, что лисы нет в первой и второй норках. В результате остается лишь 3 норы, в которых может находиться лиса.
2. Три возможные положения лисы дают 6 теоретических ходов, но это число на практике меньше, поскольку из самой правой норы лиса не может нырнуть вправо. Теперь можно разрисовать возможные "ходы" лисы и "ходы" охотника и прийти к решению, которое "поймает" лису не зависимо от "ходов" лисы.
Этот комментарий был удален автором.
ОтветитьУдалить2-3-4-4-3-2 или 4-3-2-2-3-4
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалить4,3,2,2,3,4
ОтветитьУдалитьИдея - определять в каких норах лисы точно нет и стремиться увеличить количество таких нор. Например, когда лиса находится в 1,3,5, то на следующее утро она может быть только в 2,4.
Ага. Я решал именно так. Потом нарисовал дерево возможных решений, что и дало конечный результат.
УдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьС моделировал задачу. По моим наблюдениям
ОтветитьУдалить2,2,4,4,2,4 сопоставимо с 2-3-4-4-3-2.
4,3,2,2,3,4 им уступает.
2-2-4-4-2-2-4-4-2 также заметно эффективнее 2-2-3-4-3-3-2-3-4
Этот комментарий был удален автором.
Удалить2-2-3-4-4-3-2. Аналогичный "инверсный" вариант:4-4-4-3-2-2-3-4.
ОтветитьУдалитьP.S. "инверсный" вариант: 4-4-3-2-2-3-4. Жаль исправить нельзя:(
ОтветитьУдалить1-1-2-3-4-5
ОтветитьУдалитьЕсть короче
ОтветитьУдалить2-2-3-4-5
224432. Спасибо за загадку, статьи и книгу.
ОтветитьУдалить