Ayao "Alqualos" Kuroyuki (ayao) wrote,
Ayao "Alqualos" Kuroyuki
ayao

Задача о камнях

Нашёл себе занятие! Задача о камнях. Есть два игрока и две кучи камней, в одной их n1 штук, в другой - n2. Хотя бы одно из n1 или n2 не равно нулю (т. е. есть хотя бы один камень в одной из куч). Каждый игрок может за один ход взять любое количество камней из первой кучи либо любое из второй, либо из обеих куч, но одинаковое количество. Кто берёт последним, проигрывает. Задача - написать функцию, которая бы для заданных n1 и n2 находила бы ход, ведущий к победе, либо давала ответ, что ситуация проигрышная. Проигрышная ситуация - это такая ситуация, в которой противник может подобрать ходы так, что его невозможно будет обыграть.

Тривиальная проигрышная ситуация: (0, 1). Один камень в одной куче и ничего не остаётся, кроме как его взять. Менее тривиальная - (2, 2). Варианты ходов из неё:

Можно взять (1, 0), останется (1, 2). Противник берёт (0, 2) - мы оказываемся в проигрышной (1, 0).
Можно взять (1, 1), останется (1, 1). Противник берёт (0, 1) или (1, 0) - мы оказываемся в проигрышной (1, 0) или (0, 1).
Можно взять (2, 2) и проиграть тут же ^_^
Можно взять (0, 1) - будет аналогично (1, 0).
Можно взять (0, 2), останется (2, 0). Противник берёт (1, 0) и ставит нас в (1, 0).
Аналогично (2, 0).

Вообще в этой игре все ситуации симметричны, так как первая куча ничем не отличается от второй. Так что если мы знаем ответ для (n1, n2), то для (n2, n1) он будет аналогичный.

Далее. Если мы возьмём любую проигрышную ситуацию (n1, n2) и прибавим к одному или к обеим числам некое k > 0, то получим ситуацию заведомо выигрышную. Потому что:

Из (n1 + k, n2) мы берём (k, 0) - получается (n1, n2) - напоминаю, она проигрышная, так что наш противник уже проиграл.
Из (n1 + k, n2 + k) мы берём (k, k) - получается опять та же проигрышная (для противника) ситуация. Мы в любом случае в выигрыше.

Отсюда следует, что все ситуации n1 = n2, кроме (2, 2) - выигрышные. (0, 0) мы не рассматриваем, хотя её можно считать выигрышной, так как попадём мы в неё только если противник взял последние камни, то есть уже проиграл. (1, 1) выигрышная, так как забрав один камень, мы ставим противника в проигрышную (1, 0). А (2 + k, 2 + k) выигрышная, так как забрав по k камней из каждой кучи мы поставим противника в проигрышную (2, 2).

Так как задача симметрична, будем считать, что n1 < n2. Обозначим n2 - n1 = k > 0, а n1 обозначим n. Получаем, что начальное условие у нас (n, n + k). Так и будем дальше работать.

Базовые проигрышные ситуации: (0, 1), (2, 2). Соответствующие им выигрышные множества - (0, 1 + k), (1, 0 + k), (n, n + 1), (2, 2 + k), (n, n). То есть для n <= 2 и k <= 1 мы нашли единственные проигрышные точки, остальные - выигрышные. Графически это изображается следующим образом: рисуем проигрышные точки на плоскости, а затем рисуем от них горизонтальную, вертикальную и диагональную полупрямые. Ход игрока на этой плоскости - движение либо влево, либо вверх (в экранной системе координат, с осью y направленной вниз), либо влево-вверх. Дальше смотрим внимательно на ближайшую точку, не попавшую в выигрышное множество. Видим, что как из неё ни ходи, попадёшь в выигрышную точку, но это значит выигрыш для противника. Значит, для нас эти точки проигрышные. Это точки (3, 5) и (5, 3). От них рисуем по три полупрямых и повторяем всё снова. Получим следующий рисунок.
Выигрышно-проигрышный рисунок
Здесь я нарисовал все проигрышные точки для квадрата 44x44. Видно, что они все находятся примерно на двух прямых. Также видно, что (0, 1) и (2, 2) сильно "не в кассу", будем считать их вырожденными случаями.

