Here is a solution to the warden puzzle from a few days ago.
A short description of the problem:
There are 100 prisoners, each with a number from 1 to 100 painted on their heads. Each can see the other 99 painted numbers but not his own, and has to guess his own number based only on the other 99. The goal is to get at least one correct guess.
The prisoners choose a numbering for themselves: $1, 2, \dots, 100$ (say ordered by when they got to prison). Suppose the numbers they get painted on their heads is $h_1, h_2, \dots, h_{100}$.
The solution is based on the following observation:
There is some $1 \le j \le 100$ such that $$h_1 + h_2 + \dots + h_{100} = j \mod 100$$ i.e. there is some prisoner (let's call him 'the boss') such that the sum of the painted numbers leaves the same remainder (when divided by 100) as the number chosen by the prisoners for 'the boss', based on the imprisonment date.
Now the strategy is simple, each prisoner assumes he is 'the boss' and makes his guess: by computing the sum of the other 99 (modulo 100, resulting in a number between 0 and 99) and subtracting that from his number based on imprisonment date. If the number is zero or negative, he adds a 100 to it and that would be his guess.
At least one will make the correct guess.
A short description of the problem:
There are 100 prisoners, each with a number from 1 to 100 painted on their heads. Each can see the other 99 painted numbers but not his own, and has to guess his own number based only on the other 99. The goal is to get at least one correct guess.
Solution
The prisoners choose a numbering for themselves: $1, 2, \dots, 100$ (say ordered by when they got to prison). Suppose the numbers they get painted on their heads is $h_1, h_2, \dots, h_{100}$.
The solution is based on the following observation:
There is some $1 \le j \le 100$ such that $$h_1 + h_2 + \dots + h_{100} = j \mod 100$$ i.e. there is some prisoner (let's call him 'the boss') such that the sum of the painted numbers leaves the same remainder (when divided by 100) as the number chosen by the prisoners for 'the boss', based on the imprisonment date.
Now the strategy is simple, each prisoner assumes he is 'the boss' and makes his guess: by computing the sum of the other 99 (modulo 100, resulting in a number between 0 and 99) and subtracting that from his number based on imprisonment date. If the number is zero or negative, he adds a 100 to it and that would be his guess.
At least one will make the correct guess.
No comments:
Post a Comment