Previous Entry Share Next Entry
maper

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

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

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

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

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

  • 1
Крыса переходит в соседний вагон от выстрела или к выстрелу?

В принципе как вариант - просто стрелять в каждый нечетный вагон - таким образом ты в конце концов догонишь и убьешь крысу в поезде, либо в самом конце, затратив максимум 500 выстрелов (499?)

от выстрела или к выстрелу

В условии сказано, что после каждого выстрела крыса меняет вагон на соседний и ждет следующего выстрела. Я не знаю, как сказать яснее. Соседний - это вагон, номер которого отличается на единицу (с любым знаком) от номера вагона, из которого крыса уходит. Если крыса сидела до выстрела в вагоне номер 100, то после выстрела в вагон номер 500 она может перейти в вагон номер 99 или в вагон номер 101. Выбор из этих двух возможностей - за крысой.

Ваш метод крысу не убивает. Предположим, что в начале крыса сидит в вагоне 2. Вы стреляете в вагон 1, крыса переходит в вагон 1. Далее вы стреляете в вагоны 3, 5, и так далее, а крыса после каждого выстрела меняет прописку с вагона 1 на вагон 2 и наоборот. Ваш последний выстрел в вагон 999 тоже ничего не даст.

Если выстрел не повреждает пустой вагон - придётся последовательно расстреливать все вагоны подряд с головы до хвоста поезда по два раза каждый. Так крыса гарантированно не перескочит через фронт огня. Получается 1998 - по последнему можно не стрелять, крыса уже точно будет в предпоследнем вагоне перед 2-м выстрелом по нему.

При такой схеме крыса может перескочить фронт огня.

Да, Вы правы, я поторопился. Но от 1998 никак не уйти. :)

1998 выстрелов

на первом этапе стреляем по два раза по каждому четному вагону слева направо, по последнему четному один выстрел - всего 999

на втором этапе повторяем этап первый.

Крыса в четвертом, стреляем по второму, переходит в третий. Второй раз стреляем по второму - переходит во второй, а мы идем стрелять в четвертый.

Этап 1: Предполагаем, что изначально крыса в вагоне с четным номером, начинаем травить.
стреляем в вагон 2 - крыса или убита, или в вагоне 3, или больше - вагоны 1,2 свободны от крысы.
стреляем в вагон 3 - крыса или в вагоне 4, или дальше.
стреляем в вагон 4 - крыса или в вагоне 4, или дальше, вагоны 1,2,3,4 чисты.
... стреляем в 1000ый - крыса или убита, или мы потратили 999 выстрелов, что бы узнать, что крыса изначально была в нечетном вагоне.
Зато мы сделали 999 выстрелов, и теперь она в четном - можно повторить этап 1.

Итого 1998 выстрелов и ваша крыса точно мертва.

Поздравляю.

Мы с сыном поспорили.
Я считаю, что из множества взрослых (от 15 лет) россиян брать по одному и пытаться в течение часа объянить условие этой задачи (не решение!), то 90% просто не поймут. Не поймут, это для меня значит, не будут знать, что именно требуется, не смогут отличить верное решение от неверного и не смогут обяснить условие этой задачи третьему человеку.

Мой сын считал, что не понявших будет только 40%. Ваше мнение?

По всем критериям - ближе к 40%, по умению отличить верное решение от неверного - ближе к 90

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

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

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

Ну и напоследок, я считаю, что если вы хотите сделать опрос среди россиян, это также следовало указать в условиях задачи. Я, например, не россиянин.

с уточнениями согласен, изменил запись. Мысленный опрос я проводил среди взрослых русскоговорящих homo sapiens, россияне тут ни при чем, тут вы опять правы. Итак - взрослые, чей родной язык русский.

Если вы хотели подсчитать людей, нужно было хотя бы прятать комментарии с решением. ;)Pyrary quivocal

решение и опрос

Решение - как только оно появилось, я отметил как верное. У меня не было цели выяснять, сколько еще людей кроме первого, найдут ответ самостоятельно. Наверное, этим я лишил кого-то удовольствия, Вы правы. В следующий раз буду скринить верные решения до заданного срока.

Опроса я не планировал - я только поспорил с сыном на тему о том, каковы были бы результаты такого опроса ЕСЛИ БЫ ОН ПРОВОДИЛСЯ. Только мысленный эксперимент. И мне интересны мнения других людей о возможных результатах такого мысленного эксперимента. Ваше мнение я тоже хотел бы узнать.

Re: решение и опрос

Ваше мнение я тоже хотел бы узнать.
Я даже не берусь предположить. Потому что есть понятие «репрезентативность», а я сознательно собираю тех людей, которые хотя бы интересуются математикой. Моя выборка не репрезентативная.

Только мысленный эксперимент. И мне интересны мнения других людей о возможных результатах такого мысленного эксперимента.
Эксперимент, мнение об эксперименте, мнение о мнении об эксперименте… :) Это как раз случай, когда нужно проводить реальный эксперимент. Психология — не физика.

Зато у меня есть идея, как изменить общество. Учить только тех, кто хочет и может учиться. И тогда доля людей, которые поймут условие задачи, станет ещё меньше. :/

2 лишних выстрела

Размещая задачу в сети я уже решил ее, точно так же, как и вы. А вчера понял, что есть решение на 1 выстрел короче.

