Ловля крыс

[Dendr]

Наткнулся вот на замечательную задачу. Несложная, если сразу поймать принцип.
Копирую из источника as is.

Имеется плотный ряд из 1000 картонных коробок, соединенных между собой дырками, через которые может перебежать крыса из коробки в коробку.
У вас в руках пистолет с неограниченным боезапасом, и перед вами задача: пристрелить крысу, обитающую внутри. Любое попадание в коробку, где на данный момент находится крыса, считается для зверя фатальным (а мимо коробок вы не промахиваетесь), но саму коробку не вредит (по любой коробке можно стрелять хоть сто раз).
Проблема в том, что крысу вы никогда не увидите, также вы не узнаете, удалось ли ее убить, ни по характерным воплям, ни по луже крови.
Крыса хитрая: всякий раз после выстрела она перебегает в любую из двух соседних примыкающих коробок (не важно, простреленную или нет). Правую или левую - не суть; важно, что крыса сидит на месте только в ожидании следующего выстрела.
Какое минимальное число выстрелов нужно сделать, чтобы знать наверняка, что крыса убита? И по какой методе будете стрелять?

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

Если считаете, что нашли ответ - то пишите сюда ответ в виде числа выстрелов (порядок стрельбы не надо) - а я скажу, правильно или нет.

[Шшок]

У меня получилась безумная цифра - 500499 выстрелов. Не знаю, минимум ли это, но крысу я точно ухлопаю.

[maksim82]

1998 у меня получилось.

[molch64]

А я пристрелю эту крысу с 1996 попыток (с) Валдис Пельш

[Dendr]

У меня получилась безумная цифра - 500499 выстрелов. Не знаю, минимум ли это, но крысу я точно ухлопаю.

Ну наверное... Только скорее крыса от перенапряжения издохнет

1998 у меня получилось.

И все же можно и побыстрее. Перепроверьте - какие-то выстрелы зазря сделаны.

Интересно, кстати, добавить условие в задачу, что крыса глуховата и слышит выстрел не дальше, чем на... ну, скажем, 137 коробок. Уменьшится или увеличится минимальное число необходимых выстрелов?

[Dendr]

А я пристрелю эту крысу с 1996 попыток (с) Валдис Пельш

Вот это совсем другое дело

[maksim82]

И все же можно и побыстрее. Перепроверьте - какие-то выстрелы зазря сделаны

Угум-с. 998+998.

[molch64]

Интересно, кстати, добавить условие в задачу, что крыса глуховата и слышит выстрел не дальше, чем на... ну, скажем, 137 коробок. Уменьшится или увеличится минимальное число необходимых выстрелов?

Да ладно вам 137
Вон меня в ступор уже привел случай когда крыса глухая более, чем на 3 соседних коробки.
3 часа подряд пытаюсь хоть как-нибудь эту крысу пристрелить, но она, гадина, все время уползает!
Хотя чую, что пристрелить, конечно, можно (ибо как доказывать обратное тоже не понимаю )

P.S> А вот если крыса глухая более, чем на 2k коробок, то пристреливается не более, чем за 2k+999 ходов (можно ли меньше - не знаю).

[basil0]

Это конечно не ответ, но учитывая, что коробки простреливаются:

коробок (не важно, простреленную или нет).

Получается 1 (один) выстрел в торец цепочки.

[maksim82]

Вообще задача оч хорошая. жЫзненная.

[Шшок]

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

[molch64]

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

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

[basil0]

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

Ну в первую коробку можно вообще не стрелять (второй выстрел подряд во вторую коробку 100% убивает крысу если она вначале сидела в 1 коробке). И крыса останется жива если после 999 выстрела по второй коробке перелезет во вторую коробку и далее гуляет в 1 и 2 коробках.

[Шшок]

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

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

Гы... Ну значит, я впустую отстрелял целый арсенал, а крыска все-таки жива. Ирис скажет мне спасибо. Гринпис форевер...

[Шшок]

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

Ну в первую коробку можно вообще не стрелять (второй выстрел подряд во вторую коробку 100% убивает крысу если она вначале сидела в 1 коробке). И крыса останется жива если после 999 выстрела по второй коробке перелезет во вторую коробку и далее гуляет в 1 и 2 коробках.

Дык что тогда? По два выстрела в каждую коробку подряд кроме первой и последней - и хозяева крысы в трауре...