Вход | Регистрация
    1  2   
О жизни... :: Наука

OFF: Задача: тигр за дверью

OFF: Задача: тигр за дверью
Я
   Ненавижу 1С
 
23.12.21 - 19:24
Есть 32 пронумерованных комнаты в ряд. В одной из комнат сидит тигр. Каждую минуту вы открываете дверь в одну из комнат. Если там тигр - вы его "поймали". Если нет - вы закрываете дверь. После чего тигр обязательно переходит в соседнюю комнату по отношению к той, где был - в одну из сторон по своему усмотрению (кроме крайних комнат, там только в одну сторону). После чего всё повторяется.
Можно ли гарантированно "поймать" тигра и если да - то сколько минут для этого понадобится?
   RomanYS
 
1 - 23.12.21 - 19:39
Поймать точно можно. 64 точно хватит, а для нахождения минимума думать надо :)
   Irbis
 
2 - 23.12.21 - 19:45
Про кота Шредингера задачу переписали? Через смену четности решается задача. Тигр этого сделать не может, а искатель может открыть одну и ту же дверь. ЕМНИП 2N-1 открытий потребуется в пиковом случае. Последнюю дверь можно не открывать
   Ведущий
 
3 - 23.12.21 - 19:54
Можно, за 2 * N - 2
   PR
 
4 - 23.12.21 - 20:41
(1) Для открытия 32 комнат хватит 64 открытий?
Эээ... кхм, ну, да, хватит
   PR
 
5 - 23.12.21 - 20:43
+(4) А, дверь же закрывается и тигр может в нее перейти, ну да
   ReaLg
 
6 - 23.12.21 - 21:34
Не 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.
   ReaLg
 
7 - 23.12.21 - 21:36
Не, 120. В конце 32-30, все.
   ReaLg
 
8 - 23.12.21 - 21:38
Хотянет:) 31-29-30-31 и еще раз 31.Тогда 119 :)
   HawkEye
 
9 - 23.12.21 - 21:48
(3) скобки забыл....
   HawkEye
 
10 - 23.12.21 - 21:50
(6) со второй до предпоследней, потом еще раз предпоследнюю и назад...   т.е. два раза пройти по ряду без первой и последней ячейки
   Йохохо
 
11 - 23.12.21 - 21:51
(10) между 60 тиками 59 часов
   HawkEye
 
12 - 23.12.21 - 21:53
(11) а земля крутиться вокруг солнца....
   Tatitutu
 
13 - 23.12.21 - 22:52
Минумум= 1
(если очень повезет)
Максимум = бесконечность

(в одну из сторон по своему усмотрению)
   DomovoiAtakue
 
14 - 23.12.21 - 23:03
(0)61 мин (62 открытия дверей)
   PR
 
15 - 23.12.21 - 23:23
(0) 63
1, 2, 3 ... 32, 32, 31 ... 3, 2
   hhhh
 
16 - 24.12.21 - 00:05
(15) не, так не поймаешь. Гарантированно вот так

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

то есть гарантированно за 62 отрывания можно поймать.
   Dmitry77
 
17 - 24.12.21 - 00:11
Можно упростить задачу. Пусть будет 3 двери. Можно ли поймать тигра? Да за 2 шага максимум сначала среднюю, потом ещё раз среднюю.

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

Ответ тигр может бесконечно бегать.
   Dmitry77
 
18 - 24.12.21 - 00:13
(16) тигр в третьей комнате движется строго к первой
   Йохохо
 
19 - 24.12.21 - 00:15
(17) 2332
   hhhh
 
20 - 24.12.21 - 00:22
(18) да, не получается.
   Dmitry77
 
21 - 24.12.21 - 00:35
(19) для 4 комнат действительно хватит 4 раз.
Интересно как для пяти? Что - то голова уже не соображает
   hhhh
 
22 - 24.12.21 - 00:39
(21) то есть тогда получается как у PR в (15), только без последней ячейки

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

60 открываний
   Йохохо
 
23 - 24.12.21 - 00:45
(21) дана подсказка в теме, пусть кто хочет порешает
   PR
 
24 - 24.12.21 - 00:50
(16) В начале он в 3, передвигается по одной к началу, лови
   hhhh
 
