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

(51) нам же никто не мешает открыть снова эту же комнату?

(53) но по условию в (15) мы откроем следующую дверь. В задаче же не указано, что мы видим как перемещается тигр, мы только знаем, что он может сместиться в соседнюю комнату и начального его положения не известно.

(53) а тигру ничего не мешает шагнуть в другую комнату)

(54)он обязан сместиться

(54) там конечно избыточно - достаточно 60 открываний: 2,3,...,30,31,31,30,...,3,2
И да, если мы его не поймали после повторного открытия 31, то он "слева", но только в определенных комнатах в определенные ходы )))

(56) ага, вот мы открываем 3 дверь, тигр в 4. Отсюда он может переместиться как в 3 так и в 5. А теперь смотрим варианты: мы пошли в 4, он сместился в 3, мы пошли снова в 3, он сместился в 5, мы пошли в 5, он ушел в 3 и так до бесконечности.

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

(58) ну так тебе и нужно найти умный алгоритм а не просто бездумно хлопать

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

(61) 4 клетки, охотник идет 2332, попробуй выиграть за тигра)

(62) только тут 32 клетки и уже шансы по более будут)

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

(63) ноль не больше нуля и при 1024 дверях

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

(66) именно об этом я и пишу, что зная какую дверь открывает искатель, тигр может бесконечно перемещаться. Нет условий запрещающих пересечения искателя и тигра, так же нет информации, что искатель в курсе после закрытия двери, что в нее мог зайти тигр.

(67) ну вот с 4 мя дверями уже показали алгоритм нахождения - 2332, а с 5ю? есть такой алгоритм или нет?

(66) ну он не знает как бы, но ему доступен полный перебор стратегий и выбор лучшей
(67) "Нет условий запрещающих пересечения искателя и тигра" ты не поверишь) есть

(26) (52) тигр обязан перемещаться после каждого твоего действия. Каждый ход тигр может находиться либо на чётной либо на нечётной клетке. Если ты проходишь все двери последовательно, то единственный сценарий, по которому ты пропускаешь тигра это если ты стоишь на чётной, а тигр на нечётной и наоборот. Ты можешь сменить фазу, тигр - нет, потому что он обязан каждый раз менять чётность, а ты можешь выбрать ту же дверь.

Нарисуем вот такую картинку
https://drive.google.com/file/d/1lK_NXjwqG8XNio_c-TYMVR-6EMrEGu_K/view?usp=sharing
Здесь номера столбцов - это номера комнат (пример дан для 7 комнат).
Номера строк - это ходы (время).
Крестиками отмечены открывания дверей на определенном ходу (по 1 на каждой горизонтали).
То есть один горизонтальный слой это очередное положение после открытия двери.
Если схему раскрасить в шахматном порядке, то получается тигр во времени движется по диагонали по клеткам одного цвета.

В конкретной раскраске - если он движется по белым клеткам, то будет пойман в первой половине алгоритма, если по черным - во второй.

нужно тигра в угол зажать и тогда он вынужден будет в дверь выйти

(69) ну так как он рандомно перемещается, то по рандому ему доступны все возможные варианты поведения, соответственно мы рассматриваем самую оптимальную с точки зрения тигра последовательность ходов, хотя все это поведение тигра неважно - в (71) собственно решение, не зависящее от поведения тигра.

(70) с четностью да, получается фиксированное количество ходов. Прям издевательство на животным(

есть 32 тигра и 2 клетки с дверьми, тигры по очереди заходят в одну из клеток, после чего охотник открывает одну из дверей и, если там тигр, съедает его. Если охотник не угадал тигр убегает. Охотник съел 30 тигров, какой шанс, что он съест тридцать первого? (вроде правильный рерайт =) )

(73) тут в (70) верно сказали, например для 5 клеток, как бы не сходил тигр, последовательность 2345432 его все равно поймает

(76) очепятался 23455432

я за равноправие с тигром, пущай искатель ходит так же)

(77) нет конечно же
д:  2 3 4 5 4 3 2
т:  3 4 3 4 3 4 3

