Excellent Math Riddle

Post Reply New Topic

I’d think a wizard using his voice to communicate anything but his guess would be cheating

In fact, this allows a trivial solution for 999 wizards to be promoted: each wizard enunciates his guess with a high pitch if the next wizard’s hat number is greater than the wrong option he’s relaying him, and with a low pitch if it’s less. The first wizard can choose either of his two options at random. All the remaining wizards will guess right

The numbered hats are placed randomly, meaning that there may or may not be any sequence to the numbering of the hats. Everyone here seems to be working from the premise that the numbers have some sequence to them which is NOT what I read in the original riddle. So the probabilities that everyone here have postulated seem way, way off.

It's not about the sequence. Somberlain's strategy for solving 500 works under all hat assignments because the odd/even refers to sequence of wizards guessing (Wizard 1 is odd, Wizard 2 is even, etc.) I think everyone understands the random assignments.

Unfortunately it is.



First, there is no need to use a high tone/ low tone cheat. If the sum goes over the 1001 boundary, he can simply subtract 1001 from the result and say it, I tried to express it in my previous post. http://en.wikipedia.org/wiki/Modular_arithmetic If other wizards learn this beforehand, they can understand which two should be eliminated. For example, let missing numbers be 78 and 1000. Our first wizard should say 77. In every step, there will be 3 unknowns again,and only two of them can give this solution. Check it.

But, this is valid if the wizard with the ''robbed'' number can stay silent. Take a look at his situation: he would be left with 77 78 and 1000. He can't say 77. If he says 78 or 1000, he eliminates one of the unknowns. Lets say he choose to say 78 and the wizard after him has the hat number of 298. The wizard after him would only have two options: 298 and 1000. At this point, he can consider preceding wizards' guesses, but there can be many combinations giving the summation value, since the number of unknowns can rise to hundreds.

But, if he can stay silent, other wizards can understand that he pulled the shortest straw, and they can move on.

I like the way you solve the 'sums over 1001' problem (even though some might consider it cheating), the only problem I can see occurs with the wizard whose number was taken by the first wizard.

The sum method works by each wizard eliminating all numbers in front of him and all guesses behind him (except the first guess) leaving him with three numbers, which are the missing number, the number of the first wizard and the number on his head. He uses the sum given by the first wizard to figure out which is his number.

But if one wizard guesses one of the two numbers that make the sum, all following wizards would then eliminate this number. Instead of looking at the three numbers they should be, they would be looking at 1. the number on his own head, 2. either the missing number or the first wizards number (depending on which was guessed earlier) and 3. the sum itself. All other wizards eliminate the sum by seeing it in front of him, but wizards that come after the wizard with the sum on his head can't do this.

As an example: A wizard looks ahead and listens to previous guesses to eliminate all numbers except 4, 7 and 10. He knows from the first wizards guess that the sum is 10, but 4+7=11, not 10, so he can conclude that the wizard with a 10 on his hat must be behind him. The problem is that he now doesn't know what the other number that the first wizard used was. From his perspective, the first wizard could have used 7+3 to guess 10, in which guess he should guess 4, or the first wizard could have used 4+6 to guess 10, in which case he should guess 7. If both 3 and 6 (the potential 2nd numbers that the first wizard had) have been guessed by wizards before him, he doesn't know which of those wizards was making a genuine guess and which was intentionally guessing incorrectly as he had the sum on his head.

An obvious solution would be to have the wizard with the sum on his head, who intentionally guess one of the numbers used in the sum, to guess in a high voice so that the others know what he is doing. That makes two wizards bending the rules, instead of just one

The problem is that it increases the odds only for certain distributions of hats. There are some distributions where the entire thing is random.

As soon as the number of another wizard's hat is the same distance from one of the first two numbers as the two numbers are apart, it becomes nothing more than random guessing from then on.

If you can use the tone of your voice, then why limit it to a binary value? Why not encode the entire range of 1 to 1001 itself so that you can convey one number explicitly and the second in the way you say/sing/shout/whisper/... it?

I haven't read every other post, so apologies if this has already been suggested...

Here's how it would work, and the wizards agree as such before hand...

The first wizard will say the number of the hat on the wizard immediately in front of him. Thus the first Wizard's "guess" is incorrect. The 2nd Wizard will guess the same number that the first wizard says, which he knows now to be his hat.

