Цитата PETIKANTROP () Переделана мною классическая задача. На одном из форумов она выложена, но пока никто не справился))
Есть N картонных коробок, стоящих вплотную друг к другу в один ряд. В одной из них суперпозиционная мышь, прогрызшая себе ходы из каждой коробки в соседние. Из крайних коробок прохода наружу нет. Охотнику дали ружье и неограниченное количество патронов, чтобы убить клонирующуюся мышь при следующих условиях: 1) изначально охотник не знает, в какой коробке сидит мышь; 2) если охотник выстрелил в коробку, где сидит мышь, то мышь считается убитой (на её клоны это не распространяется); 3) если охотник выстрелил в какую-либо коробку,то после выстрела мышь ( не убитая , см. п.2) материализуется в двух соседних коробках, но так, что в одной коробке более одной мыши находиться не может. Сколько выстрелов понадобится охотнику, чтобы гарантированно убить мышь?
Опять убить мышь. Так мышь убить надо или всех грызунов. Я скоро не в коробки,а в Вас буду стрелять если Вы с условиями не определитесь
сделав 11 выстрелов в 10-ю коробку, я однозначно могу заявить, что мышь убита, т.к где бы она не находилась изначально, 10 выстрелов будет достаточно, чтобы мышь попала в 10-ю коробку, а 11-ым выстрелом она будет убита.
1)6 выстрелов в 5ю корбку. Если мышь находилась в коробках 1-10 то: 1 2 1 3 2 4 1 3 5
10 9 11 8 10 12 7 9 11 13 6 8 10 12 14 5 7 9 11 13 15 Мышь убита. 2)Если мышь находилась в корбках с 11 по 20, то сделав еще 2 выстрела в 15 коробку, мы ее убьем. Доказывать или включите индукцию? 6+2=8<11
Сообщение отредактировал никник - Вс, 04.10.15, 00:36
Kreativshik,да там скорее всего оптимальная формула что то вроде х^x=N или х^2=N, х = кол-во выстрелов. Для нечетного ряда, +1. И округления в меньшую сторону. Мне сегодня не думается.Я пас. Думаю, решать задачу автора, надо вот по этому описанию автора: Охотник не знает результат отдельного выстрела, попал или не попал. Сразу после {холостого} выстрела мышь удваивается (видимо с испугу)и перемещается в две соседние {c ней коробки}, но больше одной в коробке мышей не бывает. Например, охотник стреляет в 400ю коробку, мышь сидела в 200ой. После выстрела она появляется в 199 и в 201 коробке. Далее охотник бомбанул по 300ой, к примеру, мыши расплодились в 198ю, 200 и 202ю. В 200 должно, по идее, появится 2 мышки, но одна исчезает ( выживает только одна тварюга). И т.д. Охотник должен действовать обдуманно и наверняка.{Из крайней коробки мышь перемещается только на 1 внутреннюю соседнюю позицию. Сколько выстрелов надо чтоб гарантировано убить всех мышей? }
Сообщение отредактировал никник - Вс, 04.10.15, 06:32
PETIKANTROP, насколько я понял Ваше условие, ответ: при N=3, мы гарантированно убиваем всех мышей 2я выстрелами, в остальных случаях N выстрелами. Доказывать муторно, но одну из возможных дорожек вижу в том, что каково бы ни было N, мы почти* всегда можем разработать стратегию при которой N/k (где k -любое целое число, но удобней всего, наверное, брать 2)выстрелами отсеиваем всех клонов N/k возможных размещений изначальной мыши, с локализацией оставшихся возможных клонов на известном нам участке длиной N-N/k. С нижней границей, думаю, и так понятно, почему она может быть меньше N только при N=3. *Почти заключается в том, что простые числа на 1/k не разобьешь, чтобы получить целое.Я уверен, что обойти эту загвоздочку можно, но не охота тратить уйму времени из-за максимум еще одного выстрела для некоторых N.) п.с. Прекрасная задачка, хоть и не очень внятно сформулированная.
Сообщение отредактировал никник - Пн, 05.10.15, 04:31
медальку Вам подарю.
