Excellent Math Riddle

Post Reply New Topic

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 wizards are not allowed to see the value of the extra hat. 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. The guessing begins with the wizard in the back who can x-ray 999 wizards in front of him.

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

I added the assumption that no wizard can posit or guess a value greater than 1001.

I love this riddle.

Last edited by aequitas1 on 11 May 2013, 11:36 am, edited 1 time in total.

Do we assume all wizards want to be Archmages? I just realized, if I really hate someone in front of me I could say his number; I'd certainly lose that way but he would too, and it may also screw up with everyone else's guessing.

An early examination tells me that in average 500 wizards will pass the test, but I haven't gone further than that yet. Good one.

I've heard another version of this riddle before (but never got the answer).

Anyway, it could go like this:
The back wizard (the one who can see the other 999 in front of him) can guess his number correctly, by process of elimination.
After hearing his guess, the wizard directly in front of him (who can see 998 wizards) can, by process of elimination (the 998 he can see and the one guess he's heard, which he knows is correct), also guess correctly. And the same goes for the 997th wizard, and the 996th, and the 995th...

Of course, this answer assumes that all the wizards have enormous powers of memory--but hey, they're wizards, right?

EDIT: Oh, I can't count, there's 1001 hats! So I suppose with the above strategy, about 500 would get it right...

Last edited by physicsnut42 on 11 May 2013, 7:56 pm, edited 1 time in total.

lets reduce it to ten.

Ten wizards sit in a row.

The judges have eleven hats.

But wait..

Lessee they only have TEN hats.
Each of the ten wizards gets a random hat.
No extra hat remains.

They start with the first wizard in the back.
He sees all of the nine hats in front of him. So by the process of elimination he knows that the one number he doesnt see has to be the one on his own hat. So he guesses the right number and wins.

Wizard number two sees all of the eight numbers in front of him- is forbidden to guess the number he heard number one guess so that only leaves the one number left- the one number that is actually on his hat. So he makes the winning guess (no guess at all) and wins. And so on. One hundred percent of the wizards would win!

Okay-lets go back to ten wizards and eleven hats ( to make it equivalent to the problem in the OP).

Each wizard gets one random hat, leaving one unused hat.

Each wizard can see all of the hats on the guys in front of him, but not his own nor any on the guys behind him.

They start with "wizard number one"- the guy farthest back.

He sees all of the other nine guys' hats. So out of eleven possible numbers only two are missing. That number on his own hat, and that on the extra hat.

He doesnt know which is the number on his own hat. So he has to guess, but his odds are fifty-fifty.

The next guy (wizard two) sees the hats in front of him. He heard wizard number one's guess ( so he knows that that number cant be on his own hat because he knows that wizard one would not have guessed that number if he had seen it on any of the remaining 8 wizards- but it doesnt matter because the judges wont allow him to guess a previously guessed number anyway).

So wizard number two knows 8 numbers not to guess, and is forbidden to guess a nineth number (which he wouldnt have guessed anyway). So that again leaves two possiblities. So wizard two also has to win a fifty-fifty guessing game.

Wizard three sees seven hats, and is forbidden to guess two numbers- thus nine are eliminated. That leaves two possiblities. Again- a fifty-fifty cointoss.

And so on down the line.

So if each wizard operated on his own (without a group strategy) then each wizard has a fifty-fifty chance. Not a guarantee that exactly fifty percent will actually win. But thats how to bet.

There might be some way to up the odds if the wizards are allowed to cooperate beforehand on a strategy. Have not figured that out yet.

Last edited by naturalplastic on 11 May 2013, 8:23 am, edited 1 time in total.

naturalplastic: The OP did state that the wizards were allowed to strategize beforehand. And anyway, assuming all the wizards actually wanted to become Archmage, above all else, and that they all knew that each one of them shared this desire, no prior planning would be necessary. The 999th wizard would guess correctly, and then the 998th wizard, knowing that the 999th wizard must have guessed correctly, would not have needed any prior arrangements to know what his guess should be.

No. The first wizard sees 2 missing hat values and the process of elimination results for him in a .5 probability of correctly guessing which of the two missing values is on his head.

I solved for 998 wizards with certainty but I will wait to delineate how I did so as I'm waiting to see if anyone can solve for 999.

The 500 wizards isn't too difficult if my quick analysis and resultant conclusion are correct. I focused on the 999 because it was more interesting.

Assume that the wizards practice a utilitarian-based strategem that would promote the highest amount of wizards possible and pay zero attention to the average or a resultant probability that the wizards under a continual and inherited .5 probability attempt at guessing the value of their own hats. I say that this ought to be ignored because it doesn't prove 500 with absolute certainty.

Yes- you assume that each wizard wants the honor, and is trying to maximize gain. Its a mathematical problem, not a agatha christie murder mystery in which you try to devine hidden motives.

you have tried to complicate a puzzle to make it harder to work out, but in the process, you have made the puzzle easy to calculate.

wizard 1000 sees every hat in front of him and the number between 1 and 1001 that is not seen on a hat by him must be the number on his hat.
the person in front of him who also has the ability to see every hat ahead of him can ignore the number on the hat behind him as a possibility to be his own answer considering the rearmost person will be correct. if he can see all the all the hats in front of him, he can calculate what number will be on his hat since all the hats he sees will not contain 2 numbers (since one is already taken)
and the remaining unseen number must be the one on his cap. the process inevitably resolves itself so that every person correctly identifies what their hat number is.

Not really, there are 1001 hats and 1000 wizards. So the first wizard will have to choose between two numbers, and if we keep the iterative process as you described it, every wizard afterwards will have to choose between two hats as well. That's where I got that, on average, half of the wizards will guess their number correctly, but as the OP said that is not the best angle to approach this problem.

Yes.

If the number of hats were equal to the number of wizards then ( assuming the each wizard had a photographic memory for a thousand guessed numbers) then each could easily figure out ,and 'stand and deliver' his own number correctly.

Its that one extra hat that turns it into a fifty-fifty guessing game for each wizard (regardless of his place in the order).

But as shatbat said- the OP seems to know some trick to up the odds in favor of MOST of the wizards that involves pre-game collusion between the wizards on a strategy.

So that strategy is what we have to figure out.

Last edited by naturalplastic on 11 May 2013, 10:10 am, edited 1 time in total.

since the first wizard can see every other hat, they will successfully eliminate every hat except their own from the list of possibilities of the number on their hat. so will everyone else if they are equally intelligent as the sequence progresses.
.

The first wizard can see all 999 hats in front if him. There are 1001 hats. Therefore, the first wizard doesn't know about two hats: his own and another one (with 1001 hats and 1000 hats there will be one number that doesn't appear in any hat). That first wizard takes a guess, he may be correct or he may be not with a 50/50 chance. Then it is the turn of the second wizard: he sees all 998 hats in front of him, and he knows with certainty that the number his predecessor said is not in his hat, therefore he knows 999 numbers that are not there out of 1001; again, he has a 50/50 chance to guess the correct number. This process is recursive, you'll likely understand how it goes until every wizard makes their choice, all with a 50/50 chance.
The true answer to this problem must lie elsewhere

the wizard that is the the wizard that springs from naught wizards is the naughth and also the first wizard,

the numerical system springs from zero. zero is considered to be the first element in a series. and since it is the first element it is counted as "one".

It is indeed late in Australia. The problem specifically says the numbers go from 1 to 1001, therefore there are 1001 different numbers. There are 1000 wizards, I could ennumerate them from 1 to 1000 or from 0 to 999, it doesn't really matter, there is one less wizard than possible numbers.