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

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

Кот Шредингера? Тогда он вряд ли переползёт...

(1) нет, это другой, Пятничный кот

Если он реально пятничный, то с вероятностью 50/50 ты найдёшь его в первой же коробке, или не найдёшь никогда

(3) Для начала я бы открыл вторую коробку два раза :)

А по очереди открывать, начиная с крайней, на 100 шаге точно найду котэ

(5) внимательно прочти условия задачи :)

(5) ну смотри ты открываешь 65-ю коробку, а он сидит в 66-й, ты ее закрываешь, а он переползает в 65-ю, ты открываешь 66-ю, упустил

Ряд коробок замкнут, полагаю? Если нет, то открывается первая коробка, кот переползает во вторую, т.к. она одна соседняя.

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

Есть живодерский вариант. Можно коробки попинать не открывая. Какая мявкнет, в той и кот.

(9) условия задачи ))

(9) "И закрывать коробки не собираюсь" - а вот не ври. собираешься

(10) Тогда лучше сразу стрелять.

(13) причем в торец ряда, пробивая все 100 коробок ))

(12) Так вам кота найти или коробки открывать. Если коробки закрываются, кота не словить.

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

(11) Блин, точно. Относительно коробки кота, а не октрываемой. )

(15) словить-словить, попробуй с 2 или 3 коробками сначала

(18) С тремя коробками все просто. Открываешь всегда 2 коробку , на второй ход кот точно будет пойман.

(19) да, но это не универсальный метод, на 4-х коробках уже принцип не сработает

(0) Это сложная задача. Кот пятничный, а задача не пятничная

По два раза по очереди начиная со второй коробкт проверять что ли? Я же говорю что с помощью пистолета и доброго слова можно сделать куда больше чем с помощью одного доброго слова.

(20) на 4 , два раза открываем вторую, потом отодвигаем первую. И сводим все к 19 :)

нужно открывать начиная с крайней допустим с первой: первую открыл один раз - этого достаточно, остальные открываешь по порядку, то есть дальше 2,3 и т.д., но по два раза подряд. Кот в общем случае либо найдется где-то в пути, либо будет прыгать до конца в крайнюю и там поймаешь.

(20) Для 4х коробок 2,2,3,3,2 дает гарантию поимки

Открывая одну и ту же коробку мы дождемся пока кот в неё попадет)Максимум 99 открываний если коробки замкнуты

(26) Так он может между двумя коробками в другом конце ряда бегать пока сам не сдохнет..

(26) А если не замкнуты?

(26) что такое замкнуты или не замкнуты?

(0) А кот всегда в следующую коробку переползает или может в предыдущую, ну то есть может ли он залезать дважды в одну и ту же коробку? И еще такой вопрос, коробки имеют какую-то нумерацию? Ну то есть можно ли понять, где первая коробка, а где последняя или любая может быть как первой, так и последней?

(29) по кругу или в ряд видимо

(22) да это алгоритм годный, но 199 открытий? меньше можно?

(26) В условии написано что в ряд

(32) Лучшее враг хорошего.

(31) написано же в (0) "в ряд"
(30) может и дважды и трижды, разрешаю нумеровать

То есть если мы будем уверены что кот вернется в нашу коробку, которую мы постоянно открываем, а не выпрыгнет из коробки в свободное плавание когда прыгнет в последнюю кробку

Ага, не уловил условие)

ТС в (24)  посмотри

(22) Так не взлетит же.

Т.е. ты открываешь коробку 2, там нет кота, закрываешь. Он тем временем перебегает из 4 в 3
Ты второй раз открываешь коробку 2,  там нет кота, закрываешь. Он тем временем перебегает в коробку 2.

2,2,3,3,4,4,5,5,6,6,...,97,97,98,98

(38) я уже (22) в (32) отметил

+(39) И пока ты по два раза 99 коробок открываешь, он мечется между 1-2

(39) точно, тогда (22) и (24) не решение, вы меня обманывали!

(43) Ты кота потерял чтоли?

+(44) на складе?

а кот движется в одном направлении или может менять его?

(43) от блин... ну тогда, тот же алгоритм, но каждую коробку открываешь по 100 раз (или сколько там коробок) подряд :)

(47) хотя тоже не взлетит

(46) может менять конечно

(0)По терверу только дистанция найдет кота.(с)

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

молитву перед началом можно еще прочитать..

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

Чет кажется мне, с учетом того, что Кот может в любой момент перебежать в коробку, которую ты только что закрыл - задачка не решаемая.

(53) вот наконец, только не "в конечной точке" а в предпоследней достаточно сменить, итого 198

(53) Очень даже сможет, проблема в том, что он проскакивает назад когда коробка закрывается.

если кот может перебраться в закрываемую коробку то решения нет
может вечно бегать и только теория вероятности

если же кот может перебраться в любую соседнюю исключая ту что только что открыли
то 199 открытий

Если НеудачнаяПопыткаПоиска() Тогда
    Если КотМожетСтоятьНаМесте Тогда
        МожноНайти = Ложь
    Иначе
        МожноНайти = Истина
    КонецЕсли;
КонецЕсли;

(56) если на прямом проходе он сможет проскочить, то на обратном уже не сможет

(59) Можно пример? Чет не могу сообразить.

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

(56) (60)
(НомерХода+ПоложениеКота)%2 = Константа

(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) а если за основу взять решето эрастофена сто первых элементов и тоже оквадратить (с пропусками)

эратосфена*

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

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

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