суббота, 5 мая 2012 г.

Как нужно играть начинающему?

Играют двое. Игровое поле - полоска бумаги, разделенная на 8 клеток. В клетках 4, 6 и 8 помещены шашки. Играющие поочередно передвигают произвольно выбранную шашку из данных трех на любую клетку в направлении, указанном стрелкой. Шашка может быть передвинута и через другую шашку и поставлена на клетку, занятую другой шашкой. Выигрывает тот, кто последним поставит шашку на клетку 1. Как должен играть начинающий игрок, чтобы обеспечить себе победу?
Игра
update
Первым нашел стратегию Илья.
Ответ
Решение в комментариях.
Игра со спичками.

9 комментариев:

  1. Если я не ошибаюсь, то начинающий игрок первым ходом должен сдвинуть любую фишку на одну клетку.

    Hint: неплохо замаскированная очень известная игра. )

    ОтветитьУдалить
    Ответы
    1. У меня нет ответа на эту головоломку, поэтому желательно подробное решение.

      Удалить
    2. В ходе игры нужно сдвинуть все фишки на клетку 1. При этом в общей сложности первую нужно сдвинуть на 3, вторую на 5, а третью - на 7 клеток.

      Можно рассматривать фишки как числа (изначально - 3, 5 и 7), которые каждый ход можно уменьшать на произвольную целую величину, но не дальше чем до нуля и только одну за ход.
      Или можно интерпретировать так: есть три кучки камней (по 3, 5 и 7 соответственно), и за один ход можно забрать произвольное число камней, но только из одной кучки. Выигрывает тот, кто заберет последний камень. Или так: проигрывает тот, кто не сможет сделать очередной ход.

      Эта известная игра называется "Ним". Выигрышная стратегия известна; правда, честно говоря, сомневаюсь, что сам бы до неё когда-нибудь додумался, если бы не прочитал.

      Идея стратегии следующая. Представим все исходные числа (3, 5 и 7) в двоичном виде. Произведем в каждом разряде проверку на четность, или говоря по-другому, произведем побитовое сложение:

      011
      101
      111
      ---
      001

      Набор чисел назовём "нечетным", если в результате получается 1 хотя бы в одном разряде, в противном случае будем называть его "четным". Заметим, что из четного любым ходом можно сделать только нечётный, а из нечётного всегда подходящим ходом можно сделать чётный. Обратив внимание на тот факт, что конечный набор (0, 0, 0) - чётный, получаем следующую стратегию для первого игрока: всегда сводить своим ходом набор чисел к "чётному". Противник сможет своим ходом добиться только нечётного набора, а следовательно, никогда не сможет победить.
      Ну то, что игра конечная, очевидно. )

      Удалить
    3. Да, непростая задача. Спасибо за подробный ответ.

      Удалить
    4. что-то я запутался, как в этой стратегии учитывается то, что можно перепрыгнуть через шашку или поставить шашку в ту же клетку с другой?
      так, например, если первым ходом игрок двигает шашку с 8 на 7, то у второго игрока появляются варианты: перепрыгнуть шашкой с 7 на 5, или поставить с 7 на 6. у получившихся позиций разная же четность будет?

      Удалить
    5. Тот факт, что можно перепрыгнуть через шашку или поставить с другой на ту же клетку, можно интерпретировать следующим образом: шашки друг другу не мешают, не конфликтуют. Можно считать, что каждая шашка двигается по своей индивидуальной полосе.

      Пусть первый двинет шашку с 8 на 7, т.е. остаются числа 3, 5, 6.

      011
      101
      110
      ----
      000

      Позиция четная.
      Если второй сдвинет эту фишку на 5, то получатся числа 4,5,3:

      100
      101
      011
      ---
      010

      Нечетная позиция.

      Если же сдвинет на 6, то:

      101
      101
      010
      ---
      010

      Опять позиция нечетная.

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

      Меня лично хватило лишь, чтобы определить, что все остальные ходы (4 -> 1, 4 -> 2, 6 -> 1, 6 -> 2, 6 -> 3, 8 -> 1, 8 -> 2, 8 -> 3, 8 -> 5 ) ведут к проигрышу первого :-) Точнее, дают возможность второму перехватить инициативу. Да, жесткая задача. Без восьми пядей во лбу ее не решить, еще же доказывать надо, что из четной позиции можно прийти только к нечетной. А из нечетной - как к четной, так и нечетной. :-)

      Удалить
  2. То, что из четной можно получить только нечетную, доказывается просто. Действительно, при каждом ходу мы одно из чисел уменьшаем, а следовательно, по крайней мере в одном из его двоичных разрядов произойдет изменение (0 на 1 или 1 на 0), значит в этом разряде чётность также изменится (были в сумме везде нули, а станет по крайней мере в одном из разрядов не ноль).

    Доказательство того факта, что из нечётной всегда можно прийти к чётной - немного сложнее. :) Но я верю, вы справитесь. :)

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

    ОтветитьУдалить
    Ответы
    1. --Доказательство того факта, что из нечётной всегда можно прийти к чётной - немного сложнее. :) Но я верю, вы справитесь. :)--

      Вера творит чудеса! :-)
      Доказательство сего может быть примерно таким:
      Для наглядности возьмем любой нечетный набор, например:
      1101111
      0111011
      1010101
      0110011
      0010111
      -------
      0100101 - сумма

      Ищем в сумме единицу в наивысшем разряде (самую левую проще говоря). У нас она на втором месте. Выбираем любое из слагаемых с единицей на этом же месте - очевидно, что как минимум одно такое слагаемое будет существовать. Возьмем, например, 0110011. В этом числе меняем 1 на 0 и 0 на 1 в разрядах, соответствующим единицам суммы 0100101. Получится 0010110. В итоге гарантированно получаем меньшее число (так как мы поменяли единицу старшего разряда на 0), и итоговый набор будет четным.
      Такие манипуляции можно провести для любого нечетного набора - поэтому из любого нечетного набора можно как минимум одним способом получить четный. Та-да!!!

      Удалить