Теперь попробуем найти это множество проигрышных точек аналитически. Сначала докажем, что для каждого n существует не более одной проигрышной ситуации (n, n + k). Докажем от противного. Допустим, есть две проигрышных ситуации (n, n + k1) и (n, n + k2). Тогда, находясь в ситуации с большим k мы отнимаем от правой кучи разницу между k1 и k2 - и ставим нашего противника в проигрышную ситуацию с меньшим k. Противник проигрывает, значит наша ситуация проигрышной не была.

Аналогично доказывается, что для каждого k существует не более одной проигрышной ситуации. Только в этом случае нужно брать из обеих куч, двигаясь от большего n к меньшему.

Теперь попробуем найти всё множество проигрышных ситуаций. Плясать будем от первого приличного случая, то есть от (3, 5). В терминах n и k это (3, 3 + 2). Доказано, что для каждого n и k проигрышная ситуация единственна, меньшие n и k мы рассмотрели ранее. Значит, для n <= 3 и k <= 2 проигрышных ситуаций больше не существует. Так что прибавляем к n и k по единице и получаем точку (4, 7) = (4, 4 + 3). Перебором возможных ходов можем убедиться, что она тоже проигрышная. Ещё раз увеличив n и k, получим (5, 9). Но - это не очередная проигрышная ситуация! Потому что взяв из второй кучи 6 камней мы получим (5, 3), а это то же самое что (3, 5) - наш противник в проигрыше. Почему такого не получилось с (4, 7)? Потому что цифра 4 ранее нам не встречалась на правом месте, а 5 - встречалась. Итак, делая шаг от одной проигрышной ситуации к следующей, надо внимательно смотреть, что получилось слева. Если там одно из чисел, встречавшихся ранее справа, наша новая ситуация - выигрышная! Если (5, 9) нас не устраивает, мы должны дальше идти в сторону увеличения n. k мы при этом увеличивать не обязаны, так как для k = 4 мы пока ни одной проигрышной ситуации ещё не нашли. Так что прибавляем к n единицу, получаем (6, 10) = (6, 6 + 4). 6 нам раньше в роли n2 не встречалось. Эта ситуация проигрышная. Это следует из того, что любой шаг из неё ведёт в выигрышную - для противника - ситуацию. Шаг по горизонтали или диагонали - и противник в ситуации с n1 < 6, для которых мы все проигрышные ситуации рассмотрели. Шаг по вертикали - противник в ситуации с k < 4 или n2 < 6, для которых мы проигрышные ситуации рассмотрели. Аналогичным образом получаются все проигрышные ситуации для каждого k. Через n1 иногда приходится "прыгать", если оно ранее встречалось в роли n2, это в силу симметричности задачи. Вот множество решений (n1, n2) k для 2 <= k < 20:

(3, 5) 2
(4, 7) 3
(6, 10) 4
(8, 13) 5
(9, 15) 6
(11, 18) 7
(12, 20) 8
(14, 23) 9
(16, 26) 10
(17, 28) 11
(19, 31) 12
(21, 34) 13
(22, 36) 14
(24, 39) 15
(25, 41) 16
(27, 44) 17
(29, 47) 18
(30, 49) 19

