среда, 16 января 2013 г.

Конфеты

Конфеты
Илья, участник нашего клуба, предлагает решить следующую задачу.
Двое сладкоежек играют в следующую игру. Перед ними три кучки конфет, в которых 100, 300 и 500 конфет соответственно. Каждый игрок в свой ход делает последовательно две операции: 1) съедает полностью одну из кучек по своему выбору; 2) выбирает одну из оставшихся и произвольным образом делит ее на две новые кучки так, чтобы в каждой новой кучке оказалось как минимум одна конфета (таким образом, делить кучку из одной конфеты уже нельзя, нужно выбрать другую). Проигрывает тот, кто не сможет сделать ход (т.е. когда в каждой кучке останется по одной конфете). Кто выигрывает при правильной игре, первый или второй, и какова выигрышная стратегия?

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

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

    ОтветитьУдалить
    Ответы
    1. Четного количества кучек оставить не получится, потому что после каждого хода остается опять три кучки.

      Удалить
    2. ?
      perviy igrok vsegda ostavlyaet chetnoe.
      bilo 3 sel odnu stalo 2.
      razdelil odnu stalo 4.

      esli k nemu vozrashaetsya 1 kucha on ee sedaet v ostalnom emu vse ravno on prodolzhaet libo est libo delit'

      Удалить
    3. Игрок не выбирает, какую из двух операций совершить. Он выполняет обе, сначала первую, потом вторую.

      Таким образом, сначала съедает кучку (остается две), потом делит одну из оставшихся (остается опять три).

      Удалить
  2. Выигрывает первый. Выигрышная стратегия: съедает за первый ход 500 конфет, а дальше неважно - он уже съел явно больше, чем сможет съесть второй :-)))

    ОтветитьУдалить
    Ответы
    1. Максимизировать число съеденных конфет в такой игре - это отдельная задача, хотя и совсем несложная. :)

      Удалить
  3. Кучек все время 3 (меняется только количественный состав), так что задача не сильно усложнена, главное наметить этапы.

    Лемма.
    Если игроку на его ходу попадается набор N-1-1, то он проигрывает, если N нечетное, и выигрывает, если N четное (заставляя своего соперника играть при (N-1)-1-1).
    Очевидно, что если мы докажем для нечетных N, то для четных доказательство следует напрямую.
    N=1 - проигрыш по условию.
    N=3 - единственный допустимый ход - съесть одну конфету из одинарной кучки, и разделить тройную на 2+1. Тогда сопернику достается набор 2-1-1, который, понятно, выигрывает.

    N>=5 - результат его хода (он ест только одинарную, и делит большую кучку) можно в любом случае записать, как A-B-1. Здесь A+B=N, и одно из этих чисел обязательно нечетное, а другое - четное (для определенности, пусть A четное). Тогда соперник ест "нечетную" кучку, а "четную" делит на две (A-1) и 1, выдавая сопернику набор (A-1)-1-1, где A-1 - нечетно (!). Так как A-1<N, то по индукции понятно, то мы можем прийти к 1-1-1, рано или поздно.
    Это и доказывает Лемму.

    Следствие 1. Любой набор вида (2n)-X-1, где n, X - любые натуральные, выигрышный для текущего игрока: съев X, можно привести кучки к виду (2n-1)-1-1, отчего соперник проигрывает по Лемме.

    Следствие 2. Набор вида X-Y-1, где X, Y - нечетные больше 1, проигрышный.
    Если съесть X или Y, то потом надо вынужденно делить вторую большую кучку на четную и нечетную части, приводя к выигрышному условию для соперника (см. Сл. 1).
    Если съесть кучку из одной конфеты, то четность результирующих кучек в любом случае будет Н-Н-Ч, и соперник, съев одну из нечетных, откладывает из четной одну конфету, возвращая набор к условию Сл. 2 до тех пор, пока X или Y не станет равным единице, а это проигрыш по Лемме.

    Следствие 3. Любой набор Н-Н-Ч - выигрышный (см. Сл. 2).
    Следствие 4. Любой набор Н-Ч-Ч - выигрышный. Достаточно съесть одну из четных кучек, а из другой отложить одну конфету.
    Следствие 5. Любой набор Н-Н-Н - проигрышный. В любом случае (кроме 1-1-1, который проигрышный по определению), после хода, получится набор Н-Н-Ч, который выигрышный для соперника.

    Случай набора Ч-Ч-Ч надо рассмотреть отдельно.

    ОтветитьУдалить
    Ответы
    1. Итак, Ч-Ч-Ч.
      Если игроку попадается этот набор, то на следующем ходу он получит либо Ч-Н-Н, дав сопернику выиграть, либо Ч-Ч-Ч, оставляя неопределенность.

      Видно, что 2-2-2 - проигрышный набор, тогда как 4-2-2 - выигрышный, т.к. сводится к первому. (Да и вообще, любой набор X-4-2 - выигрышный)
      Соответственно, 6-2-2 - проигрышный (лучший ход приводит к 4-2-2 и победе соперника), 8-2-2 - выигрышный...
      И, если присмотреться, то Лемма работает и тут, надо только удвоить все числа в ней.

      Но дальше начинаются сложности, которые обойти не удалось пока.

      Удалить
    2. Начало верное, я сам также анализировал. И тоже столкнулся с определенными сложностями на этом этапе. :)

      Удалить
  4. Второй выигрывает

    П.1. Набор ЧЧЧ превращается или в ННЧ, или в ЧЧЧ (кроме 2-2-2, конечно)
    П.2. Набор ННЧ всегда можно превратить в ННН
    П.3. Набор ННН можно превратить только в ННЧ


    Чтобы выиграть, игроки должны стремиться подставить сопернику набор ННН, так как 1-1-1 есть ННН.
    Итак, у нас вначале 100-300-500 ЧЧЧ.
    Если игрок 1 превращает его в ННЧ, тогда игрок 2 ННЧ превращает в ННН, игрок 1 сможет его превратить только в ННЧ, игрок 2 опять в ННН, что ведет к триумфальной победе игрока №2.
    Т.е. чтобы выиграть, игрок 1 должен сделать ЧЧЧ->ЧЧЧ и стремится подставить сопернику ситуацию 2-2-2. Игрок 2, естественно,тоже.
    Кто уклонится от этой тактики - лузер.
    Поэтому господа игроки будут оперировать парами конфет. Образно говоря, пара конфет у нас сливается в одну, и задача мутирует в следующую:
    "Вначале у нас 50-150-250 конфет - бла-бла-бла ... проигрывает тот, кто не сможет сделать ход"

    У нас опять вначале ЧЧЧ, поэтому абсолютно такими же соображениями приходим к выводу, что игроки должны оперировать изначально четверками конфет и стремиться подставить сопернику 4-4-4.
    Кто не захочет так играться, проиграет.
    Т.е.Задача мутирует в такую:
    "Вначале у нас 25-75-125 конфет ... проигрывает тот, кто не сможет сделать ход".
    А это уже интересно, так как имеем вначале ННН, а это НЕВЫГОДНО для игрока, начинающего игру, так как соперник сможет постоянно подставлять ему набор ННН.

    Поэтому выигрывает всегда второй игрок.

    Выигрышная стратегия: сначала играем четверками, второй игрок всегда подставляет набор ННН относительно четверок. Когда игрок 1 "разобьет" четверку, подставляем ему набор ННН относительно двоек, когда он "разобьет" двойку, подставляем ему обычный набор ННН.

    ОтветитьУдалить
    Ответы
    1. Все верно. :)

      Проигрышные позиции в этой игре - такие, когда все числа имеют одинаковую кратность двойки в разложении на простые множители.

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


      Теперь нужно разобраться, а что будет в игре с четырьмя кучками. :)

      Удалить
    2. 2 кучи
      Ага. Потому что с ЧЧ можно за один ход сделать НН, а с ЧЧЧ сделать ННН никак низзя :-)

      4 кучи
      Да примерно то же самое, что и с тремя.
      НННН можна подставить сопернику с наборов типа ННЧЧ или НННЧ, и уже вести его до победы. Например, набор 100-300-500-900 есть НННН относительно четверок, он невыгоден для первого. А набор 101-101-100-100 есть ННЧЧ относительно единиц - для первого выигрышный... Вообщем, кто желает, может расписать детальнее.

      Удалить
    3. Да, с четырьмя не особо сложнее, действительно. Поскольку из ЧЧЧЧ можно сделать только ЧЧЧЧ или ЧЧНН, то с наборами вида ЧЧЧЧ все понятно.
      А ЧЧЧН превращается либо в ЧЧЧЧ, либо в ЧЧЧН, либо в ЧЧНН или ЧННН (последние два варианта сразу ведут к проигрышу, естественно)... Тут немного повозиться нужно, чтобы корректно все описать все проигрышные позиции вида ЧЧЧН, но в целом - да, что-то получится. :)

      Удалить