В конце первого прохода стрелять в 1000-ный вагон бессмысленно - крысы не может там быть, так как только что без толку стрельнули в 999-ый вагон. Поэтому уже после 998 выстрела ясно, что первоначальное предположение о крысе в четном вагоне ложно. Тогда в начале крыса, очевидно, была в нечетном вагоне, и после 998-ого выстрела в вагон с номером 999 она тоже находится в нечетном вагоне! Максимальный номер вагона (обязательно нечетный!), где она может быть после 998-ого выстрела в 999-ый вагон - это 999-ый. Повторно стреляем в него и далее после каждого неудачного выстрела смещаемся на 1 влево, при этом легко видеть, что живая крыса всегда может быть только левее выстрела. Когда, двигаясь влево, мы стрельнем в вагон 2, это будет выстрел номер 1996, после которого крыса снова будет в нечетном вагоне (в первом). Поэтому последним выстрелом (номер 1997) в первый вагон крыса обязательно будет убита, если осталась в живых до сих пор.

UPD.

На самом деле, последний выстрел номер 1997 не потребуется.Поскольку крыса осталась жива после конца первого прохода (то есть после выстрела № 998, мы знаем что в самом начале она была в нечетном вагоне. После выстрела № 1995 (в третий вагон при обратном проходе) сделано нечетное число выстрелов, следовательно крыса теперь сменила четность вагона и находится в четном вагоне. Но в этот момент остался только один четный вагон, в котором она может находиться - второй. Делаем в этот второй вагон последний выстрел номер 1996 - крыса убита, если оставалась живой до этого момента. (Улучшение решения с 1997 до 1996 выстрелов подсказал мне сын, я только записал).

Хотелось бы знать Ваше мнение - не просмотрел ли я чего.

Edited at 2010-12-09 09:06 pm (UTC)

Re: 2 лишних выстрела

Да, все верно. До 1997 у меня в коментариях уже упростили. И до 1996 тоже вроде бы верно.

Алгоритм неверный:

Этап 1: Предполагаем, что изначально крыса в вагоне с четным номером, начинаем травить.
стреляем в вагон 2 - крыса или убита, или в вагоне 3, или больше - вагоны 1,2 свободны от крысы.

>> до выстрела крыса была в 3 вагоне,
>> после выстрела переползла во 2 вагон

стреляем в вагон 3 - крыса или в вагоне 4, или дальше. .... - это не так, крыса во 2 вагоне

Автор какбы упускает из виду, что крыса перемещается между выстрелами

Т.о. доказать не могу, но чувствую что 100% алгоритма нет

Число 3 - нечетное. Значит после 999 выстрелов она будет в чётном вагоне, и на втором проходе точно попадётся.

А может, просто - два раза в первый, два раза во второй, и так до 999-го?

крыса убежит.

http://leonid-b.livejournal.com/756587.html?thread=16163179#t16163179

Здесь описано как именно.


задача тоже

Имеются две комнаты. В одной три лампочки накаливания,а в другой три кнопки,каждая из которых зажигает одну из лампочек.
Вопрос: КАК можно узнать какая из кнопок включает какую лампочку,если в каждую из комнат можно зайти только один раз?

Re: задача тоже

Неясности в условии:

1. Известно ли начальное состояние лампочек?
2. Сказано, что кнопка зажигает лампочку. А как ее погасить? Возможно несколько вариантов:

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

Как только эти неясности будут устранены - думаю, что решение предложу сразу.

Edited at 2010-11-29 05:08 pm (UTC)

Re: задача тоже

ok, уточняю.
1.Начальное состояние лампочек - все выключены.
2.Кнопка работает,как обыкновенный выключатель - одним нажатием включается и таким же нажатием выключается. Никакого дополнительного пульта нет. Чётность или нечётность нажатий значения не имеет.

Можете считать меня занудой

В Вашем втором пункте три фразы. Первая содержит, на мой взгляд, неточность. Вместо слова "включается" следовало бы написать "включает лампочку", а вместо слова "выключается" - "выключает лампочку". Именно так используется глагол включать в Вашей первоначальной формулировке, только там в одном случае используется именно этот глагол, а в другом - глагол "зажигать" в форме "зажигает". Ни в одном из случаев нет возвратной формы, которую Вы почему-то использовали в своем последнем посте. Все-таки кнопка именно включает лампочку, а не включается сама!

Но если исправить эти две неточности, то конец первой фразы Вашего третьего пункта будет звучать так: "одним нажатием включает лампочку и таким же нажатием выключает ее." Однако это противоречит третьей фразе Вашего второго пункта, так как получается, что как раз нечетные нажатия на кнопку включают ламопчку, а четные - выключают.

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

Re: Можете считать меня занудой

Да,не особенный Вы и зануда ))) почти со всеми замечаниями можно согласиться.
Сейчас и я начну "знудеть" тоже )))
Вы отдалили решение выше изложенной задачи примерно на 4 мин. Лампочка нагревается меньше ,чем за 30 секунд.И столько же требуется,чтобы неспеша зайти в другую комнату.
Эта задача мною была обнаружена на нескольких ресурсах. И везде говорится про пять минут. А мне в своё время эти "пять минут" стоили понижения оценки не 1 балл при поступлении в ВУЗ.
А в целом,конечно,задачу Вы решили правильно.
И по сравнению с тем преподом Вы просто Ангел)))
Спасибо.

Усложним задачу - пусть вагоны замкнуты в кольцо.

не интересно

Задача с таким изменением условия решения не имеет. Доказательство:

Если решение существует, то это означает, что даже если крысе известно, в какой последовательности обстреливаются вагоны, она не может остаться в живых, не нарушив правила об обязательном переходе в соседний вагон после каждого выстрела. В исходной задаче крыса убивается либо 998-ым либо 1998-ым выстрелом. Дольше крыса прожить не может. Перед фатальным выстрелом она в тупиковом вагоне, например, тысячном, и даже зная, что следующий выстрел будет в вагон 999, вынуждена туда идти и умереть.

Но в случае закольцованных вагонов, у крысы всегда будет два варианта перехода - поэтому, если она знает или угадает, куда будет следующий выстрел, она пойдет в другую сторону.

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

  • 1
?

Log in

No account? Create an account