25 - 24.12.21 - 01:15
(24) я уже понял, (22) тогда
   exwill
 
26 - 24.12.21 - 01:24
(15) Что мешает тигру проскочить через тебя на пути обратно?
   PR
 
27 - 24.12.21 - 01:49
(25) 1 в начале пропускать нельзя, он там мог быть с самого начала и идти за тобой по пятам
   PR
 
28 - 24.12.21 - 01:50
(26) Условия задачи мешают
   hhhh
 
29 - 24.12.21 - 01:54
(27) если идет по пятам, то 31-31 решает проблему, он оказывается в ячейке 29, и дальше у него нет выбора. Идет назад в ячейку 1.
   hhhh
 
30 - 24.12.21 - 02:00
(27) тут 2 варианта: четные или нечетные. Если он изначально стоит на четной ячейке, например, ячейка 4, тогда без вариантов оттесняем его на ячейку 32 к 30 ходу. Второй вариант: нечетные, тогда он идет по пятам, но на 31м ходу попадает на ячейку 29, и потом спокойно оттесняется в ячейку 1. К 60-му ходу.
 
 
   DrZombi
 
31 - 24.12.21 - 06:06
0.23 минуты
   Krendel
 
32 - 24.12.21 - 06:09
Если комнаты в ряду, то их число конечно и это 32, минимум 1
   osa1C
 
33 - 24.12.21 - 06:36
(0) лучше бы задал вопрос про и игру на шашечной доске "Заяц и Волки" (во всяком случае так мы это называли в детстве.... Есть ещё название "Овца и Волки"). Смысл игры в том что есть 4 Вока, которые ходят только по черным клеткам и только вперед. И один белый Заяц, который ходит тоже только по черным клеткам, но имеет право ходить и вперед и назад. Задача Зайца прорваться между волками на другую сторону доски. У Волков же задача загнать Зайца, так чтобы у него не было ходов не вперед, не назад.
   osa1C
 
34 - 24.12.21 - 06:42
(33) + ну а по сабжу.... двухстволка и 2^4 патронов хватит, чтобы выловить тигра за 2^3 секунд. Просто двери надо не открывать!!!! Там может быть Тигр, а стрелять через дверь. БЕЗОПАСНОСТЬ превыше всего )))
   Вася Теркин
 
35 - 24.12.21 - 06:49
Нет минимального количества. Попробуй проще. Есть две двери и тигр постоянно переходит из двери в дверь и ты постоянно переходишь... И никогда не поймаешь. Одной ладьей поставить шах невозможно
   osa1C
 
36 - 24.12.21 - 06:51
(35) Шах ладьей поставить НЕВОЗМОЖНО?  Вы уверены, Мессир?
   Вася Теркин
 
37 - 24.12.21 - 06:51
Мат, конечно
   Вася Теркин
 
38 - 24.12.21 - 06:52
Как узнать что тигр в соседней комнате? Тигр и игрок проходят друг через друга легко бесконечное количество раз
   osa1C
 
39 - 24.12.21 - 06:52
(37) можно и мат.... Там же кроме ладьи есть Король
   K1RSAN
 
40 - 24.12.21 - 06:52
Странно, что никто не решил написать простенькую программу, которая бы имитировала эту задачу)
   Krendel
 
41 - 24.12.21 - 06:53
(39) Думаю это задача решена
   Вася Теркин
 
42 - 24.12.21 - 06:54
(39) Здесь короля нет, только край доски. Ты край двигать можешь? Нужен ещё капкан чтобы подкладывать в комнату. Тогда можно поймать тигра.
Открываешь комнату и можешь положить капкан. Или забрать... Хотя капкана скорее всего понадобится два
   osa1C
 
43 - 24.12.21 - 06:54
(42) Шах и Мат https://ibb.co/02jg1zt
   Вася Теркин
 
44 - 24.12.21 - 06:56
открываешь первую дверь, ставишь капкан
открываешь третью дверь, ставишь второй капкан,
открываешь первую дверь, убираешь капкан,
Открываешь пятую дверь, ставишь капкан....
   osa1C
 
45 - 24.12.21 - 06:58
(44) читай (34) там решение лучше
   Вася Теркин
 
