вторник, 3 июля 2018 г.

Welcome, так сказать, back:)

Мне вот тут подумалось, что блоггинга мне не хватает. Причем не очень хочется писать чего-то длинное и сильно умное. Для этого, у меня теперь на английском блог есть. Хочется чего-то простого и легковесного, типа журнала живого. Вроде бы есть всякие Г+ и фейсбуки, но их формат мне все равно не нравится. Если захочешь чего-нить своего потом найти там, заморишься.

Так что я решил восстановить блог, но в формате, о чем пишется, о том и буду писать. В основном о технологиях, о книжках читаемых и мыслях при этом в голову приходящих.

Вот и сейчас просто хочется поделиться загадкой, которую вчера решал:

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

18 комментариев:

  1. Нельзя такое с утра пораньше!
    Норы 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 (готова).
    Таким образом мы поймали лису произвольной чётности. ;)
    Наверняка есть какая-то умная теорема на этот счёт. Но иногда перебор проще.

    ОтветитьУдалить
    Ответы
    1. Протупил. После того, как выяснили, что лиса чётная, третью нору надо проверить дважды, чтобы выйти на нужный режим.

      Удалить
  2. Велком бэк :) Очень не хватало обзора книжек и вообще всяких хороших и свежих мыслей на проф тематику и просто.

    ОтветитьУдалить
  3. С точки зрения теории вероятности достаточно проверять одну и ту же нору, ведь в условии сказано "в конечном итоге", т.е. время у нас не ограничено :)

    ОтветитьУдалить
    Ответы
    1. :) Но ведь и не сказано, что у лисы нет тактики и она не прыгает постоянно влева-вправо на одну нору.

      Удалить
    2. Да, я думал об этом. Тут надежда на то, что лиса ведет себя природно непредсказуемо :) А если лиса с тактикой...интересно, сможет ли она придумать как обойти любую тактику охотника? :)

      Удалить
    3. Любая стратегия упирается в стратегию лисы. Поэтому оптимальнее всего проверять какую-то одну нору. Правда и на это лиса имеет контрстратегию. Она просто скачет по двум соседним норам. Какую вы стратегию придумали?

      Удалить
    4. @Андрей, Igor: тут в комментариях уже есть ответы.

      Я думал так:
      1. Проверяю вторую слева нору (после этого есть гарантия, что лисы нет в первой и второй норках. В результате остается лишь 3 норы, в которых может находиться лиса.
      2. Три возможные положения лисы дают 6 теоретических ходов, но это число на практике меньше, поскольку из самой правой норы лиса не может нырнуть вправо. Теперь можно разрисовать возможные "ходы" лисы и "ходы" охотника и прийти к решению, которое "поймает" лису не зависимо от "ходов" лисы.

      Удалить
  4. Этот комментарий был удален автором.

    ОтветитьУдалить
  5. Этот комментарий был удален автором.

    ОтветитьУдалить
  6. 4,3,2,2,3,4
    Идея - определять в каких норах лисы точно нет и стремиться увеличить количество таких нор. Например, когда лиса находится в 1,3,5, то на следующее утро она может быть только в 2,4.

    ОтветитьУдалить
    Ответы
    1. Ага. Я решал именно так. Потом нарисовал дерево возможных решений, что и дало конечный результат.

      Удалить
  7. Этот комментарий был удален автором.

    ОтветитьУдалить
  8. С моделировал задачу. По моим наблюдениям
    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

    ОтветитьУдалить
    Ответы
    1. Этот комментарий был удален автором.

      Удалить
  9. 2-2-3-4-4-3-2. Аналогичный "инверсный" вариант:4-4-4-3-2-2-3-4.

    ОтветитьУдалить
  10. P.S. "инверсный" вариант: 4-4-3-2-2-3-4. Жаль исправить нельзя:(

    ОтветитьУдалить