Как следует из названия, эта проблема наполовину вдохновлена вежливым близоруким пьяным ботом @NP

Наш бедный бот помещается на декартовой сетке в начале координат, и через каждую минуту он перемещается на 1 единицу в одном из четырех направлений (вверх, вниз, влево, вправо).

Через n минут все скрытые мины в сетке активируются, убивая любого плохого бота, который может оказаться над ними. Мины расположены во всех целочисленных координатах, удовлетворяющих уравнению | y | = | x |.

Вызов

Вам будет предоставлено n , количество минут до взрыва мины, в качестве входных данных и выходных данных вы должны найти вероятность того, что бот мертв .

Ввод : натуральное число, представляющее n .

Вывод : Пусть вероятность того, что бот мертв, будет p / q, где p и q - относительно простые целые числа (q не может быть 0, но p может). Выход р.

правила

• Ваш алгоритм не должен работать в экспоненциальном или более высоком времени. В идеале он должен работать за полиномиальное время или меньше.
• Ваш алгоритм должен быть способен обрабатывать входные данные n<20 (могут быть скорректированы, если слишком сложно) в разумные сроки.
• Это вызов для игры в гольф .
• Перебор всех возможностей для данного n будет определенно не принят в качестве ответа.

Тестовые случаи

1->0

2->3

4->39

6->135

8->7735

10->28287

Пример расчета для n = 6

У нас есть 4 возможных хода: U, D, R и L. Общее количество путей, которое можно было бы выбрать, составляет 4 ^ 6 или 4096. Есть 4 возможных случая, которые приземляются вдоль линии y = x: x, y = ± 1; х, у = ± 2; х, у = ± 3; или x = y = 0. Мы посчитаем количество способов попасть в (1,1), (2,2) и (3,3), умножим их на 4, чтобы учесть другие квадранты, и добавим это количество способов в конечном итоге в (0,0).

Случай 1: бот заканчивается в (3, 3). Чтобы бот оказался здесь, у него должно было быть 3 правильных хода и 3 хода вверх. Другими словами, общее количество способов попасть сюда - это способы перестановки букв в последовательности RRRUUU, в которой 6 выбирают 3 = 20.

Случай 2: бот заканчивается в (2,2). Чтобы бот оказался здесь, у него могло быть 2 хода вверх, 3 хода вправо и 1 ход слева; или 2 правильных движения, 3 движения вверх и 1 движение вниз. Таким образом, общее количество способов получить здесь является суммой способов перестановки букв в последовательностях RRRLUU и UUUDRR, обе из которых (6 выбирают 1) * (5 выбирают 2) = 60, всего 120 возможностей ,

Случай 3: бот заканчивается в (1,1). Чтобы бот оказался здесь, у него могли быть: 1 правильный ход, 3 хода вверх и 2 хода вниз. В этом случае количество способов перестановки букв в последовательности RUUUDD составляет (6 выберите 1) * (5 выберите 2) = 60.

1 ход вверх, 3 движения вправо и 2 движения влево. В этом случае количество способов перестановки букв в последовательности URRRLL составляет (6 выберите 1) * (5 выберите 2) = 60.

2 движения вправо, 1 движение влево, 2 движения вверх и 1 движение вниз. В этом случае количество способов перестановки букв в последовательности UUDRRL составляет (6 выберите 1) * (5 выберите 1) * (4 выберите 2) = 180.

Таким образом, общее количество способов попасть в (1,1) составляет 300.

Случай 4: бот заканчивается в (0,0). Чтобы бот оказался здесь, он мог иметь:

3 правых хода и 3 левых хода. В этом случае количество способов перестановки букв в последовательности RRRLLL составляет (6 выберите 3) = 20.

3 ходов вверх и 3 ходов вниз. В этом случае количество способов перестановки букв в последовательности UUUDDD составляет (6 выберите 3) = 20.

1 движение вправо, 1 движение влево, 2 движения вверх и 2 движения вниз. В этом случае количество способов перестановки букв в последовательности RLUUDD составляет (6 выберите 1) * (5 выберите 1) * (4 выберите 2) = 180.