46 - 24.12.21 - 06:58
(45) Нет, #шкурупопортишь. Нехорошо.
   Вася Теркин
 
47 - 24.12.21 - 06:59
(43) Нет короля тут. Одна ладья голая
   Вася Теркин
 
48 - 24.12.21 - 07:00
(34)  тут говорят что за дверью может быть не только тигр, но и король. Это терракт получится.
   osa1C
 
49 - 24.12.21 - 08:12
(47) Король есть всегда.... И их даже два ))) как минимум
   Вася Теркин
 
50 - 24.12.21 - 08:55
(49) Нет. В парламентской демократии королям головы рубят, там только нация, пешки.
   Kassern
 
51 - 24.12.21 - 09:36
(28) И в каком это месте "Условия задачи мешают"? Читаем внимательно: "Каждую минуту вы открываете дверь в одну из комнат. Если ТАМ тигр - вы его "поймали". ПОСЛЕ чего тигр обязательно переходит в соседнюю комнату". Ключевые слова я выделил. Получается, что открыв дверь 3, когда тигр был в 4, мы его не находим и закрываем дверь, после этого тигр может успешно перейти в комнату 3 и это не нарушит условие задачи, ведь "поймать" его мы может только в комнате по условию!
   Kassern
 
52 - 24.12.21 - 09:38
(26) "Что мешает тигру проскочить через тебя на пути обратно?" Получается, что ничего не мешает
   Ненавижу 1С
 
53 - 24.12.21 - 09:39
(51) нам же никто не мешает открыть снова эту же комнату?
   Kassern
 
54 - 24.12.21 - 09:40
(53) но по условию в (15) мы откроем следующую дверь. В задаче же не указано, что мы видим как перемещается тигр, мы только знаем, что он может сместиться в соседнюю комнату и начального его положения не известно.
   Kassern
 
55 - 24.12.21 - 09:42
(53) а тигру ничего не мешает шагнуть в другую комнату)
   Йохохо
 
56 - 24.12.21 - 09:42
(54)он обязан сместиться
   Ненавижу 1С
 
57 - 24.12.21 - 09:44
(54) там конечно избыточно - достаточно 60 открываний: 2,3,...,30,31,31,30,...,3,2
И да, если мы его не поймали после повторного открытия 31, то он "слева", но только в определенных комнатах в определенные ходы )))
   Kassern
 
58 - 24.12.21 - 09:45
(56) ага, вот мы открываем 3 дверь, тигр в 4. Отсюда он может переместиться как в 3 так и в 5. А теперь смотрим варианты: мы пошли в 4, он сместился в 3, мы пошли снова в 3, он сместился в 5, мы пошли в 5, он ушел в 3 и так до бесконечности.
   Kassern
 
59 - 24.12.21 - 09:48
просто видимо для вас "поймать" тигра, значит с ним пересечься, а в условии задачи именно открыть комнату с ним.
   Йохохо
 
60 - 24.12.21 - 09:48
(58) ну так тебе и нужно найти умный алгоритм а не просто бездумно хлопать
 
 
   Kassern
 
61 - 24.12.21 - 09:49
(60) самый худший вариант, это когда тигр знает куда пойдет искатель. В этом случае можно написать алгоритм, при котором вы никогда не найдете тигра. Получается, что есть такая вероятность, что тигр не будет найден
   Йохохо
 
62 - 24.12.21 - 09:51
(61) 4 клетки, охотник идет 2332, попробуй выиграть за тигра)
   Kassern
 
63 - 24.12.21 - 09:52
(62) только тут 32 клетки и уже шансы по более будут)
   Kassern
 
64 - 24.12.21 - 09:55
другое бы дело, если бы искатель закрывал дверь уже после смещения тигра, тогда пересечений бы не было и за фиксированное количество ходов можно было бы поймать.
   Йохохо
 
65 - 24.12.21 - 09:56
(63) ноль не больше нуля и при 1024 дверях
   Smallrat
 
