Перед Вами расположены 100 закрытых коробок в ряд, в одной из которых спрятался пятничный кот. Вы можете открыть одну из коробок и проверить наличие пятничного кота. Если его там не оказалось, то после закрытия этой коробки пятничный кот обязательно незаметно перебирается в одну из соседних (относительно той, в которой он был) коробок.

Можно ли вообще однозначно определить в какой коробке пятничный кот за конечное число ходов-открытий коробок?
Если да, то сколько требуется действий?

(59) Что такое прямой и обратный проход?

(59) Допустим открываем первую коробку, а кот вот второй коробке, закрываем первую, кот прыгает в третью, открываем вторую  и т.д., пока не дойдем до 99, допустим кот к этому моменту сидит в сотой, когда ты закроешь 99 он перепрыгнет из сотой в 99-ю и ты его все равно не поймаешь.

(63) это из (53)

(64) мы 99-ю же дважды открываем

(66) Так он мог и раньше в обратном направлении побежать, в условиях же он не ограничен в смене направления

(25) С хрена ли? А кот был в 4, 3, 2, 1. Поймал?

При постановке задачи в (0) задача нерешаема.

Засада в том, что кот перемещается при закрытии коробки. То есть его можно поймать только случайно.

решения нет) кот очень хитр

Вообще 197 открытий/закрытий? Поскольку, когда откроем 99 и его там не окажется, то он после закрытия 99 коробки переберется в нее. Следовательно открывать ее не надо, мы и так знаем что он там.

Мне кажется нельзя его поймать впринципе. Например мы решили открыть 2 (или любую, кроме 1 или 100 коробки) коробку два (или бесконечное число) раза. И на самый последний раз, когда закрываем коробку, он может быть в соседней и переместиться в нашу закрытую коробку. Далее мы опять открываем ее кучу раз, и после последнего закрытия, кот опять же может быть в соседней и переместится в нашу закрытую. То есть кот всегда может быть на шаг позади. Чистый рандом.

Единственный вариант когда можно кота поймать, это все время открывать 2 или 99 коробку, и угадать когда он переместится в нашу, и выбрать 3 (98), чтобы кот перебрался в 1 (100), и тогда открывать 2 (99). Но опять же рандом.

Вобщем словить кота при данном условии нереально!

за 200 ходов разве нет ? :)

(71) Да, кошки они такие их только ответной хитростью можно взять :)

(0) если кот может перелезть в ту коробку, которую ты только что открывал, то задача не имеет решения при числе коробок более 2х

(76) 2 раза подряд открой коробку номер 1, после этого открой коробку два и ты можешь быть твердо уверен что кот не в 1 в этот момент.

(77) кот может перелезть в коробку после того, как ты ее закроешь во второй раз

(53) Решение найдено ведь уже.

(76) Она не имеет 100% решения даже при числе коробок равном 2.
Это как гарантированно выкинуть решку за конечное число ходов.

(68) Да поймал на 5м ходу. И что это за тон?

(80) с учетом того, что кот ОБЯЗАН переместиться после закрытия коробки, то при двух коробках он гарантированно найдется после второго открытия одной и той же коробки. А вот в трех его можно уже и не найти

(82) А ну да, обязательно же перемещается.

(82) и при трех найдется за 2 хода.

(82) при трех достаточно вторую коробку открыть два раза.

Решение. Всего 198 открытий-ходов.
Перенумеруем подряд коробки от 1 до 100.
Открываем в 2 акта.
Акт 1: открываем с 1 по 99 коробки подряд
Акт 2: открываем с 99 по 1 коробки подряд

Акт 1. Если кот не собирается пересекать "фронт открываемых коробок", то мы его загоняем в 100-ю и так как 99-ю открываем дважды, он будет пойман.
Если кот пересекает "фронт открываемых коробок", то значит когда мы открывали N-ю он сидел в (N+1)-й и переползает в N-ю. Итак, значит когда мы открываем четную коробку, кот сидит в нечетной и наоборот.

Акт 2. На начало акта кот сидел в нечетной коробке. Мы снова открываем 99-ю и кот из нечетной переползает в четную. Теперь открывая четную кот сидит в четной, то есть четности совпадают. И снова пересечь "фронт открываемых коробок" кот не сможет.

