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

Поймать точно можно. 64 точно хватит, а для нахождения минимума думать надо :)

Про кота Шредингера задачу переписали? Через смену четности решается задача. Тигр этого сделать не может, а искатель может открыть одну и ту же дверь. ЕМНИП 2N-1 открытий потребуется в пиковом случае. Последнюю дверь можно не открывать

Можно, за 2 * N - 2

(1) Для открытия 32 комнат хватит 64 открытий?
Эээ... кхм, ну, да, хватит

+(4) А, дверь же закрывается и тигр может в нее перейти, ну да

Не 64 мало ИМХО, по три проверять надо. Предположим, мы знаем, что в k ячейках включительно "слева" его нет. Открываем k+1, в этот момент он может "проскочить в "k". Значит потом надо еще раз пробежать k-1, k, k+1.
Начинаем 2х вторая слева. после этого в первой и второй слева его нет. потом 3-1-2-3 потом 4-2-3-4 .... 31-29-30-31-32-30-31
Итого 2 + 4*29 + 3 = 121.

Не, 120. В конце 32-30, все.

Хотянет:) 31-29-30-31 и еще раз 31.Тогда 119 :)

(3) скобки забыл....

(6) со второй до предпоследней, потом еще раз предпоследнюю и назад...   т.е. два раза пройти по ряду без первой и последней ячейки

(10) между 60 тиками 59 часов

(11) а земля крутиться вокруг солнца....

Минумум= 1
(если очень повезет)
Максимум = бесконечность

(в одну из сторон по своему усмотрению)

(0)61 мин (62 открытия дверей)

(0) 63
1, 2, 3 ... 32, 32, 31 ... 3, 2

(15) не, так не поймаешь. Гарантированно вот так

1, 1, 2, 2, 3, 3, ..., 31, 31.

то есть гарантированно за 62 отрывания можно поймать.

Можно упростить задачу. Пусть будет 3 двери. Можно ли поймать тигра? Да за 2 шага максимум сначала среднюю, потом ещё раз среднюю.

Пусть 4 комнаты. И тут как не открывай двери тигр всегда может уйти в свободную соседнюю.

Ответ тигр может бесконечно бегать.

(16) тигр в третьей комнате движется строго к первой

(17) 2332

(18) да, не получается.

(19) для 4 комнат действительно хватит 4 раз.
Интересно как для пяти? Что - то голова уже не соображает

(21) то есть тогда получается как у PR в (15), только без последней ячейки

2, 3, ..., 30, 31, 31, 30, ..., 4, 3, 2

60 открываний

(21) дана подсказка в теме, пусть кто хочет порешает

(16) В начале он в 3, передвигается по одной к началу, лови

(24) я уже понял, (22) тогда

(15) Что мешает тигру проскочить через тебя на пути обратно?

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

(26) Условия задачи мешают

(27) если идет по пятам, то 31-31 решает проблему, он оказывается в ячейке 29, и дальше у него нет выбора. Идет назад в ячейку 1.

(27) тут 2 варианта: четные или нечетные. Если он изначально стоит на четной ячейке, например, ячейка 4, тогда без вариантов оттесняем его на ячейку 32 к 30 ходу. Второй вариант: нечетные, тогда он идет по пятам, но на 31м ходу попадает на ячейку 29, и потом спокойно оттесняется в ячейку 1. К 60-му ходу.

0.23 минуты

Если комнаты в ряду, то их число конечно и это 32, минимум 1

(0) лучше бы задал вопрос про и игру на шашечной доске "Заяц и Волки" (во всяком случае так мы это называли в детстве.... Есть ещё название "Овца и Волки"). Смысл игры в том что есть 4 Вока, которые ходят только по черным клеткам и только вперед. И один белый Заяц, который ходит тоже только по черным клеткам, но имеет право ходить и вперед и назад. Задача Зайца прорваться между волками на другую сторону доски. У Волков же задача загнать Зайца, так чтобы у него не было ходов не вперед, не назад.

(33) + ну а по сабжу.... двухстволка и 2^4 патронов хватит, чтобы выловить тигра за 2^3 секунд. Просто двери надо не открывать!!!! Там может быть Тигр, а стрелять через дверь. БЕЗОПАСНОСТЬ превыше всего )))

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

(35) Шах ладьей поставить НЕВОЗМОЖНО?  Вы уверены, Мессир?

Мат, конечно

Как узнать что тигр в соседней комнате? Тигр и игрок проходят друг через друга легко бесконечное количество раз

(37) можно и мат.... Там же кроме ладьи есть Король

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

(39) Думаю это задача решена

(39) Здесь короля нет, только край доски. Ты край двигать можешь? Нужен ещё капкан чтобы подкладывать в комнату. Тогда можно поймать тигра.
Открываешь комнату и можешь положить капкан. Или забрать... Хотя капкана скорее всего понадобится два

(42) Шах и Мат https://ibb.co/02jg1zt

открываешь первую дверь, ставишь капкан
открываешь третью дверь, ставишь второй капкан,
открываешь первую дверь, убираешь капкан,
Открываешь пятую дверь, ставишь капкан....

(44) читай (34) там решение лучше

(45) Нет, #шкурупопортишь. Нехорошо.

(43) Нет короля тут. Одна ладья голая

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

(47) Король есть всегда.... И их даже два ))) как минимум

(49) Нет. В парламентской демократии королям головы рубят, там только нация, пешки.

(28) И в каком это месте "Условия задачи мешают"? Читаем внимательно: "Каждую минуту вы открываете дверь в одну из комнат. Если ТАМ тигр - вы его "поймали". ПОСЛЕ чего тигр обязательно переходит в соседнюю комнату". Ключевые слова я выделил. Получается, что открыв дверь 3, когда тигр был в 4, мы его не находим и закрываем дверь, после этого тигр может успешно перейти в комнату 3 и это не нарушит условие задачи, ведь "поймать" его мы может только в комнате по условию!

(26) "Что мешает тигру проскочить через тебя на пути обратно?" Получается, что ничего не мешает

(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) правда без скобок...