66 - 24.12.21 - 09:57
(61) такой и должен быть алгоритм поведения тигра, типа он не рандомно прыгает, а зная, какая дверь будет открыта, перемещается соответственно и алгоритм открывания должен быть такой, чтобы тигр гарантированно нашелся при таком его поведении. Если есть такое поведение тигра, что он может бесконечно быть не пойманным, то задача соответственно не имеет решения.
   Kassern
 
67 - 24.12.21 - 10:00
(66) именно об этом я и пишу, что зная какую дверь открывает искатель, тигр может бесконечно перемещаться. Нет условий запрещающих пересечения искателя и тигра, так же нет информации, что искатель в курсе после закрытия двери, что в нее мог зайти тигр.
   Smallrat
 
68 - 24.12.21 - 10:01
(67) ну вот с 4 мя дверями уже показали алгоритм нахождения - 2332, а с 5ю? есть такой алгоритм или нет?
   Йохохо
 
69 - 24.12.21 - 10:01
(66) ну он не знает как бы, но ему доступен полный перебор стратегий и выбор лучшей
(67) "Нет условий запрещающих пересечения искателя и тигра" ты не поверишь) есть
   Ryzeman
 
70 - 24.12.21 - 10:01
(26) (52) тигр обязан перемещаться после каждого твоего действия. Каждый ход тигр может находиться либо на чётной либо на нечётной клетке. Если ты проходишь все двери последовательно, то единственный сценарий, по которому ты пропускаешь тигра это если ты стоишь на чётной, а тигр на нечётной и наоборот. Ты можешь сменить фазу, тигр - нет, потому что он обязан каждый раз менять чётность, а ты можешь выбрать ту же дверь.
   Ненавижу 1С
 
71 - 24.12.21 - 10:02
Нарисуем вот такую картинку
https://drive.google.com/file/d/1lK_NXjwqG8XNio_c-TYMVR-6EMrEGu_K/view?usp=sharing
Здесь номера столбцов - это номера комнат (пример дан для 7 комнат).
Номера строк - это ходы (время).
Крестиками отмечены открывания дверей на определенном ходу (по 1 на каждой горизонтали).
То есть один горизонтальный слой это очередное положение после открытия двери.
Если схему раскрасить в шахматном порядке, то получается тигр во времени движется по диагонали по клеткам одного цвета.

В конкретной раскраске - если он движется по белым клеткам, то будет пойман в первой половине алгоритма, если по черным - во второй.
   pechkin
 
72 - 24.12.21 - 10:02
нужно тигра в угол зажать и тогда он вынужден будет в дверь выйти
   Smallrat
 
73 - 24.12.21 - 10:11
(69) ну так как он рандомно перемещается, то по рандому ему доступны все возможные варианты поведения, соответственно мы рассматриваем самую оптимальную с точки зрения тигра последовательность ходов, хотя все это поведение тигра неважно - в (71) собственно решение, не зависящее от поведения тигра.
   Kassern
 
74 - 24.12.21 - 10:14
(70) с четностью да, получается фиксированное количество ходов. Прям издевательство на животным(
   Йохохо
 
75 - 24.12.21 - 10:16
есть 32 тигра и 2 клетки с дверьми, тигры по очереди заходят в одну из клеток, после чего охотник открывает одну из дверей и, если там тигр, съедает его. Если охотник не угадал тигр убегает. Охотник съел 30 тигров, какой шанс, что он съест тридцать первого? (вроде правильный рерайт =) )
   Kassern
 
76 - 24.12.21 - 10:16
(73) тут в (70) верно сказали, например для 5 клеток, как бы не сходил тигр, последовательность 2345432 его все равно поймает
   Kassern
 
77 - 24.12.21 - 10:17
(76) очепятался 23455432
   Kassern
 
78 - 24.12.21 - 10:17
я за равноправие с тигром, пущай искатель ходит так же)
   pechkin
 
79 - 24.12.21 - 10:19
(77) нет конечно же
д:  2 3 4 5 4 3 2
т:  3 4 3 4 3 4 3
   Ненавижу 1С
 
