Найдите кота

[Dmitry Tkachenko]

Перед нами расположены $n\geqslant 2$ закрытых коробок, в одной из которых спрятался кот. Мы можем открыть одну из коробок и проверить наличие кота. Если его там не оказалось, то после закрытия этой коробки кот обязательно незаметно перебирается в одну из соседних (относительно той, в которой он был) коробок. Доказать, что мы сможем обнаружить кота за $2n-4$ открывания, но не меньше.

[amon]

Dmitry Tkachenko в сообщении #1072697 писал(а):

обнаружить кота за $2n-4$ открывания

Т.е. при $n=2$ мы сразу знаем, в которой из двух коробок кот?

[Dmitry Tkachenko]

amon, $n>2,$ конечно. Уже не могу поправить.

[ET]

Способ обнаружения:
Если $n$ нечетное. то проверяем ящики
$2$,$3$,$4$,...,$n-1$,$2$,$3$,....$n-1$
Если $n$ четное, то
$2$,$3$,$4$....$n-1$,$n-1$,$n-2$,...$3$,$2$

strike - в обоих случаях возможно по 2му пути (для четного)

[worm2]

ET в сообщении #1072908 писал(а):

Если $n$ четное, то
$2$,$3$,$4$....$n-1$,$n-1$,$n-2$,...$3$,$2$

Этот способ для нечётных $n$ тоже годится .

-- Пт ноя 13, 2015 11:57:10 --

Доказательство, что меньшим числом обойтись нельзя.
Пусть какая-то внутренняя ($2, 3, \dots, n-1$) коробка проверена не более одного раза. Тогда кот будет прятаться в этой коробке сразу до и сразу после проверки (если ни разу не проверена, то на первом шаге, например), а также на всех остальных шагах, совпадающих по чётности с шагом проверки. На шагах, не совпадающих по чётности, кот выбирает одну из соседних коробок, в которой на данном шаге нет проверки (очевидно, можно считать, что порядок проверки известен коту наперёд).

[Ktina]

Отдалённо напоминает вот эту задачу: http://www.problems.ru/view_problem_det ... p?id=32062