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

Решение задачи о камнях

О-о-о-о-о-о-о-о!!! Я её решил, причём как! И аналитическое решение нашёл, которым можно по заданному k найти n за константное время, и за O(log n) итераций можно проверить, если не доверяем вещественной арифметике, хотя практика показала что тут точности более чем хватает.

Решив, полез в инет искать решения. Выяснил, что задачка была придумана неким Витгофом аж в 1907 году. И он же нашёл решение. 100 лет назад получается, кстати.

Короче, сначала мы с Димариусом тоскливо смотрели на ряды Фибоначчи, думая, чего хорошего из них можно выжать. Ничего не придумали. Потом я решил нарисовать на плоскости все точки, для которых размотка рядов Фибоначчи до начала требует чётное число итераций или нечётное. Получилось вот что:
Чётные и нечётные пары рядов
Неправда ли, знакомая картинка? Это ЖЖ неспроста - решил я. Прямые, разделяющие чёрную и белую области, имеют коэффициент наклона, равный золотому сечению. Соответственно, если взять нижнюю четверть, для точек в белой области n1/n2 > G, а для точек в чёрной n1/n2 < G, G - золотое сечение, то есть (sqrt(5)-1)/2. То есть отношение чисел Фибоначчи для любого ряда прыгает из чёрной области в белую на каждой итерации, хоть и стремится к золотому сечению. Это доказать оказалось нетрудно. Достаточно было понять, что первые два числа ряда не могут иметь отношение больше 0.5, а дальше из того, что на n-м шаге отношение больше легко выводится, что на n+1-м оно будет меньше и наоборот. Ладно, доказали.

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

Для этого пришлось взять The Gimp и нарисовать следующий корявый рисунок:
Всевозможные расстояния
Вот если мы будем рассматривать точку, что снизу от нижней прямой, то для неё я ввёл три расстояния до прямой золотого сечения. Расстояние горизонтальное, вертикальное и диагональное. Эти расстояния равны количеству пикселей, на которое нужно сдвинуться вверх, вправо или вправо-вниз, чтобы попасть на прямую золотого сечения. Причём для диагонального расстояния геометрическое расстояние будет равно диагональному расстоянию умноженному на корень из двух, так как именно такую длину имеет диагональ одного пикселя. Это мне, программисту, удобно всё пикселями мерить. Все эти расстояния иррациональны, поскольку на прямой ни одной рациональной точки нет ни фига. Поэтому, чтобы число пикселей получилось целым, нужно эти расстояния округлять.

Так вот, критерий "шаг вправо-вниз ведёт в белую точку" по сути означает, что диагональное расстояние меньше единицы, поэтому сдвиг на единицу заставляет нас пересечь прямую. Чисто геометрически удалось это расстояние найти для произвольных n1 и n2, таких что n1<n2:
N(n1, n2) = (G*n2 - n1) / (1 - G)
Причём если точка находится в чёрной области, это расстояние положительное, а если в белой - то отрицательное, т. е. шагать надо влево-вверх.
Значит, наш критерий проигрышности точки формулируется следующим образом:
0 < N(n1, n2) < 1 - точка должна быть чёрной и лежать "близко" к границе. Теперь мы знаем, что это за "близко". Осталось всего-то ничего - доказать это.
Ещё я сумел выразить вертикальное (d1) и горизонтальное (d2) расстояния через N:
d1(n1, n2) = N(n1, n2) * G, d2(n1, n2) = N(n1, n2) * (1-G)
Доказать оказалось не очень просто, но и не так сложно. Спасло знание алгоритма, а именно, того, что k+1-е решение отличается от k-го либо на (+1,+2), либо на (+2,+3). Сначала я тупой подстановкой доказал, что критерий выполняется для первых решений - (3, 5) и (4, 7). Затем я подумал и понял, что для определённого диапазона k=2..K количество точек, удовлетворяющих критерию равно K-1 (количеству разных k), и количество решений равно тому же. Для критерия это следует из того что если провести K-1 диагоналей под 45 градусов, то они все где-нибудь да пересекут прямую золотого сечения, и ближайшая целочисленная точка как раз и будет удовлетворять критерию. А для решений это уже доказано - для каждого k существует одно и только одно решение. Получилось что для k=2..3 множества решений и точек, удовлетворяющих критерию, совпадают. Осталось доказать рекурсивное правило, из которого будет следовать, что и для больших k это так.

