囚犯与黑白手套 #

题目 #

A hundred prisoners are gathered together by their warden. Each prisoner gets two gloves: one black and one white. They are told that they have one night in order to plan a strategy, after which no communication between them will be possible. In the morning, they are told, each prisoner will have a distinct real number painted on his forehead. Each prisoner will be able to see the numbers painted on all other prisoners, but not his own. What each prisoner needs to do is to decide which glove to put on which hand. Once all prisoners have donned all gloves, they will be placed in a long line, one beside the other, ordered according to the value of the number on their foreheads, and will be asked to hold hands. If the pairs of hands holding each other all have same-colored gloves, all 100 prisoners will be set free.

Your goal is to design a strategy that will maximize the probability of this happening.

解答 #

100% 获得自由的策略是存在的. 囚犯们可以给自己编上从 1 到 100 的号码. 约定奇数号码的囚犯的默认戴法是左黑右白 (BW), 偶数号码的囚犯的默认戴法是左白右黑 (WB). 在排成一列后, 每个人统计自己看到的编号序列的逆序对个数, 如果是奇数那么就交换左右手的手套. 可以证明, 对于相邻的人, 他们看见的逆序对个数奇偶性相同, 当且仅当他们的编号的奇偶性不同. 考虑 $…, x, y, …$ , 为例. 设前面 $a$ 个数中有 $p_1$ 个大于 $x$ 的数, 有 $p_2$ 个大于 $y$ 的数, 后面 $b$ 个数中有 $q_1$ 个小于 $x$ 的数, 有 $p_2$ 个小于 $y$ 的数. 那么 $x$ 看到的逆序对个数是 $p_2 + q_2$ , $y$ 看到的逆序对个数是 $p_1 + q_1$ . 考虑 $100$ 个数中大于 $x$ 的数的个数, 为 $p_1 + b - q_1 + I(x < y)$ , 与 $x$ 的奇偶性相同; 类似, $100$ 个数中大于 $y$ 的数的个数为 $q_1 + b - q_2 + I(y < x)$ , 与 $y$ 的奇偶性相同. 那么 $p_1 + q_1 \equiv p_1 - q_1\equiv x - b - I(x < y)$ , $p_2 + q_2 \equiv p_2 - q_2\equiv y - b - I(y < x)$ , 有 $(p_1 + q_1) - (p_2 + q_2)\equiv (x - y) + (I(y < x) - I(x - y))\equiv (x - y) + (I(y < x) + I(x - y))\equiv x - y - 1$ . 因此, 对于相邻的人, 他们看见的逆序对个数奇偶性相同, 当且仅当他们的编号的奇偶性不同. 综上, 这样的策略总是能够保证相邻的手套颜色一致.