Посмотрим на него внимательно. Шаг n1 от итерации к итерации не менее единицы. Это доказано ранее. Шаг n2 равен шагу n1 плюс шаг k. Так как они оба не меньше единицы, значит шаг n2 не менее двух. Из этого следует, что когда мы на очередной итерации напоролись на ситуацию, когда n1 встречалось ранее в качестве n2, например, (5, 9), то увеличение n1 и n2 на единицу даст нам n2, гарантированно не встречавшееся ранее, так как минимальный шаг между ними равен 2, а значит всегда найдётся "дырка". Для примера (5, 9) это дырка между (3, 5) и (4, 7):
(3, 5) 2
-- тут нет (n1, n2 = 6) - дырка! --
(4, 7) 3
Раз дырка всегда найдётся, то максимальный шаг, который нам придётся сделать в n1 - это два. k при этом всё равно меняется с шагом в единицу, так что n2 изменится с шагом 2 + 1 = 3. Итак, возможные переходы от предыдущей проигрышной ситуации к следующей: (+1, +2) и (+2, +3). Других просто нет. Расстояние между ближайшими n1 составляет от 1 до 2, между ближайшими n2 - от 2 до 3. k всегда увеличивается на единицу. Насколько делать шаг по n - зависит от того, какие n + k нам встречались ранее. Программа, осуществляющая поиск решений, выглядит в первом приближении так:
  static int m[STONES_SIZE]; // STONES_SIZE - просто константа
  int n = 2;
  int klast = 2;
  m[2] = 100; // любое большое число
  for(int k = 2; k < STONES_SIZE; k++) {
    n++;
    if (n > m[klast])
      klast++;
    if (n == m[klast]) {
      printf("-(%3d, %3d) %3d\n", n, n - klast, klast);
      n++;
    }
    m[k] = n + k;
    printf("+(%3d, %3d) %3d\n", n, n + k, k);
  }

К сожалению, она жрёт памяти порядка N (N - максимальное k для которого мы ищем решения). Зато порядок времени тоже всего лишь N. Если бы мы просматривали на каждой итерации все прошлые решения с целью поиска там нужного n2, то время было бы O(N^2), но если хорошо подумать, необходимости в этом нет, так как если мы помним, где (на каком k) в последний раз нашли совпадение (klast), то новое совпадение следует искать в следующей точке - меньшие смысла рассматривать нет, сильно большие - тоже, так как n1 растёт в общем случае не быстрее n2 и не может его перегнать. Так что запомнив последний индекс, мы всегда смотрим только туда, индекс этот при необходимости увеличивая, чтобы не отстать.

Если хорошо подумать, объём потребляемой памяти можно сократить в разы. Каждый раз, находя решение (n1, n2) мы уже в этот момент знаем, что в будущем n1 придётся "перепрыгнуть" через теперешнее n2. Можно завести массив битиков, в котором помечать все n2, через которые придётся "прыгать". А при рассмотрении очередного кандидата n1 просто смотреть, установлен ли этот битик. В упрощённом виде (вместо битиков - bool) это выглядит так:
  int n = 2;
  static bool jump[STONES_SIZE * 3];
  for(int k = 2; k < STONES_SIZE; k++) {
    n++;
    if (jump[n])
      n++;
    jump[n + k] = true;
    printf("(%d, %d) %d\n", n, n + k, k);
  }

Массив "прыжков" пришлось завести побольше, так как n2 больше k. Можно в условии цикла нарисовать не k < STONES_SIZE, а n + k < STONES_SIZE. Тогда не придётся прикидывать во сколько раз n2 больше k. Ещё можно упаковать бульки в битики, уменьшим ещё в 8 раз. Но всё равно будет порядок O(N).

Теперь вопрос: можно ли уменьшить порядок времени или памяти. Мне видится память O(1) при времени O(N). Димариус, вместе с которым мы решали эту задачу, считает, что можно время уменьшить до O(log n) или типа того, если идти не по всем решениям, а как-то быстрее. Ведь наша цель - для данных (n1, n2) проверить, являются ли они проигрышной ситуацией, и если нет, то найти ближайшую проигрышную ситуацию, чтобы загнать туда противника. Неплохо было бы также идти в обратную сторону, то есть в сторону уменьшения n и k.

