Як вирішується завдання про кота Леопольда, миші і п’яти нірках

Кот Леопольд дуже голодний. Він хоче зловити і з'їсти миша за всяку ціну, але бажано швидше.

Миша сховалася за стіною, вона знаходиться в системі з п'яти норок, розташованих поруч один з одним, на одній прямій лінії. Кожна пара сусідніх норок (1-я і 2-я; 2-а і 3-я, 3-я і 4-я; 4-я і 5-я) з'єднані між собою ходом. Очевидно, ходи заховані десь в товщі стіни.

Кот Леопольд не знає, де саме знаходиться миша, так як він її не бачить. Але він знає, що перед кожною його спробою вона неодмінно знаходиться десь в одній з цих п'яти норок. При кожній своїй спробі кіт може засунути лапу в одну з норок (але тільки в якусь одну) і перевірити цю нірку на наявність миші. Якщо спроба виявилася вдалою, то миша спіймана. Якщо ж спроба виявилася невдалою і миші в досліджуваній нірці не виявилося, то миша до початку наступної спроби кота обов'язково переходить в сусідню нірку (така умова завдання). Наприклад, з норки № 3 в разі невдачі кота мишка може перебігти або в нірку № 2, або в нірку № 4. З норки № 1 - тільки в № 2; з № 5 - тільки в № 4.

Кількість спроб у Леопольда не обмежена, але він бажає зловити мишу по можливості за найменшу кількість спроб.

Питання: чи може за таких умов Леопольд взагалі зловити мишку і якщо так, то скільки спроб йому знадобиться і яким буде алгоритм упіймання миші?

Очевидно, необхідно спочатку прийняти рішення в якій норі може бути миша, а потім варіант черговості перевірки. З причини того, що миша після кожної спроби кота переходить в сусідню нору, вона послідовно чергує непарні нори з парними. Припустимо, вона знаходиться в непарній норі.

• Перевіряємо 3 нору, якщо її там немає, значить в 1 або 5 і перейде в 2 або 4.
• Наступна спроба нора 2, знову порожньо, значить в 4 норі, і далі сховається в 3 або 5.
• Тепер коту необхідно випробувати 3 нору, що б виключити можливість миші перебратися на іншу сторону норок, а миші сховатися 5 норі.
• Наступний хід - обстеження 4 нори, в якій повинна опинитися миша при правильному початковому нашому припущенні. В іншому випадку, миша сховалася на початку гри в парному норі, а в даний момент знаходиться в непарній.
• Перевіряємо повторно 4 нору, так вона повинна вже бути в одній з парних норах.
• Якщо її немає, значить, вона була в норі під номером 2. Тоді коту залишається засунути лапу в 3 нору і якщо спроба виявиться невдалою, миші згідно з правилами доведеться з першої нори перебратися в нору під номером 2, де і спіткає її сумна доля.