744. How?.md

This page has detailed how I solved the 744. What? Where? When?

Step 1

It's easier to find the probability that the game ends abnormally, i.e. with a red card, denote it as . Start from small n and see if there is any pattern here:

n = 1: there are three envelopes. The game ends no matter which card is chosen,

n = 2: there are five envelopes. The game ends with a red card if any of the following happens:

      - 1st envelope contains the red card --> 1/5

      - 1st envelope contains a question, the expert gives the correct answer; 2nd envelope contains the red card --> 1/5 * p

      - 1st envelope contains a question, the expert gives the wrong answer; 2nd envelope contains the red card --> 1/5 * (1 - p)

      - 1st envelope contains a question, the expert gives the correct answer; 2nd envelope contains a question, the expert gives the wrong answer; 3rd envelope contains the red card --> 1/5 * p * (1 - p)

      - 1st envelope contains a question, the expert gives the wrong answer; 2nd envelope contains a question, the expert gives the correct answer; 3rd envelope contains the red card --> 1/5 * (1 - p) * p

      So

n = 3: there are seven envelopes. Using the same idea,

Step 2

Notice that the denominator of is simply . So we can just focus on the numerator. Let and write the numerator as a function , we have

For and , the following two equations are useful

To double check my calculation above, I wrote the following piece of code which replicates the process but struggles when n is bigger than 10.

from collections import deque

class Node:
    def __init__(self, up, down, prob, N, red=1):
        self.up = up  # expert's point
        self.down = down  # viewers' point
        self.prob = prob  # probability of reaching current node
        self.N = N  # remaining number of non-red normal envelopes
        self.red = red  # if current is red


class Game:
    def __init__(self, n, p):
        self.n = n
        self.p = p
        self.res = 0.0  # probability of game ending normally

    def calculate(self):
        root = Node(0, 0, 1.0, 2 * self.n, 0)
        dq = deque([root])
        while dq:
            node = dq.popleft()
            if node.red:
                continue
            if node.up == self.n or node.down == self.n:
                self.res += node.prob
                continue
            up, down, prob, N = node.up, node.down, node.prob, node.N
            dq.append(Node(up, down, prob / (N + 1), N, 1))
            dq.append(Node(up + 1, down, self.p * prob * N / (N + 1), N - 1, 0))
            dq.append(Node(up, down + 1, (1 - self.p) * prob * N / (N + 1), N - 1, 0))
        return self.res

def v1(n, p):
    """Replicates the process.
    Becomes slow when n > 10"""
    g = Game(n, p)
    return g.calculate()

Step 3

The coefficients in seem to have a pattern. From List of integer sequences, I found Catalan number. So I implemented the v2() below and it gives the same answer as v1() above for small n. However, it doesn't work when n is bigger than 520 since it involves large factorials.

from math import comb

def catalan(k):
    return comb(2 * k, k) / (k + 1)

def v2(n, p):
    """Only works for n <= 520.
    Otherwise OverflowError"""
    x = p * (1 - p)
    y = sum(catalan(k) * pow(x, k) for k in range(n))
    return 1 - y * n / (2 * n + 1)

Step 4

It is in this section that I found the answer!

Setting y = -4x helps produce the final code below.

def p744(n, p):
    """Only works for large n"""
    x = p * (1 - p)
    y = (1 - sqrt(1 - 4 * x)) / (2 * x)
    return 1 - y * n / (2 * n + 1)

Final words

A bit of hard work (step 1 and step 2) and a bit of luck (step 3 and step 4). Solving Project Euler is possible.