The 3rd wizard says the number of the 4th Wizards hat. The 4th wizard guesses this number.

And so on. This way, half the wizards guess correctly.

A wizard cannot repeat another wizard's guess.

The problem with this solution is that the wizards are not allowed to repeat any of the previous wizards' guesses.

Yes.

First of all, let's change the problem just a bit. The change is cosmetic but aligns the problem a bit better with mathematics.

Instead of numbering the hats 1 to 1001, let's number them 0 to 1000.

Better yet, let's make it a bit more general and have N wizards with N+1 hats numbered from 0 to N where N is an even number. For N=1000, then we have 1000 wizards and 1001 hats numbered 0 to 1000. Note that it doesn't make any real difference whether we number the wizards from 0 to N-1 or from 1 to N. Without loss of generality, let's leave them numbered from 1 to N.

Why the change in numbering the hats? Because we can use true modular arithmetic.

If we start by 1, we can't use true modular arithmetic but must fudge it a bit. For example, if N=1000, then we are doing arithmetic mod 1001. What is 500+501? It is 0, not 1001 and there is no hat 0.

By numbering hats 0 to N (0 to 1000 for N=1000), then modular arthmetic works properly.

From now on, we are doing N+1 modular arithmetic. So when we say x+y, we mean x+y mod N+1.

Now that that's out of the way, note that for any even number N, we will be doing arithmetic modular an odd number. For any given distinct numbers x and z, there will be one and only one number y such that x+y = z.

Also, note that for each hat a, there is a hat N+1-a such that a+(N+1-a) is zero. That is N+1-a is the additive inverse of a and a is the additive inverse of N+1-a. We will denote the additive inverse of a as "-a". For example, if N=1000, the additive inverse of 10 (or -10) is 991 since 10+991=0.

Thus when we see hat a-b, that is a plus the additive inverse of b, a+(-b). For example, if N = 1001, then 25-10 = 25+(-10)=25+991=1016 mod 1001=15 and 10-25 = 10+(-25)=10+976=986.

So the first wizard to guess, the one at the back of the column of wizards, adds the two numbers he doesn't see and guesses that number. Assume that the numbers he doesn't see are a and b, then he guesses the number a+b.

The next wizard notes that he doesn't see three distinct numbers. a, b, and c. Assume that none are hat 0 -- we will discuss that a bit later. The wizard knows the sum of a and b. All he has to do is try at most three additions to determine that the two numbers are a and b and so he selects c which is his number. The next wizrd doesn't see a, b, c, and another number d. Since the number c has already been called, it is no longer under consideration and so he has to choose from a, b, and d. Once again, only a and b add up to the number a+b. (If a+d were to equal a+b, then set it up as a+b=a+d, subtract a from each side and you get b=d which is not allowed since no two hats have the same hat number.)

And so it keeps going this way.

Sooner or later, a wizard will be wearing the hat a+b. So he sees that hats a, b, and a+b are not accounted for. Since the first wizard chose a+b, this wizard can only choose either a or b. Assume without loss of generality that he chooses a which is wrong. Of course, we knew this would happen and it isn't any big deal.

But now everything has changed for the future wizards. The next wizard does not see hats b, a+b, or the one he is wearing which is c. He immediately recognizes that b+(a+b) is not equal to a+b. If c is not hat 0, then neither c+b nor c+(a+b) is equal to a+b. The only thing that can explain this is that someone else has hat a+b and he has to choose from hat b or hat c. Remember that for any x and z, there is a number y such that x+y=z. Since the first wizard called out a+b, if the current wizard sees the hat a+b-c ahead of him, then his hat has to be hat c.

But if hat a+b-c has already been chosen, he is in a dilemma. Since both hat a and hat a+b-c has been called, then either of the two hats b and c could be correct. There is no way to do anything but actually guess with a 50-50 chance of getting it wrong.

What about the case where he is wearing hat 0? Then he has a choice between hat b and hat 0. Hat a has been chosen and so hat b could be the other one in the pair to form a+b. Hat a+b has been chosen and so hat 0 could be the other one in the pair to form a+b. In either case, he has an actual 50-50 guess between hat 0 and hat b.

Now how about the special case where either the hat not worn or the hat worn by the first wizard is hat 0. Then the two hats seen as missing by the first wizard are hat 0 and hat a. He calls out 0+a or a as his hat and has a 50-50 chance of getting it right. The next wizard is wearing hat b and has a choice between 0 and b. Since the first wizard called out hat a, and since both 0+a is a and hat b-a is visible, then he must be wearing hat b.