1 движение вверх, 1 движение вниз, 2 движения вправо и 2 движения влево. В этом случае количество способов перестановки букв в последовательности RRLLUD составляет (6 выберите 1) * (5 выберите 1) * (4 выберите 2) = 180.

Таким образом, общее количество способов попасть в (0,0) составляет 400.

Сложив эти случаи вместе, мы получим, что общее число способов попасть в | y | = | х | 4 (20 + 120 + 300) + 400 = 2160. Таким образом, наша вероятность составляет 2160/4096. Когда эта доля полностью уменьшена, это 135/256, поэтому наш ответ 135 .

Python 2 , 65 байт

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Попробуйте онлайн!

Вероятность смерти бота может быть выражена как:

$$f(n) = 2s-s^2\text{, where } s=\frac{1}{2^n}\binom{n}{n/2}$$

и бином понимается равным когда не является целым.$0$$n/2$

Мы можем рассуждать так. Какова вероятность того, что бот приземлится на линию ? Это происходит, если общее количество ходов вверх и влево равно общему количеству ходов вниз и вправо. Это та же вероятность, что, скажем, вы подбрасываете монету раз и получаете столько хвостов, сколько и голов. Вы должны выбрать сальто, чтобы быть главами сальто, что может быть сделано способами, из возможных последовательностей в целом, давая вероятность$y=x$$n$$n/2$$n$$\binom{n}{n/2}$$2^n$

Вероятность посадки линии также равна . Таким образом, вероятность посадки на любой линии равна сумме этих или , за исключением того, что мы дважды учитываем вероятность посадки в обеих линиях и должны вычесть ее, чтобы компенсировать.$y=-x$$s$$2s$$x=y=0$

Оказывается, вероятность посадки на составляет всего , произведение вероятности посадки на каждой линии. Мы можем утверждать, что события независимы следующим образом: если мы выберем случайную последовательность равных чисел «Вверх или Влево» и «Вниз или Вправо», чтобы попасть на а также с «Вверх или Вправо» и «Вниз или Влево» «для мы можем однозначно объединить их в последовательность вверх, вниз, влево, вправо, взяв пересечение пар направлений в каждой позиции.$x=y=0$$s^2$$x=y$$x=-y$

Таким образом, вероятность посадки на или равна .$x=y$$x=-y$$2s-s^2$

Код вычисляет бином используя это выражение как с базой . Чтобы извлечь числитель из доли вероятности, отметим, что знаменатель является степенью 2, поэтому мы используем выражение, чтобы разделить максимальную степень 2 , выраженную в виде классического битового трюка .$\binom{n}{n/2}$(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

Решение заключается в том, чтобы записать как чтобы на ссылались только один раз, и работать без дробей чтобы оставаться в целых числах. Вычисление имеет полиномиальное время по даже с использованием метода вычисления биномов.$2s-s^2$$1-(1-s)^2$$s$$1/2^n$$n$

После написания доказательства вероятности смерти бота я нашел более чистый способ доказать это и представить его.

Будем отслеживать значения и после каждого хода бота. Каждое из четырех направлений вверх, вниз, влево и вправо либо увеличивает, либо уменьшает каждое из и , причем четыре направления соответствуют четырем комбинациям.$a=x+y$$b=x-y$$a$$b$

Таким образом, случайный ход эквивалентен случайному добавлению к и независимо к . Это равносильно выполнению отдельных случайных прогулок по и .a ± 1 b a $\pm 1$$a$$\pm 1$$b$$a$$b$

Теперь робот заканчивается на линии или именно тогда, когда или . Таким образом, вероятность завершения с равна и аналогично для . Поскольку прогулки независимы, вероятность того, что и равна , поэтому вероятность того, что хотя бы один равен нулю, является дополнением .x = - y a = 0 b = 0 a = 0 s = $x=y$$x=-y$$a=0$$b=0$$a=0$ b=0a≠0b≠0(1-с)21-(1-с)$s=\frac{1}{2^n}\binom{n}{n/2}$$b=0$$a\neq 0$$b\neq 0$$(1-s)^2$$1-(1-s)^2$