(84) только случайно. Но случайно он может и за один ход найтись при любом количестве коробок.

(86) где в условии сказано, что код обязательно только в одну сторону идет? Из чего следует, что он не может 99 раз переходить из 1й коробки во 2ю и обратно?

Тогда и при 4 поймаем.
2 раза открываем 2ю. Если не поймали, то кот либо в 3, либо в 4. 2 раза открываем 3ю - пойман.

+(86) фактически это решение дано RomanYS в (53) я просто причесал немного

(89) >2 раза открываем 2ю. Если не поймали, то кот либо в 3
да, но только он там искючительно, пока коробка 2 открыта. После закрытия он уже может быть и в3, и в 4, и в 2, и в 1

(86) как-то неочевидно, что за меньшее количество ходов нельзя

(88) не обязательно в одну сторону, может и так, но ты обрати внимание на инвариант четности в решении

(92) согласен, минимум не доказан

(93) тогда это решение уже на 3х коробках не работает

(95) По ходу оно не работает на нечетном числе коробок, но работает на четном

(95) работает, открываем 1,2,2,1

(97) 1,2,2 уже сработает

(97) А на 4х?

100

(99) 1,2,3,3,2,1 надеюсь ты общий алгоритм уже понял?

кстати есть мнение что при обратном проходе нет необходимости идти до первой коробки.

решать нужно на 4 коробках
решение основывается на крайних коробках, после нахождения в которых кот обязан переползти в предпоследнюю
решаем на 4х:
открываем --- где может быть
3 - 124
3 - 123
2 - 13
2 - 24
3 - 3 - кот пойман в любом случае

далее распространить эту методику на 100 (мне щас некада дальше думать)

его там не может быть из за четности.

(86) Раз во втором акте четность стала совпадать,  значит он попадется на второй коробке, а не на первой, значит ходов будет 197(до первой коробки не доберемся)

(102) кстати из четности да, уменьшаем до 197

(101) Есть мнение, что первую коробку нет необходимости открывать при первом проходе, экономим один ход.

При 4 тоже работает. Хмм...

(107) опять да, таки 196! спасибо

Как видим метод монте-карло будет эффективнее )

Хоть и не гарантирует результата.

(0) ОТВЕТ 13.... и не говорите, что я не прав... сегодня ПЯТНИЦА???  ... 13 ???

Меньше 196 нельзя. Если меньше, то одну из "некрайних" коробок мы проверяли не более 1 раза. Допусти кот знает о последовательности открытия всё.

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

2. Есть коробка проверенная 1 раз. По четности кот определяет где ему изначально сесть: в этой коробке или слева/справа, чтобы на нужном ходу открытия не быть в открытой ЭТОЙ коробке. А в остальном действует как в пункте 1.

Буду наступать на коробки ))

(81) Это случайность, попробуй на 6 ячейках, по-твоему алгоритму не поймаешь.

(53) Упс, да, работает :)) Прикольный алгоритм :))

Задача для 3 класса. Мегопроги не могут сообразить даже когда им дали решение) КВН:)

(117) ну задним число у нас все умные )))

Открываем первую коробку, кот либо там, либо на следующем шаге он будет в соседней. Соседняя коробка для первой одна, т.к. коробки расположены в ряд, значит он будет во второй. Все, задача решена.
Максимум потребуется 2 действия.

(117) Для третьего класса? Ню ню.

(119) Возьми с полки пирожок :))

Нужно использовать то, что кот обязан менять четность.

Допустим что мы знаем что кот сейчас в четной коробке.
Тогда открываем каждую нечетную по 2 раза.
11335577 и т.д. до конца - кот проскочить нам заспину не может и будет пойман (если верно наше допущение).

Если дошли до конца и не нашли, то теперь мы точно знаем что вначале он был в нечетной, аналогичным образом двигаемся назад. Максимум 199-200 открываний.

(122) 196 насчитали уже

(122)
1(3>2)
1(2>1)
3(1>2)
3(2>3)
5(3>4)
5(4>5)
..
99(97>98)
99(98>99)
что дальше?

и хрен ты его поймаешь при такой тактике.

(0) Вопрос по Задорнову- как кот может НЕЗАМЕТНО перемещаться по ЗАКРЫТЫМИ коробками?

(126) У тебя кот есть?

(126) он же пятничный кот