Теперь покажем, что не существует гарантированной стратегии за меньшее открывание дверей.
Если она есть, то значит какую-то из НЕ крайних (имеющих соседнюю слева и справа) мы открывали не более одного раза.
Воспользуемся все той же картинкой-раскраской
https://drive.google.com/file/d/1ZfYtPlPpCXBdfYpOKgbqMs3kXcWnEO9D/view?usp=sharing
Пусть мы поставили в какой-то НЕ крайней вертикали только один крестик. Пусть на черное поле. Важно, что есть оба соседа!
Тогда пусть тигр движется по белым клеткам "колеблясь" возле данной вертикали - отмечено Т.
На данной вертикали по условию задачи его никто не поймает - там только один крест и он на черной клетке.
На соседних вертикалях у него две позиции, но мы не можем на обе поставить кресты (только один крест на горизонтали).
В результате у тигра есть шанс остаться не пойманным при меньшем числе ходов.

(77)  
2 3 4 5 5 4 3 2
3 4 3 4 3 2 3 4

(81) а вас 3/3 в конце не смущает?))

(82) действительно ловится

(83) вот если бы тигр мог остаться в комнате, то все бы было иначе...

(84) думаю он бы не ловился

план:
1) открываем двери по-порядку 2..31
если тигр не попался значит он был за нечётной дверью изначально
2) открываем все двери по-порядку начиная с нечётной 1..31
тигр уже не сможет убежать туда где вы уже были
в клетке 32 он не может спрятаться в конце т.к. когда я за нечётной дверью то и тигр за нечётной
Итого 59 открываний

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

(86) ответ 61 открываний

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

(88) правильно
Предположим тигер во 2 комнате. Начинаем открывать все двери с первой, по два раза. Если тигер переходит из 2 в 1 - спалится на 2 ходу. Если в 3 и далее, гоним его в конец коридора, открывая каждую дверь 2 раза. На 60 ходу тигер окажется в 62 комнате, откуда ему ход только в 61, там то мы его на 61 ходу и накроем подлеца

(90) тебе попался тигр неудачник, удачник свалит

(90) по 2 раза открывать бесполезно,
тигр всё равно проскочит туда где вы уже смотрели

По условиям задачи тигра поймать невозможно. На любую вашу стратегию могу предложить выигрышную для тигра. Дорого.
Например, в (90) на первом ходу тигр в 2, потом 3, 4, 3, 2, ну до конца (1,2).

(93) приведи для такого 2 3 4 5 5 4 3 2

(94) мой план такой же но более общий:
сначала открыть все двери начиная с чётного
потом все двери начиная с нечётного

(94) 6 6 6 6 6 6 6 )))

+ (96) 1 1 1 1 1 1 1 1

(96) (97) Тигр не может сидеть на одном месте, ты проиграл

(97) ты не прочитал условие. Тигр должен менять место каждый раз

(97) вы нарушаете условия задачи комнат 64

тогда я тоже могу

(101) что ты можешь?

(100) неправда, 32

(99) он просто ждет, когда тигр к нему придет

(100) те только для 64 комнат нельзя поймать. А для меньшего можно?

(105) Да можно для любого, я проиграл )) куда деньги слать?

(106) вот сюда http://amur-tiger.ru/ru/ у них свой фонд есть)

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

(50) Короли всегда возвращаются ив Испании и во Франции и даже блин в России

(0) нет нельзя, ибо тигр может гулять между двумя комнатами, а ты открывать их когда его нет

(110) возьмите 5 комнат и придуймайте алгоритм для тигра, чтобы его не поймали. охотник будет ходить так 23455432

тот же принцип работает и на N комнат

(111) 234432 будет для пяти комнат.
Ответ в самом начале темы дали правильный, 2N-4

(113) 234432 - ответ неправильный, убежит тигр
23455432 - ответ почти правильный, но дверь 1 тоже надо открывать в конце т.к. задача поймать тигра а не узнать где он прячется

мой ответ: 2N-3

(114) ну тогда 2N-2, потому что надо количество минут, а не количество открываний двери

(114) "ответ неправильный, убежит тигр " напишите последовательность, при которой он убежит)

(115) нет нулевой минуты бесплатной, всё равно 2N-3

(117) Напиши, как тигр убежит. Гипотетический тигр в комнате 1 на последнем ходу ловится в первые три хода, тащемто

