/sci/ - Science & Math

In a tower where 1000 wizards live is held a trial that goes like this: the 1000 wizards are ordered in a row, and 1000 hats are randomly placed on their heads numbered between 1 and 1001, non-repeating. The wizard who successfully guesses the hat on his head gets promoted to an archmage.

Wizards are allowed to hear each other's guesses, but not the correctness of a guess. In addition they can cast an x-ray vision spell that allows them to see all the hats in front of them (but not those behind them). Lastly, and importantly, no two wizards are allowed to say (guess) the same number.

They are allowed to decide on a strategy beforehand.

(a) Show that at least 500 wizards can be promoted with certainty.
(b) Can 999 wizards be promoted with certainty?