?

Log in

No account? Create an account
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