80 - 24.12.21 - 10:20
Теперь покажем, что не существует гарантированной стратегии за меньшее открывание дверей.
Если она есть, то значит какую-то из НЕ крайних (имеющих соседнюю слева и справа) мы открывали не более одного раза.
Воспользуемся все той же картинкой-раскраской
https://drive.google.com/file/d/1ZfYtPlPpCXBdfYpOKgbqMs3kXcWnEO9D/view?usp=sharing
Пусть мы поставили в какой-то НЕ крайней вертикали только один крестик. Пусть на черное поле. Важно, что есть оба соседа!
Тогда пусть тигр движется по белым клеткам "колеблясь" возле данной вертикали - отмечено Т.
На данной вертикали по условию задачи его никто не поймает - там только один крест и он на черной клетке.
На соседних вертикалях у него две позиции, но мы не можем на обе поставить кресты (только один крест на горизонтали).
В результате у тигра есть шанс остаться не пойманным при меньшем числе ходов.
   pechkin
 
81 - 24.12.21 - 10:20
(77)  
2 3 4 5 5 4 3 2
3 4 3 4 3 2 3 4
   Kassern
 
82 - 24.12.21 - 10:20
(81) а вас 3/3 в конце не смущает?))
   pechkin
 
83 - 24.12.21 - 10:22
(82) действительно ловится
   Kassern
 
84 - 24.12.21 - 10:25
(83) вот если бы тигр мог остаться в комнате, то все бы было иначе...
   Smallrat
 
85 - 24.12.21 - 10:45
(84) думаю он бы не ловился
   ManyakRus
 
86 - 24.12.21 - 11:14
план:
1) открываем двери по-порядку 2..31
если тигр не попался значит он был за нечётной дверью изначально
2) открываем все двери по-порядку начиная с нечётной 1..31
тигр уже не сможет убежать туда где вы уже были
в клетке 32 он не может спрятаться в конце т.к. когда я за нечётной дверью то и тигр за нечётной
Итого 59 открываний
   El_Duke
 
87 - 24.12.21 - 11:21
(0) Из условия неясно можно ли открывать одну дверь 2 раза подряд
Про тигра сказано что он обязательно переходит, а охотник должен ли переходить ?
   ManyakRus
 
88 - 24.12.21 - 11:23
(86) ответ 61 открываний
   pechkin
 
89 - 24.12.21 - 11:24
(87) раз не сказано значит можно. каждый раз можно любую открывать
   El_Duke
 
90 - 24.12.21 - 11:40
(88) правильно
Предположим тигер во 2 комнате. Начинаем открывать все двери с первой, по два раза. Если тигер переходит из 2 в 1 - спалится на 2 ходу. Если в 3 и далее, гоним его в конец коридора, открывая каждую дверь 2 раза. На 60 ходу тигер окажется в 62 комнате, откуда ему ход только в 61, там то мы его на 61 ходу и накроем подлеца
   Йохохо
 
91 - 24.12.21 - 11:43
(90) тебе попался тигр неудачник, удачник свалит
   ManyakRus
 
92 - 24.12.21 - 13:27
(90) по 2 раза открывать бесполезно,
тигр всё равно проскочит туда где вы уже смотрели
   Arbuz
 
93 - 24.12.21 - 13:29
По условиям задачи тигра поймать невозможно. На любую вашу стратегию могу предложить выигрышную для тигра. Дорого.
Например, в (90) на первом ходу тигр в 2, потом 3, 4, 3, 2, ну до конца (1,2).
   pechkin
 
94 - 24.12.21 - 13:31
(93) приведи для такого 2 3 4 5 5 4 3 2
   ManyakRus
 
95 - 24.12.21 - 13:34
(94) мой план такой же но более общий:
сначала открыть все двери начиная с чётного
потом все двери начиная с нечётного
   Arbuz
 
96 - 24.12.21 - 13:34
(94) 6 6 6 6 6 6 6 )))
   Arbuz
 
97 - 24.12.21 - 13:35
+ (96) 1 1 1 1 1 1 1 1
   Ненавижу 1С
 
98 - 24.12.21 - 13:35
(96) (97) Тигр не может сидеть на одном месте, ты проиграл
   pechkin
 
99 - 24.12.21 - 13:36
(97) ты не прочитал условие. Тигр должен менять место каждый раз
   Arbuz
 
100 - 24.12.21 - 13:36
(97) вы нарушаете условия задачи комнат 64
  1  2   

Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.