彩虹帽子

Rainbow Hats

专题: Strategy / 策略
难度: L4
来源: Brainstellar

题目详情

有 $N$ 人组队。进入房间后，每人被随机戴上一顶帽子，帽子上写着 $0,1,\dots,N-1$ 中的一个数（允许重复）。

每个人能看到其他人的帽子数字但看不到自己的。随后所有人同时猜自己帽子上的数字。

问：如何制定策略，保证至少有 1 人一定猜对？

提示：考虑模 $N$ 。

N people team up and decide on a strategy for playing this game. Then they walk into a room. On entry to the room, each person is given a hat on which one of the first N natural numbers is written. There may be duplicate hat numbers. For example, for N=3, the 3 team members may get hats labeled 2, 0, 2. Each person can see the numbers written on the others' hats, but does not know the number written on his own hat. Every person then simultaneously guesses the number of his own hat. What strategy can the team follow to make sure that at least one person on the team guesses his hat number correctly?

Hint

Modulo?

解析

把队员编号为 $0\sim N-1$ 。第 $i$ 人看到其他帽子数字之和为 $s$ ，则他猜

(i - s)\bmod N.

这样全体帽子数字总和 $S$ 满足 $S\equiv m\pmod N$ 的那个人 $m$ 会猜中自己的帽子，从而保证至少一人正确。

Original Explanation

Solution

Let the persons be numbered 0 to N-1. The i-th person should announce 1 + (i-s)mod N, where s is the sum of numbers he sees. With this strategy, if the sum of all N numbers equals 1 + (m mod N), then the m-th gnome is guaranteed to announce the number of his own hat!