树边分类
Tree-edge Triage
题目详情
Aaron and Beren are playing a game on an infinite complete binary tree. At the beginning of the game, every edge of the tree is independently labeled A with probability p and B otherwise. Both players are able to inspect all of these labels1. Then, starting with Aaron at the root of the tree, the players alternate turns moving a shared token down the tree (each turn the active player selects from the two descendants of the current node and moves the token along the edge to that node). If the token ever traverses an edge labeled B, Beren wins the game. Otherwise2, Aaron wins.
An example game is in the picture above: after the labeling, Aaron chooses to go left to avoid immediate defeat, but after Beren goes right Aaron is doomed to choose one of two B paths and Beren wins.
What is the infimum of the set of all probabilities p for which Aaron has a nonzero probability of winning the game? Give your answer in exact terms.
-
… somehow. ↩
-
To make this precise, we can add the following step to the start of the game: after the edges are labeled and inspected, Beren is allowed to name any positive integer N. Aaron wins if the first N edges traversed by the token are all labeled A, Beren wins if any of them are labeled B. ↩
解析
假设对于给定的p，Aaron 在无限树上获胜的概率为x。然后 从游戏的前两回合来看，如果双方至少有一方获胜，阿龙就可以获胜 该树有 3 个标记为 A 的边，Beren 可以选择的两个子树都可以通过以下方式获胜 Aaron（我们知道其概率 x，每个子树独立）。所以方程x p 必须满足：
x = 2 * p^3 * x^2 - p^6 * x^4。
（减去的项是根据阿龙何时可以在双方都获胜的情况下进行重复计算的 树）。
我们想要找到最小的正p，其中它的正根x < 1。这可以 可以用判别式理论来完成，但也可以通过注意到作为p来解决 增加，即上式右侧的四次图 从下方接近 f(x) = x 的图形，接触到它的那一刻 相切。所以我们可以添加右侧导数等于的约束 1 在平等点：
1 = 2 * p^3 * (2x) - p^6 * 4x^3
这两个方程的解为x = 8/9，以及p = (27/32)^(1/3)。所以最低的 阿龙能够赢得比赛的非零概率是惊人的高 8/9 概率！
恭喜你们解决了这个棘手的数学难题！
Original Explanation
Suppose for a given p, Aaron’s probability of winning on the infinite tree is x. Then looking at first two turns in the game, Aaron can win if at least one of the two sides of the tree has 3 edges marked A and BOTH subtrees Beren can choose between are winnable by Aaron (which we know has probability x, independently per subtree). So the equation x and p must satisfy is:
x = 2 * p^3 * x^2 - p^6 * x^4.
(The subtracted term is from the double counting of when Aaron can win on both sides of the tree).
We want to find the smallest positive p where this has a positive root x < 1. This can be done with the theory of discriminants, but also can be solved by noticing that as p increases, the graph of the quartic that is the right hand side of the above equation approaches the graph of f(x) = x from below, and the moment where it touches it will be tangent. So we can add the constraint that the derivative of the right hand side equals 1 at the point of equality:
1 = 2 * p^3 * (2x) - p^6 * 4x^3
These two equations are solved by x = 8/9, and p = (27/32)^(1/3). So the lowest nonzero probability Aaron can have of winning the game is the surprisingly high 8/9 chance!
Congrats to those of you who worked out this tricky math puzzle!