So i was doing one of the question's of TOURNAMENT OF THE TOWNS and I was not able to understand the solution given by them. The problem is:

The King decided to reduce his Council consisting of thousand wizards. He placed them in a line and placed hats with numbers from 1 to 1001 on their heads not necessarily in this order (one hat was hidden). Each wizard can see the numbers on the hats of all those before him but not on himself or on anyone who stayed behind him. By King’s command, starting from the end of the line each wizard calls one integer from 1 to 1001 so that every wizard in the line can hear it. No number can be repeated twice. In the end each wizard who fails to call the number on his hat is removed from the Council. The wizards knew the conditions of testing and could work out their strategy prior to it.Can the wizards work out a strategy which guarantees that at least 999 of them remain in the Council?

The solution I worked out was to sum up all the number's the last wizard can see mod(1001) and speak that number .This will help every other person know there hat number But the solution tournament of town used had a 50% chance for the last person. Their solution is:

The 1000-th wizard does not know two numbers, his and on the hidden hat. There are two ways to order these two numbers. In one case the permutation of all 1001 numbers is even, in the other case it is odd. According to the preliminary agreement the 1000-th wizard calls the number that makes the permutation even (with 50% probability to be wrong). Now 999-th wizard also does not know only two numbers, his own number and the number on the hidden hat. He arranges these numbers so that the resulting permutation is even and calls the corresponding number. His answer is indeed correct since the permutation he made in his mind coincides with the permutation defined by the last wizard, which correctly reflects the number of the 999-th wizard. In a similar way, all the others wizards calculate their numbers. Consequently all wizards but probably the last one will deliver correct answers.

Now what i do not understand is what do they mean by a even permutation

  • 1
    $\begingroup$ @hardmath sorry for question not being clear . What I really wanted to know was why the parity will be odd for one number and even for other . I already read this definition somewhere but i was not able to deduce how they are stating the answer through this definition . It would be better if you can explain me the whole answer . Thank's $\endgroup$ – Kashish Garg Jun 28 '16 at 16:05
  • $\begingroup$ That helps to clarify what you want to know, but it would be best to edit the clarification into the body of the Question. In many cases problems that feature a large number ("one thousand") items are easier to grasp by doing a small example. Here, consider the case of three hats and see if the extra knowledge (is permutation even or odd?) would get the solution with 100% chance. $\endgroup$ – hardmath Jun 28 '16 at 16:11

Let's call the action of trading two numbers i a permutation a "swap". Thus from $1,2,3,4$ you can reach $2,1,3,4$ or $3,2,1,4$ by making just one swap, but you could not reach $1,4,2,3$ with one swap.

An even permutation is one that you can reach from the identity permutation using an even number of swaps. An odd permutation is any permutation which is not even.

WIth this definition, an even perutation applied to an even permutation, or an odd applied to an odd, results in an even permutation.

Now look at the situation if the 1000-th wizard Gandalf sees all the numbers except (say) 1 and 2. BY prior agreement the missing hat is placed at the end of the line, so if Gandalf has the number 2 hat, the total permutation parity is even only if the pemrutation parity of the hats on wizards 999 thru 1 is even. So if that permutation is even, Gandalf will guess 2; otherwise he will guess 1.

Now we come to the 999-th wizard, Harry. Harry doesn't see his own hat $H$, and he also doesn't see the hidden hat and Gandalf's hat. But say Gandlaf guessed two; Harry knows that his own hat is not number 2. That leaves only two possibilities for his hat. Here we come to a flaw in the explained answer: Harry assumes Gandalf was right, adn fiugres out what his hat has to be on that basis. (This is possible because if Gandalf is right he has exactly two possible guesses, and they are swaps of one another so one leads to odd and one to even.) Obviously, if Gandalf was right, Harry will be right as well.

What if Gandalf was wrong? Then the overall permutatoin was odd, not even. And harry has th e wrong hat in mind for Gandalf, so when he tries to make the permutation even, he iss off by the swap of two hats. So he reaches the same (erroneous) odd permutation, which means that his own guess is right.

The next wizard has the same analysis: He assumes Gandalf was right, he knows Harry was right, and the computes based on his assuption, which always gives him the right guess.

And so forth.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.