Сделать этого пока не удалось. Зато удалось кое-что выяснить. Для начала, распечатаем результаты работы первого решения, которое печатает не только находимые по ходу дела (n1, n2) k, но и решения для тех n1, через которые она "прыгает", вытаскивая при этом n2 и k из прошлого. Нормальные решения она помечает плюсом, "прыгнутые" - минусом. Графически это, кстати, означает, что наше решение попало на "прямую" из другой получетверти - например, мы идём по нижней, а решение попало на верхнюю. Итак, результаты печати:

+( 3, 5) 2
+( 4, 7) 3
-( 5, 3) 2
+( 6, 10) 4
-( 7, 4) 3
+( 8, 13) 5
+( 9, 15) 6
-( 10, 6) 4
+( 11, 18) 7
+( 12, 20) 8
-( 13, 8) 5
+( 14, 23) 9
-( 15, 9) 6
+( 16, 26) 10
+( 17, 28) 11
-( 18, 11) 7
+( 19, 31) 12
-( 20, 12) 8
+( 21, 34) 13
+( 22, 36) 14
-( 23, 14) 9
+( 24, 39) 15
+( 25, 41) 16
-( 26, 16) 10
+( 27, 44) 17
-( 28, 17) 11
+( 29, 47) 18
+( 30, 49) 19

Закономерности. Не может быть двух минусов подряд. Это доказано ранее: два минуса подряд значило бы, что шаг n1 (расстояние между плюсами) равен 3, а он может быть только 1 или 2. Не может быть более двух плюсов подряд. Это означало бы расстояние между прилегающими минусами в три плюса - а это в свою очередь означало бы шаг для n2 равный 4 - ведь мы помним, что в минусах n1 - это ранее встречавшиеся в плюсах n2!

Что тут не доказано, но наблюдается, так это то, что при переходе плюс-минус n2 для минуса равно k от предыдущего плюса, например:
+( 22, 36) 14
-( 23, 14) 9
- видите, 14 прыгнуло с места k на место n2? Причина этого явления пока не очень ясна. Что это даёт? Ну, например, если мы идём по итерациям, и прошли уже два плюса подряд, мы знаем, что следующим должен быть минус. Мы знаем n1 - оно у нас при таком способе печати всегда увеличивается на единицу, потом что мы заполнили "дыры", мы знаем n2 - оно равно предыдущему k, хотя это не доказано. Мы знаем k, так как это всего лишь n1 - n2. То есть переход от двойного плюса к минусу всегда осуществляется контекстно-независимо. Переход от минуса к плюсу - тоже, если мы помним хотя бы последний плюс, для чего не нужно памяти O(N). А вот переход от одиночного плюса куда-либо - это уже сложнее. Неизвестным тут остаётся то, что же за этим плюсом идёт - ещё один плюс, или минус? Закономерности тут пока не удалось найти даже не доказанной.

