Выживет ли мышь?

[buka]

Пожалуйста.
Показать скрытый текст

Допустим N нечётное число.
Стратегия следующая.
1. Предполагаем, что вначале мышка в чётной норке, т.е. во 2-й, 4-й, 6-й,...,N-1.
1.1 Стреляем во 2-ю. Либо убили, либо, если мышка была в 4-й, 6-й,...,N-1, то она переместится в 3-ю, 5-ю, 7-ю,...,N-2, N.
1.2 Стреляем в 3-ю. Либо убили, либо, если мышка была в 5-й, 7-й,...,N-2, N, то она переместится в 4-ю, 6-ю,...,N-1.
1.3 Стреляем в 4-ю. Либо убили, либо, если мышка была в 6-й, 8-й...,N-1, то она переместится в 5-ю, 7-ю,...,N-2, N.
...
1.N-3 Стреляем в N-2. Либо убили, либо мышка была в N и переместилась в N-1
1.N-2 Стреляем в N-1. (N-1, заметим, чётная)  При предположении, что вначале мышка в чётной норке мы должны её убить. Если этого не произошло, значит вначале мышка была в нечётной норке и сейчас, следовательно, тоже в нечётной норке. И это значит что она сейчас, на N-2 шагу переместилась в чётную и мы опять начнём со 2-й норки. Но на сей раз мы точно знаем, что она - в чётной норке.
Первый проход состоял из N-2 шагов.
Второй проход также будет состоять из N-2 шагов. Итого - 2*N-4 шага при N нечётном.
2.Допустим N чётное число.
Стратегия следующая.
Предполагаем, что вначале мышка в чётной норке, т.е. во 2-й, 4-й, 6-й,...,N.
2.1 Стреляем во 2-ю. Либо убили, либо, если мышка была в 4-й, 6-й,...,N, то она переместится в 3-ю, 5-ю, 7-ю,...,N-3, N-1.
2.2 Стреляем в 3-ю. Либо убили, либо, если мышка была в 5-й, 7-й,...,N-3, N-1, то она переместится в 4-ю, 6-ю,...,N-2, N.
2.3 Стреляем в 4-ю. Либо убили, либо, если мышка была в 6-й, 8-й...,N-1, то она переместится в 5-ю, 7-ю,...,N-3, N-1.
...
2.N-3 Стреляем в N-2. Либо убили, либо мышка была в N и переместилась в N-1
2.N-2 Стреляем в N-1. (N-1, заметим, нечётная)  При предположении, что вначале мышка в чётной норке мы должны её убить. Если этого не произошло, значит вначале мышка была в чётной норке и сейчас, следовательно, тоже в чётной норке. И это значит что она сейчас, на N-2 шагу переместилась в нечётную и мы начнём с 1-й норки. Но на сей раз мы точно знаем, что она - в нечётной норке.
Второй проход у нас потребует на 1 шаг больше, т.е N-1.
Итого: N-2 + N-1 = 2*N - 3.

[Илья]

Не, просто в формулу 2N-1 входят все случаи. Можно конечно убить мышь и за меньшее число ходов, но не во всех случаях. А чтобы гарантированно убить мышь при любом N нам надо 2N-1, в которую входит и 2N-3, и 2N-2 и т. д. Но при наихучшем варианте развития событий мы точно убьем мышку за 2N-1, больше выстрелов точно не понадобиться. Меньше? Возможно, но точно не больше. Так что на все вопросы задачи ответ есть. Возможно убить мышку при заданных услових? Ответ: Да, возможно. За сколько ходов: за 2N-1. Ни 2N-2. ни 2N-3 не дает этой универсальности, так как при других N формула 2N-3  уже не будет работать. А нам надо, чтобы работала при любых N. А при любых N работает только 2N-1.

[Smith]

А при любых N работает только 2N-1.

Илья, 2N-3 работает для всех случаев, для которых работает 2N-1, однако, очевидно, "минимальнее"

[Илья]

Илья, 2N-3 работает для всех случаев, для которых работает 2N-1, однако, очевидно, "минимальнее"

Смит, допустим у нас 10 коробок, мышка в одной из них. Уложишься в 17 выстрелов? Твоя стратегия?

[Илья]

Стреляем в N-1. (N-1, заметим, чётная)  При предположении, что вначале мышка в чётной норке мы должны её убить. Если этого не произошло, значит вначале мышка была в нечётной норке и сейчас, следовательно, тоже в нечётной норке. И это значит что она сейчас, на N-2 шагу переместилась в чётную и мы опять начнём со 2-й норки. Но на сей раз мы точно знаем, что она - в чётной норке.

Последнее предложение в этом отрывке не совсем понятно. Откуда нам будет это известно?
Предлагаю частный случай в 9 норок, попробуем испытать вашу стратегию.
По стратегии мы должны начинать со 2-ой норки, а мышка пусть у нас будет сидеть в первой. Поехали:
2-3-4-5-6-7-8-9
Ход мышки: 1-2-3-4-5-6-7-8 и когда был произведен выстрел по 9-ой мышка в нее перебегает.
Второй проход по вашей стратегии выглядит так:
2-3-4-5-6-7-8-9
Ход мышки: 9-8-9-8-9-8-9-8 и после 8-го выстрела мышка опять перебегает в 9-ую. Ба!!
Как так?! Мышка оказалась жива

[Smith]

Илья, 2N-3 работает для всех случаев, для которых работает 2N-1, однако, очевидно, "минимальнее"

Смит, допустим у нас 10 коробок, мышка в одной из них. Уложишся в 17 выстрелов? Твоя стратегия?

да. стратегию описал buka, это именно то, что я имею ввиду. 17 выстрелов для 10 коробок.

[Илья]

да. стратегию описал buka, это именно то, что я имею ввиду. 17 выстрелов для 10 коробок.

Так начинай стрелять.
Попробуем помочь мышке.

[Smith]

Илья, я с удовольствием, только через часик, если можно

[Илья]

Окей.

[Андрей56рус]

Мыш умрет гдето посте 3-4 выстрела.Охотник стрельнит в первую коробку и прислушается куда и в какую сторону побежала мышь!Но может и с первой попытки)если сначало стукнет по коробке или ещё что нибудь сделает с ней!Мышь побежит он услышит и если не дурак)))))поймёт в какую коробку она убежала!

[Илья]

 

[Smith]

Мыш умрет гдето посте 3-4 выстрела.

..от разрыва сердца

зы: бедный. бедный Йорик

[Илья]

Так у мышки оказывается и имя имеется. Чувствую - быть задачке легендарной.

[Smith]

2Илья:
если мне везет, то мышь в четной, и мои ходы 2,3,4,5,6,7,8,9 - хлоп! есть)
но мне (как обычно, блин!) не везет, и мои дальнейшие ходы: 2,3,4,5,6,7,8,9,10 - хлоп! привет, мышь!!
итого: 8+9=17 

[Lkob]

2Илья:
если мне везет, то мышь в четной, и мои ходы 2,3,4,5,6,7,8,9 - хлоп! есть)
но мне (как обычно, блин!) не везет, и мои дальнейшие ходы: 1,2,3,4,5,6,7,8,9 - хлоп! привет, мышь!!
итого: 8+9=17 

 Если я правильно понял, то это звучит так: "Если мне повезло, то прийдется поступать так, если не повезло, значит поступать по-другому. Сумма этих двух - решение". Либо же я недопонимаю?