As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.

Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit in one of four directions (Up, Down, Left, Right).

After n minutes, all of the latent mines on the grid activate, killing any poor bot that might find themselves over them. The mines are located at all integer coordinates satisfying the equation |y|=|x|.

Challenge

You will be provided n, the number of minutes before the mines blast, as an input, and as an output, you must find the probability that the bot is dead.

Input: An natural number representing n.

Output: Let the probability the bot is dead be p/q, where p and q are relatively prime whole numbers (q can't be 0, but p can). Output p.

Rules

  • Your algorithm must not run in exponential or higher time. It ideally should run in polynomial time or less.
  • Your algorithm must be able to handle inputs of n<20 (can be adjusted if too hard) in a reasonable time.
  • This is a challenge.
  • Iterating over all possibilities for a given n will most definitely not be accepted as an answer.

Test Cases

1->0

2->3

4->39

6->135

8->7735

10->28287

Example Calculation for n=6

We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is 4^6, or 4096. There are 4 possible cases that land along the line y = x: x,y = ±1; x,y = ±2; x,y = ±3; or x = y = 0. We will count the number of ways to end up at (1,1), (2,2), and (3,3), multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at (0,0).

Case 1: The bot ends at (3, 3). In order for the bot to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence RRRUUU, which is 6 choose 3 = 20.

Case 2: The bot ends at (2,2). In order for the bot to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences RRRLUU and UUUDRR, both of which are (6 choose 1) * (5 choose 2) = 60, for a total of 120 possibilities.

Case 3: The bot ends at (1,1). In order for the bot to end up here, it could have had: 1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RUUUDD is (6 choose 1)*(5 choose 2) = 60.

1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence URRRLL is (6 choose 1)*(5 choose 2) = 60.

2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence UUDRRL is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.

Thus, the total number of ways to end up at (1,1) is 300.

Case 4: The bot ends at (0,0). In order for the bot to end up here, it could have had:

3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence RRRLLL is (6 choose 3) = 20.

3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence UUUDDD is (6 choose 3) = 20.

1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RLUUDD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.

1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence RRLLUD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.

Thus, the total number of ways to end up at (0,0) is 400.

Adding these cases together, we get that the total number of ways to end up on |y| = |x| is 4(20 + 120 + 300) + 400 = 2160. Thus, our probability is 2160/4096. When this fraction is fully reduced, it is 135/256, so our answer is 135.

  • I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance. – Mr. Xcoder Aug 19 at 15:08
  • @Mr.Xcoder I will add one when I have time. – Rushabh Mehta Aug 19 at 15:20
  • 2
    Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other. – trichoplax Aug 19 at 21:48
  • 1
    But nobody talks about First Gen Learning Algorithm? – Redwolf Programs Aug 20 at 2:40
  • 1
    @RedwolfPrograms ahaha yea but this bot has the cooler name – Rushabh Mehta Aug 20 at 3:03
up vote 17 down vote accepted
+50

Python 2, 65 bytes

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

Try it online!

The probability the bot is dead can be expressed as:

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

and the binomial is understood to equal \$0\$ when \$n/2\$ isn't whole.

We can reason like this. What's the probability that the bot lands on the \$y=x\$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin \$n\$ times and get as many tails as heads. You must choose \$n/2\$ flips to be heads of \$n\$ flips, which can be done in \$\binom{n}{n/2}\$ ways, of \$2^n\$ possible sequences overall, giving probability

$$s=\frac{1}{2^n}\binom{n}{n/2}$$

The probability of landing the \$y=-x\$ line is also \$s\$. So, the probability of landing on either line is the sum of these or \$2s\$, except we're double-counting the probability of landing of \$x=y=0\$ in both lines, and must subtract it to compensate.

It turns out the probability of landing on \$x=y=0\$ is just \$s^2\$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on \$x=y\$ and likewise with "Up or Right" and "Down or Left" for \$x=-y\$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.

So, the probability of landing on \$x=y\$ or \$x=-y\$ is \$2s-s^2\$.

The code computes the binomial \$\binom{n}{n/2}\$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.

The solution is golfed by writing \$2s-s^2\$ as \$1-(1-s)^2\$ so that \$s\$ is only referenced once, and working without the \$1/2^n\$ fractions to stay within the integers. The computation is polynomial-time in \$n\$ even with the funky way of computing binomials.


After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.

Let's keep track of the values of \$a=x+y\$ and \$b=x-y\$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of \$a\$ and \$b\$, with the four directions corresponding to the four combinations.

So, a random move is equivalent to randomly adding \$\pm 1\$ to \$a\$ and independently \$\pm 1\$ to \$b\$. This is equivalent to doing separate random walks on \$a\$ and \$b\$.

Now, the robot ends on the line \$x=y\$ or \$x=-y\$ exactly when \$a=0\$ or \$b=0\$. So, the probability of ending with \$a=0\$ is \$s=\frac{1}{2^n}\binom{n}{n/2}\$ and likewise for \$b=0\$. Since the walks are independent, the probability that \$a\neq 0\$ and \$b\neq 0\$ is \$(1-s)^2\$, so the probability that at least one is zero is the complement \$1-(1-s)^2\$.

  • 3
    Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1 – Rushabh Mehta Aug 19 at 19:16
  • enjoy the small bounty (don't have much to give so sorry) – Rushabh Mehta Aug 22 at 21:56
  • 1
    @RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward. – xnor Aug 24 at 1:03
  • The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out. – Rushabh Mehta Aug 24 at 1:04

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.