(124)
Дальше мы получаем важное знание, что сейчас кот сидит в нечетной коробке.
Таким образом, при каждом открывании мы знаем 50 коробок где кота быть не может. И т.к. он не может перепрыгнуть через коробку или отстаться в той же, Котэ не уйти, он будет обязательно пойман и кастрирован

(129) В приведенном примере - как ты дальше его поймаешь?

А так разве его не поймаем первая коробка 2 раза и на предпоследней однозначно его поймаем. Т.е. 100

(131) нет
1(3>2)
1(2>1)
3(1>2)
3(2>3)
5(3>4)
5(4>5)
..
99(97>98)
99(98>99)
И он в 99 а не в 100 ) а мог быть в любой нечетной.

(130)
Ну как дальше, зная что он в нечетной коробке, открываем 99 и если его там нет, то его нет и в соседних 98 и 100.
Дальше, зная что он в четной коробке, открываем 98 и, если его там нет, то 97-100 пустые.
Дальше, зная что он в нечетной коробке, открываем 97 и, если его там нет, то 96-100 пустые.
И т.д.

котэ нагнул 1с-ников

(134) пускай котэ расскажет как налог на имущество считается, посмотрим кто кого нагнул

(135) Принес ты курицу домой, отдал 13% котэ.

(136) 13% это подоходный...

(137) котэ пофигу какой, главное что съедобный

(135) котэ имущества не надобно, он радикально эту проблему порешал

>кот перебирается в одну из соседних (относительно той, в которой он был)
Открывать всегда 25-ю коробку, с вероятностью 50% он там должен появиться.

Какой-то неправильный кот.

Если кот перемещается между двумя коробками и при приближении границы фронта через коробку, то начинает двигаться в сторону фронта. При таком поведении кота задача не решаема, т.к. КОТ "ХИТРЫЙ". (кот постоянно перемещается межу 9-10, вы открыли 7 и он начинает двигаться в сторону 7, когда вы откроете 7 второй раз он на 8 и следующим шагом сядет 7, а вы откроете 8... В условии не сказано точное поведение КОТА, значит он может быть "ХИТРЫМ"

Я нашел - как правильно вставить картинку?

http://wallpaperscraft.ru/image/89435/3840x2400.jpg

(113)может 195?

(144) нет, минимум 196

На примере 6 коробок.
2,2,3,4,5,5,4 - не закрывая 4 коробку, если котэ не найден то он во 2.

макс число 12 ходов, текущее решение 7 - сэкономили 5 ходов.
100*2-5=195

(146) закрыть надо по условию, а вот куда кот после этого пойдет - вопрос

тем более когда ящиков 100

+(147) собственно доказательство (113) это и говорит

(146) знать что кот сидит во втором ящике в тот момент когда вы открываете 4й ящик и поймать кота - не одно и то же.

(149)"Можно ли вообще однозначно определить в какой коробке пятничный кот за конечное число ходов-открытий коробок"
Ничего не сказано про поймать. Только про то чтоб определить где сидит кот при открытии коробок. Я нашел при открытии где сидит кот)

*это как отгадать где деньги в двух шкатулках в поле чудес: если не угадал с первого раза, ты точно знаешь что они во второй коробке, но денег не получишь

а теперь та же задача, но коробки расположены квадратом 10 на 10

*то после закрытия этой коробки пятничный кот обязательно незаметно перебирается в одну из соседних - в конце хода он перебрался в соседнюю, вы не успели сообщить его состояние в течении своего хода

(153)В условии написано "за конечное число открытий коробок" В задачи закрытия это середина хода.
Но я понимаю после уточнения условия надо чтоб коробка закрылась, не настаиваю ни на чем.

(152) не взлетит, нет коробок с одним выходом

Я нашел пятничного кота http://mtrpl.ru/wp-content/uploads/2015/04/кот-в-коробке-3.jpg

(156) "Вы можете открыть одну из коробок и проверить наличие пятничного кота"
Если он там оказался, коробку Вы уже не сможете закрыть. ;)

(155) а если за основу взять решето эрастофена сто первых элементов и тоже оквадратить (с пропусками)

эратосфена*

Чётные и нечётные коробки...

А дальше понятно я думкю

Хорошая задача, можно с внуками играть (как в морской бой). Только, боюсь, быстро просекут стратегию охотника.