总和一，某处
Sum One, Somewhere
题目详情
For a fixed p, independently label the nodes of an infinite complete binary tree 0 with probability p, and 1 otherwise. For what p is there exactly a 1/2 probability that there exists an infinite path down the tree that sums to at most 1 (that is, all nodes visited, with the possible exception of one, will be labeled 0). Find this value of p accurate to 10 decimal places.
解析
对于固定的 p，令 f(p) 为树具有 总和为零的无限路径，g(p) 树具有的概率 总和最多为 1 的无限路径。本月的问题是要求 找到 p 使得 g(p) = 1/2。
使用二叉树分解为其根和两个子树，我们看到
f(p) = p·(2f(p) - f(p)^{2})
简化为
f(p) = 2 - 1/p。
进一步，我们看到
g(p) = p·(2g(p) - g(p)^{2}) + (1-p)·(2f(p) - f(p)^{2})。
代入 g(p) = 1/2，我们最终得到 p 中的三次方程：
3p^{3} - 10p^{2} + 12p - 4 = 0
近似解0.5306035754…
恭喜本月的求解者！
Original Explanation
For a fixed p, let f(p) be the probability that the tree has an infinite path of sum zero, and g(p) the probability that the tree has an infinite path of sum at most 1. This month’s problem is asking to find the p such that g(p) = 1/2.
Using the decomposition of a binary tree into its root and its two subtrees, we see
f(p) = p·(2f(p) - f(p)2)
which simplifies to
f(p) = 2 - 1/p.
Further, we see
g(p) = p·(2g(p) - g(p)2) + (1-p)·(2f(p) - f(p)2).
Plugging in g(p) = 1/2 we end up with a cubic equation in p:
3p3 - 10p2 + 12p - 4 = 0
with approximate solution 0.5306035754…
Congrats to this month’s solvers!