中括号学 101
Bracketology 101
题目详情
There’s a certain insanity in the air this time of the year that gets us thinking about tournament brackets. Consider a tournament with 16 competitors, seeded 1-16, and arranged in the single-elimination bracket pictured above (identical to a “region” of the NCAA Division 1 basketball tournament). Assume that when the X-seed plays the Y-seed, the X-seed has a Y/(X+Y) probability of winning. E.g. in the first round, the 5-seed has a 12/17 chance of beating the 12-seed.
Suppose the 2-seed has the chance to secretly swap two teams’ placements in the bracket before the tournament begins. So, for example, say they choose to swap the 8- and 16-seeds. Then the 8-seed would play their first game against the 1-seed and have a 1/9 chance of advancing to the next round, and the 16-seed would play their first game against the 9-seed and have a 9/25 chance of advancing.
What seeds should the 2-seed swap to maximize their (the 2-seed’s) probability of winning the tournament, and how much does the swap increase that probability? Give your answer to six significant figures.
解析
解决这个谜题的最直接方法是，在给定每次交换的情况下，递归地计算每场比赛获胜者的概率分布。对 2 号种子最有利的交换是交换种子 3 和 16，这将使 2 号种子获胜的概率增加 6.55795%。一个容易犯的错误是意外地报告了将 2 号种子与 1 号种子交换后 1 号种子的获胜概率。这种交换对 2 号种子有利，但只将其获胜概率从 21.6040% 增加到 23.0283%，即增加了 1.4243%。
以下解谜者设法找到了正确的交换并计算了概率的增加。
Original Explanation
The most straightforward way to solve this puzzle was to compute the probability distributions of the winners of each match recursively, given each swap. The most advantageous swap for the 2-seed is to swap seeds 3 and 16, which increases the 2-seed’s probability of winning by 6.55795%. One easy mistake to make was to accidentally report the 1-seed’s probability of winning after swapping the 2-seed with the 1-seed. This swap is good for the 2-seed, but only increases their probability of winning from 21.6040% to 23.0283%, so 1.4243%.
The following puzzlers managed to find the correct swap and the increase in probability.