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