Jane Street puzzle writeup: Sum One, Somewhere

I really enjoyed working on this months puzzle which involved labeling nodes in an infinite binary tree (0 with the probability of p and 1 otherwise).

The goal was to find the value of p so the probability of an infinite path along the binary tree (with at most one 1) existing is 1/2.

Solution:

I started out by defining f(o) as the probability that a binary tree has at most o ones.

Now there are two relevant cases to consider:

Case 1: o = 0 (no extra 1’s allowed)

For an infinite path to exist in this case the current node must be 0, which occurs with probability p. Additionally at least one of the two sub-trees must have an infinite path of 0's (or equivalently not both of them should have no path).

$$f_p(0) = p \cdot (1 - (1 - f_p(0))^2)$$

Simplifying this equation by dividing by f(0) yields:

$$f_p(0) = \frac{2p-1}{p}$$

Case 2: o = 1 (at most one 1 allowed)

Now there are two more sub-cases depending on if the current node is a 0 or 1:

• If it's a 0, there is still have one 1 left.

• If it's a 1, we need to continue using f(0).

A possible equation modelling this behavior is:

$$f_p(1) = p \cdot (1 - (1 - f_p(1))^2) + (1-p) \cdot (1 - (1 - f_p(0))^2)$$

Since f(1) should be 1/2 I simply replaced each occurrence of f(1) with 1/2.

$$\frac12 = p \cdot (1-(1-\frac12)^2)+(1-p)\cdot (1-(1-f_p(0))^2)$$

Solving results in this cubic equation:

$$0= \frac34 p^3 - \frac52 p^2+3p-1$$

After solving for p, the first 10 decimal digits are: 0.5306035754.

I had a great time working on this puzzle, and I am looking forward to the next one!