maper (maper) wrote,
maper
maper

Category:

задача про крысу

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

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

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

upd. Вы (охотник) находитесь снаружи поезда и не видите, что внутри, но можете стрелять по любому вагону. После выстрела крыса может перейти в любой соседний вагон. Оба уточнения сделаны по просьбе одного из посетителей страницы, считающего, что без них задача сформулирована неполно.
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 28 comments