(116)
охотник: 234432
тигрррр: 212345
открывать дверь 2 раза подряд бесполезно :-)

(119) на первом ходу это что такое?

(119) вы издеваетесь над животными?? Сразу к охотнику пихнули?)

(120) я неправ :-(
но в общем случае это всё равно неправильно решение если дверей было бы больше,
просто совпадение что дверей мало

(122) попробуйте на 10 дверях, так же будет наглядно

(123) просто в экселе нарисуйте по числу в каждой ячейке 2345678998765432 и напротив попробуйте алгоритм для тигра придумать

правильно: обойти всё начиная с чётного, потом начиная с нечётного
неправильно: обойти всё начиная с чётного два раза
234+432 = обход два раза начиная с чётного числа

(125) вы видимо не поняли смысл, зачем в одной комнате охотник ждет. Это нужно, чтобы сменить "фазу" после прохода всех комнат, кроме крайних. Это дает 100% возможность поймать тигра.

(125) первым проходом мы 100% убеждаемся, что справа нет хищника. А раз мы его не встретили, значит наши фазы хода не совпали (мы на четных, тигр на нечетных к примеру), как только мы подождали ход, мы убедились, что он не в крайней точке и сменили фазу, теперь тигру некуда деваться

(125) Вы не правы. Суть в том, что четность двери тигра каждый раз меняется. Поэтому начинаем с 2 и допредпоследней. Таким образом, если тигр был в четной двери в начале, то он будет гарантированно пойман. Если же тигр был в нечетной двери, то второй раз проходим этот же маршрут назад, и, таким образом, не оставляем тигру шансов.
(127) "первым проходом мы 100% убеждаемся, что справа нет хищника." - ложное утверждение. Первым проходом мы убеждаемся что в начале тигр не был в четной двери.

(128) первым проходом+повтором предпоследней двери)

(129) Первым ходом тигр был правее в 3-й двери, и идет влево, поймаете его первым проходом?

(128) можете назвать случай, когда тигр будет правее охотника при первом проходе+ повторе предпоследней двери?

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

(128) мой ответ точно такой же как твой,
поэтому мы оба правы, и я не могу быть неправ.
Зато я первым написал алгоритм :-)

(133) "неправильно: обойти всё начиная с чётного два раза
234+432 = обход два раза начиная с чётного числа" вы утверждаете, что это не верно, но не привели ни 1 примера, когда это не работает

(132) В таком случае некорректно высказывание "первым проходом мы 100% убеждаемся, что справа нет хищника.", т.к. в начале тигр может быть правее и первым проходом мы его не ловим.
Корректно высказывание "первым проходом мы 100% убеждаемся, что _в конце первого прохода_ справа нет хищника."

(126) наверно ты прав :-)
сменить фазу надо если всего количество дверей нечётное (=5)

(134) это не работает если количество дверей>5 и чётное
как и задано в задаче
т.е. ответ неправильный в общем случае
ответ случайно правильный для одного случая 5 дверей

(137) приведите пример для 6 дверей и алгоритма охотника 23455432, когда хищник его обходит

(137) я привел 5 дверей, так как это наглядно

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

(138)
2345+5432 - это ответ правильный
т.к. сначала с чётного потом с нечётного
неправильно - два раза с нечётного

(138)
2345+5432 - это ответ правильный
т.к. сначала с чётного потом с нечётного
неправильно - два раза с чётного

(142) окей, давайте для 7 дверей, тогда 2345665432 устроит?

еще раз показывает, что вы не уловили суть первого прохода и стояния в пердпоследней комнате)

(143) 7 - 2 раза должна быть

(145) зачем? Напишите алгоритм тигра, который это обойдет

(140) всё правильно мыслишь, везде прав :-)
только решать надо для общего случая сколько угодно дверей, или 32 дверей

(147) на небольших примерах просто наглядней, каждый может сам попробовать полосатого спасти)

(71) и (80) смотри

(9) Действительно, со скобками нужно было. Короче, за 60 открываний.

2 * N - 4 или 2 * (N - 2)

(147) формула для общего случая дана еще в (3) правда без скобок...