Найти пятничного кота #758186

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ТС в   посмотри

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

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

я уже в отметил

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

точно, тогда и не решение, вы меня обманывали!

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

+ на складе?

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

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

хотя тоже не взлетит

может менять конечно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

это из

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение. Всего 198 открытий-ходов. Перенумеруем подряд коробки от 1 до 100. Открываем в 2 акта. Акт 1: открываем с 1 по 99 коробки подряд Акт 2: открываем с 99 по 1 коробки подряд Акт 1. Если кот не собирается пересекать "фронт открываемых коробок", то мы его загоняем в 100-ю и так как 99-ю открываем дважды, он будет пойман. Если кот пересекает "фронт открываемых коробок", то значит когда мы открывали N-ю он сидел в (N+1)-й и переползает в N-ю. Итак, значит когда мы открываем четную коробку, кот сидит в нечетной и наоборот. Акт 2. На начало акта кот сидел в нечетной коробке. Мы снова открываем 99-ю и кот из нечетной переползает в четную. Теперь открывая четную кот сидит в четной, то есть четности совпадают. И снова пересечь "фронт открываемых коробок" кот не сможет.

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

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

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

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

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

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

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

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

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

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

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

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