Для этого я выразил N(n+1, k+1) и N(n+2, k+1) через N(n,k), а потом доказал, что если для нового решения N не попадает в интервал 0..1, то ход (+1,+2) уводит нас в область N>1, а ход (+2,+3) - в область N<0. Геометрически это следует из того, что углы наклонов прямых соотносятся так: 1/2 < G < 2/3. Причём далеко из интервала 0..1 мы убежать не могли, потому что N с каждым шагом изменяется на фиксированную константу. Это мне позволило оценить, в какой диапазон попадёт N для нового решения, если для предыдущего оно было в 0..1. Далее я рассмотрел оба случая, и пришёл к выводу, что куда бы мы ни шагали, если N при этом шаге вылезло из диапазона 0..1, то если провести прямую вверх из точки решения и остановиться на первой чёрной точки в верхней, симметричной области, то для неё N будет попадать в интервал 0..1. А поскольку эта чёрная точка симметрична одной из рассмотренных нами ранее, она является проигрышной. Но из того, что она проигрышная, следует выигрышность той точки, в которую мы шагнули. И если это выполняется для шагов (+1,+2) и (+2,+3), то получается противоречие - мы ведь знаем, что одна из этих точек должна быть решением! А значит, доказательство от противного удалось.

Это даёт замечательный результат: теперь нам не нужно иметь O(n) памяти чтобы помнить все прошлые n2. Достаточно оценить N и посмотреть, попадает ли оно куда надо или нет. Если нет - делаем дополнительный шаг по n и гарантированно попадём куда надо. Выглядит наше решение вот так:

double approx_N(int n, int k)
{
  // G1 = (1 - G) - это всё глобальные константы
  return ((G - (double)(n) / (double)(n + k)) / G1) * (double) (n + k);
}

void approx()
{
  int n = 2;
  for (int k = 2; k < STONES_SIZE; k++) {
    n++;
    double N = approx_N(n, k);
    if (N > 1.0)
      n++;
    N = approx_N(n, k);
    printf("(%d, %d) %d\n", n, n + k, k);
  }
}

Памяти ему не надо вовсе. Время O(n). Работает на ура. Если мы боимся ошибок округления, хотя практика показала, что бояться их тут не стоит, то можно увеличить время до O(n log n). Для этого вместо проверки N нужно делать пробный шаг по n и проверять - чёрная там точка или белая. Если белая, мы стоим в проигрышной, если же чёрная - то эта чёрная проигрышная. Белость или чёрность проверяем размоткой ряда Фибоначчи и оценкой чётности или нечётности пары - для этого и нужно O(log n) операций.

Теперь вспоминаем, что мы вообще-то должны не все проигрышные ситуации искать, а по заданному (n1, n2), n1 < n2 найти ход в ближайшую проигрышную. Если (n1, n2) в белой области, это будет ход по диагонали влево-вверх. Из уравнений прямых находится количество шагов в ту сторону:
(n1 - Gn2) / (1 - G)
Округляем это дело в большую сторону - нам ведь в чёрную область надо попасть. Причём проверять полученную точку на правильность не нужно, для каждого k решение существует, а в другом месте его быть и не может.

Если (n1, n2) в чёрной области, то шаг делаем вверх, либо на нижнюю прямую, либо на верхнюю. Вот тут надо оценивать N, только по нему можно понять, какая же из точек проигрышная. Количество шагов вверх на нижнюю прямую:
(Gn2 - n1) / G, округление в меньшую сторону (мы не хотим вылезти из чёрной области)
Количество шагов вверх на верхнюю прямую:
n2 - Gn1, тут округляем в большую сторону, так как мы хотим залезть в чёрную область вверху.

Работает, опять же, на ура. Тут же можно белость и чёрность оценивать не по критерию n1/n2 < G, а размоткой ряда, чтобы избежать вещественной арифметики. И сделав нужный шаг, можем поболтаться вперёд-взад, считая ряды Фибоначчи и уточняя, туда ли мы попали. Но и тут практика показала, что вещественная арифметика справляется.

Ещё нужно помнить, что для малых n (<=2) и k (<=1) ситуации вырожденные, так что их нужно рассматривать отдельно.

У Витгофа всё было гораздо проще. Формула для вычисления n по k:
n = k * (1 + G), округляем в меньшую сторону. Всё!!!
Правда, этого достаточно лишь для нахождения множества проигрышных ситуаций, а не для того, чтобы понять, куда ходить из заданной точки, хотя одно легко следует из другого. И эта формула легко получается из моих выкладок, если в формулу для диагонального расстояния подставить n1 = n, n2 = n + k, то и получится, что формула Витгофа эквивалентна моему "диагональное расстояние от 0 до 1". Жаль не удалось найти доказательство формулы, интересно было бы посмотреть чего у него общего с моими бреднями.
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