Sooner or later there will be a wizard with hat c for which the corresponding hat a-c has already been selected and is not visible. This wizard will be faced with a choice of 0 or a-c and will not be able to determine whether the first wizards choice was between hats 0 and a or between hats a-c and c. Thus, he cannot know from the preceeding choices whether he is wearing hat 0 or c and will have to randomly choose between the two guesses. Note also that this will occur before N/2 of the wizards have made their guesses.

Thus, if the wizards adopt a strategy of having the first wizard call out the sum of the two hats he doesn't see, there will always be some number of wizards who will not be able to determine their hat based on the information given by the choices of the previous wizards.

Note that if you go back to numbering the hats 1 to N+1, you will essentially have the same situations. The only difference is that the mathematics is a bit confusing because you are are mixing mod N+1 arithmetic with regular arithmetic.

Also note that the attempt to convey information by the tone of the voice will, at best, in addition to being a cheat, act reduce the number of times when a wizard must guess, but not by much. There will still be plenty of situations where wizards will not be able to determine their hat number and will have to guess.

Thanks. I did mod 1001 (or mod 1000) and I constructed a set of hat assignments on notepad. I see a similarity to this problem and the problem of a clock. How do you express whether it is 1pm or 1am on an old clock? I felt and still feel that there needs to be some new dimension to the communication or guesses in this problem but I'm running through other strategies and as Soberlain said, I feel like 998 is unsolvable without the second wizard being able to remain silent.

Wizard 1* [ 5, 1000] mod 1001: 5 + 1000 = 4 thus guesses 4.
------------------------
Wizard 2 [99, 5, 1000]
Wizard 3 [10, 5, 1000] These wizards can guess their hat value by process of elimination regardless of distribution.
Wizard 4 [37, 5, 1000]
---------------------------
Wizard 5* [4, 5, 1000] This wizard is unable to guess his hat value though he knows it.
---------------------------
Wizard 6 [769, 5, 0] This wizard sees a different sum than Wizard 1 stated and calculates the sum of his values with the guess of Wizard 5.
Wizard 7 [16, 5, 0] This wizard sees a different sum and can discern his hat value by calculating against the sum two steps back.
Wizard 8 [236, 5, 0]
Wizard 9 [690, 5, 0]
Wizard 10 [800, 5, 0]
Wizard 11 [33, 5, 0]
Wizard 12 [12, 5, 0]
Wizard 13 [205, 5, 0]
Wizard 14 [113, 5, 0]
Wizard 15 [800, 5, 0]

I wonder if there is a strategy or algorithm the wizards can apply that would allow them to determine their hat value but it's unlikely and the unknowns are a problem under certain distributions. How can subsequent wizards after wizard 7 determine that 5, 1000 were the two missing sums. Maybe it is possible to discern that 5 is the recurring value but I haven't found it.

Being able to stay silent doesn't help. The more hat numbers are not eliminated, the sooner that there will be ambiguities.

If he says his guess in a different manner somehow then the other wizards can calculate the sums of each of their values against his guess and know that 5 is the recurring number unassigned and everyone will know their number.

Being able to convey additional information from the way something is said is completely contrary to the spirit of the problem.

And if they can communicate information by how they say the hat number, it would be relatively trivial for someone of their powers to be able to indicate another hat at the same time.

For example, the first wizard could make a selection from the two hats he can't see and announce the number by taking as many seconds to say the number as there are in the hat of the person in front of him. (Assume really big lungs.) The person in front merely needs to determine how many seconds it took to learn his number and then says it using the number of seconds for the hat number in front of him.

Here's a simple example of where it fails to stay silent.

First, assume that the hats are numbered 0-1000 and that all additions are mod 1001.

Suppose that hat 999 is not being worn and that the first three wizards to guess have numbers 12, 10, and 0 in that order.

The first wizard sees that 999 and 12 are missing. So he adds them together to get 12+999 = 10 and says the number 10.

The second wizard doesn't see hats 10, 12, and 999 and concludes that his hat must be 10 but that it is already taken so he stays silent.

The third wizard doesn't see hats 0, 10, 12, and 999. The problem is that 0+10=10 and 12+999=10. What number is he going to call out?