Ещё есть фишка, что эти все числа подозрительно близки к золотому сечению. Если развернуть от каждой пары чисел ряды Фибоначчи в сторону уменьшения, получается следующая картина:
( 1, 2) 3
( 1, 3) 3
( 2, 4) 3
( 1, 2) 5
( 3, 6) 3
( 1, 3) 5
( 4, 8) 3
( 1, 4) 5
( 2, 4) 5
( 1, 5) 5
( 2, 5) 5
( 1, 2) 7
...
( 26, 60) 9
( 5, 26) 11
( 23, 62) 9
( 28, 59) 9
( 10, 23) 11
( 25, 61) 9
( 2, 28) 11
( 22, 63) 9
( 27, 60) 9
( 7, 25) 11
( 24, 62) 9
( 29, 59) 9
Тут слева нарисована начальная пара ряда, а справа - пар ряда нужно пройти, чтобы получить очередное решение. Например, для (1, 3) это три пары: (1, 3) -> (3, 4) -> (4, 7). Последняя пара и есть решение. Выше приведены числа для первых решений, и решений где-то в районе k = 1000. Видно, что постепенно решения "отползают" от начал рядов, сначала они отличаются на 3-7 итераций, потом на 7-9, ближе к 1000 - уже на 9-11. Остаются неясными вопросы, далеко ли они уползут от начал рядов, а также каково вообще множество этих рядов. Интуитивно кажется, что ползут они к бесконечности, а множество рядов - это все вообще возможные ряды Фибоначчи. Если приведённые выше значения отсортировать и отфильтровать уникальные, получится примерно вот что:
( 1, 2)
( 1, 3)
( 1, 4)
( 1, 5)
( 1, 6)
( 1, 7)
( 1, 8)
( 1, 9)
( 1, 10)
( 1, 11)
( 1, 12)
( 1, 13)
( 1, 14)
( 1, 15)
( 1, 16)
( 1, 17)
( 1, 18)
( 1, 19)
( 1, 20)
( 1, 21)
( 1, 22)
( 1, 23)
( 1, 24)
( 1, 25)
( 1, 26)
( 1, 27)
( 1, 28)
( 1, 29)
( 1, 30)
( 2, 4)
( 2, 5)
( 2, 6)
( 2, 7)
( 2, 8)
( 2, 9)
( 2, 10)
( 2, 11)
( 2, 12)
( 2, 13)
( 2, 14)
( 2, 15)
( 2, 16)
( 2, 17)
( 2, 18)
( 2, 19)
( 2, 20)
( 2, 21)
( 2, 22)
( 2, 23)
( 2, 24)
( 2, 25)
( 2, 26)
( 2, 27)
( 2, 28)
( 2, 29)
( 2, 30)
( 2, 31)
( 2, 32)
( 3, 6)
( 3, 7)
( 3, 8)
( 3, 9)
( 3, 10)
( 3, 11)
( 3, 12)
( 3, 13)
...
Тут видно, что попадается практически всё, что можно только сочинить. Наверняка при больших k будут и ряды, начинающиеся с (1, 31) и (2, 50), и чего угодно. Но это тоже пока не доказано. Да и нет смысла доказывать, пока не ясен, какой с этого может быть прок. Даже если удастся доказать, что отношение пар стремится к золотому сечению, что с этим делать? Димариус предложил нарисовать прямую и принадлежность произвольной пары к множеству проигрышных точек оценивать по нахождению в эпсилон-окрестности этой прямой, но тут не очень понятно, что брать за эпсилон. Для небольших чисел эпсилон должен быть большим, для больших - меньше. Он предложил подобрать его экспериментально для подсчитанных ранее моим способом решений. Это даст нам решение с памятью и временем O(1), но только для заранее известных множеств решений. Разумеется, это всё-таки даёт нам выигрыш - позволяет нигде не хранить ранее найденные решения и не тратить время на их повторное нахождение каждый раз. Между прочим, решения до ста миллионов моим методом считаются за секунду, но в файл пишутся четыре минуты - и файл этот занимает более 3 гигабайт.

Итого, осталось: разобраться с тем, какое же это всё имеет отношение к числам Фибоначчи, найти способ понять, что же идёт после плюса: минус или ещё один плюс, доказать разного рода предположения, если от них обнаружится какой-то прок, свести память к O(1) или время к чему-нибудь поменьше. Память O(N) мне активно не нравится. Хотя при объёме в 1 Гб можно посчитать решения до 8 млрд., что уже не влезает в 32 бита, а если использовать файл для хранения массива - то вообще офигеть можно.

И ещё: изначальная задача всё-таки не только сделать один шаг, но и играть дальше. А это значит - придётся либо всё-таки запоминать найденные решения, а не только массив "прыжков", либо на каждом ходе заново всё считать. Механизм "перемотки взад" был бы полезнее, но я понятия не имею, как по этим решениям можно шагать в обратную сторону. Хотя, шаги нам известны, остаётся всё та же "проблема плюса". И недоказанное утверждение о том, что n2 минуса равно k предыдущего плюса.
Tags: think
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments