Есть N картонных коробок, стоящих вплотную друг к другу в один ряд. В одной из них сидела мышь и прогрызла себе ходы из каждой коробки в соседние. Из крайних коробок прохода наружу она не прогрызла.
Охотнику дали ружье и неограниченное количество патронов, чтобы убить мышь при следующих условиях:
1) изначально охотник не знает, в какой коробке сидит мышь.
2) если охотник выстрелил в коробку, где сидит мышь, то мышь считается убитой
3) если охотник выстрелил в коробку, где нет мыши, то после выстрела мышь обязательно переходит в любую коробку соседнюю к той, в которой она сидела в момент выстрела. И сидит там пока не грянет следующий выстрел.
Сможет ли охотник гарантированно застрелить мышь? Если да, то за какое наименьшее количество выстрелов?
buka
Гений
 Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
 |
� Ответ #30 : Март 25, 2010, 21:39:08 � |
|
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3. 2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ... N-1 (для начала)  N=3 является исключением  |
|
|
|
|
Записан
|
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #31 : Март 25, 2010, 21:46:56 � |
|
Пожалейте мышку
|
|
|
|
|
Записан
|
Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
|
|
|
Miki
Гений
Offline
Сообщений: 827
СПАСИБО
-вы поблагодарили: 21
-вас поблагодарили: 49
|
|
� Ответ #32 : Март 25, 2010, 21:54:40 � |
|
а может эта мышка из фильма Мышиная охота,тогда хрен убьете!
|
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #33 : Март 25, 2010, 21:57:55 � |
|
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3. 2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ... N-1 (для начала) Смит, так эта формула для наихудшего развития событий. А ты представил не самый худший вариант, тем более с таким большим N Допустим, мы знаем чётность норки мышки в начальный момент.
Тогда за N (или N-1) ходов мы её убьём, начиная последовательно стрелять с минимального соответствующего номера. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
|
� Ответ #34 : Март 25, 2010, 23:03:43 � |
|
Если число норок N нечётно - то 2*N -1, если чётно, то 2*(N-1)
ок. N=3. 2 выстрела: 2-й ящик и снова 2-й ящик. тыдыщщщ... N-1 (для начала) Смит, так эта формула для наихудшего развития событий. А ты представил не самый худший вариант, тем более с таким большим N Допустим, мы знаем чётность норки мышки в начальный момент.
Тогда за N (или N-1) ходов мы её убьём, начиная последовательно стрелять с минимального соответствующего номера. Илюха, а при n=4 как ты думаешь - работает? |
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #35 : Март 25, 2010, 23:13:50 � |
|
Илюха, а при n=4 как ты думаешь - работает? Да, работает и формула как раз 2N-1. Допустим мышка во 2-ой, начинаем с 1-2-3-4-4-3-2 мышка гарантированно убита Так как 2-1-2-1-2-1-2-1-2 - ходы мышки. В других случаях она умрет еще раньше.  Ой, количество коробок четно, а формула 2n-1 Не порядок. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #36 : Март 25, 2010, 23:14:03 � |
|
Дополнения. 1. N=4 тоже исключение. Достаточно 4 выстрелов. 2. Для чётного N требуется в худшем случае 2*N-3 а не 2*(N-1), т.е. на один меньше. 3. Для нечётного N требуется тоже 2*N-3 а не 2*N-1, т.е. на два меньше. Почему на один/два меньше - могу объяснить, но попытайтесь догадаться сами |
|
|
|
� Последнее редактирование: Март 25, 2010, 23:24:57 от buka �
|
Записан
|
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
|
� Ответ #37 : Март 25, 2010, 23:25:55 � |
|
1. N=4 тоже исключение. Достаточно 4 выстрелов.
возможно) какая стратегия при этом? |
|
|
|
|
Записан
|
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
|
� Ответ #38 : Март 25, 2010, 23:26:06 � |
|
|
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #39 : Март 25, 2010, 23:29:54 � |
|
1. N=4 тоже исключение. Достаточно 4 выстрелов.
возможно) какая стратегия при этом? Четырех выстрелов маловато будет, чтобы гарантированно убить мышь. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #40 : Март 25, 2010, 23:34:19 � |
|
Но там изложена не оптимальная стратегия В оптимальной стратегии требуется 2*N-3 шага. |
|
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #41 : Март 25, 2010, 23:42:14 � |
|
1. N=4 тоже исключение. Достаточно 4 выстрелов.
возможно) какая стратегия при этом? Четырех выстрелов маловато будет, чтобы гарантированно убить мышь. Оппс! Пардон, ошибся. 4 - не исключение. Кроме того - для нечётных N требуется всё-таки 2*N-1, а для чётных N - 2*(N-2). С 2*N-3 я ошибся  |
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #42 : Март 25, 2010, 23:45:22 � |
|
Ребята ответ на вопрос: сколько потребуется минимум выстрелов, чтобы гарантированно убить мышь при N коробках? Уже дан: 2N-1. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #43 : Март 25, 2010, 23:48:00 � |
|
Ребята ответ на вопрос: сколько потребуется минимум выстрелов, чтобы гарантированно убить мышь при N коробках? Уже дан: 2N-1. Это в случае нечётного N. В случае чётного - 2*(N-1) = 2*N-2 |
|
|
|
|
Записан
|
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
|
� Ответ #44 : Март 25, 2010, 23:49:38 � |
|
Но там изложена не оптимальная стратегия В оптимальной стратегии требуется 2*N-3 шага. до сегодняшнего дня я представлял 2n+1 или 2n в зависимости от четности, но теперь что-то не совсем уверен  |
|
|
|
|
Записан
|
|
|
|
|
