Excellent Math Riddle

Post Reply New Topic

I thought of a recursive strategy all wizards subsequent to Wizard 5 in my example can use to discern their hat values but when two permutations conflict with respect to sum it get's destroyed. I need to add some kind of additional argument. My immediate reflex is to have the wizards facing these two possibilities use some kind of numerical analysis on previous guesses under the assumption that all but one (wizard 5 because wizard 1 is no longer a factor really) were correct and use the values gathered from the wizards ahead of them and then construct a strategy respecting probabilities but it doesn't work. It ends up in a .5 probability for the wizard(s) facing the conflicting sums.

I feel like the predictive quality of the dopamine in my brain would give me a stronger clue that it cannot be solved.

I'll be stuck on this one forever. lol

Edit: I also wonder if Wizard 5 in my example can somehow express either the higher or lower value to demonstrate something but how would a subsequent wizard faced with two values conflicting discern anything from this? Any ideas?

Let's go over this:

We know that, to guarantee 999 wizards become archmages, the first one has to be the non-guaranteed one.

We know that if the first wizard guesses any hat number other than his two, then he eliminates another wizard.

We know that if the first wizard guesses either of the two proper guesses, all that could be stated as information would be a binary value.

We know that either the first wizard has to clarify the other 999, or each wizard has to clarify the next one.


I'm guessing that the solution would have to involve communicating information in other ways than a straight guess (like the high-pitched voice mentioned earlier). Even higher and lower could have ambiguity.

If the first wizard gives his answer in a Donald Duck voice it means....

If he does an impersonation of Jimmy Cagney it means......

If he does Arnold Schwartznegger it means...........

But the third wizard also knows the planned strategy, and knows that the second wizard would only stay silent if his hat was the same number as the sum give by the first wizard. He knows that the second wizards must have hat number 10, and so eliminates 10 as a possibility for his hat. If we allow one of the wizards to stay silent then 998 wizards will guess right.

The only possible way to get 999 wizards to guess correctly would be if the first one doesn't take another wizard's number.

The first wizard would have to say either "12" or "999" in that case in order for it to be a solution. There has to be a way to convey information just by saying one of the two options.

This. They know that the first wizard gives the average and the wizard with that number stays silent. The number of unknowns stay constant at 3. And from 3 different numbers, there is no way to obtain the same summation by adding up 2 of them. Thus, the 998 solution can be obtained.

And the 999 solution is simply not possible, that is the answer for part (b).

I don't like the idea of ''voice acting'', it has nothing to do with a mathematical solution and all available options should be stated in the problem. Adding extra boundary conditions to the problem after the statement of the problem is kind of cheating. The solution of the problem should be robust. Maybe our wizard with the ''voice acting'' duty have aspergers and he has a monotone voice? Maybe he is blind? Maybe he will intimidate the supervisor and get the archmage title for all?

A wild imagination can solve everything in theory.

I agree that voice acting is bending the rules too far, even if it's just a distinction between high pitch and low pitch, but I'd just thought I'd add that if you take a strict reading of the problem then having one wizard remain silent could be seen as bending the rules as well; the problem as written doesn't explicitly say that every wizard HAS to guess a number, but it's kind of suggested.

In fact I think the cornerstone of our 998 strategy, having the first wizard call out the sum of his two possible numbers, could be seen as bending the rules. Our strategy asks the first wizard to give up a 50/50 chance of becoming an archmage in order to help his peers, but can we assume that a wizard would be so charitable?

That's why I asked whether a wizard can choose to stay silent.

Actually, there is no assumption.


But he did not give any information about using high/low pitch.

After all, it is his question and his imagination. So it is his will.

After some thought, I think that the adding method may be good for 998 wizard promotions after all.

I'll post more later.

First, let's change the hat numbers to 0 to 1000 instead of 1-1001 so that we can use mod N+1 arithmetic as it is meant to be used. We can do the equivalent with hats number 1 to 1001, but it is considerably less natural than just using modular arithmetic

And let's generalize this to N Wizards instead of 1,000 Wizards.

Thus, we will number the wizards from last to first as 1, 2, ..., N. That is, wizard 1 will be the last wizard in line (and first to choose) while wizard N is the first wizard in line and last to choose.

Let the set of hat numbers be H = {h_0, h_1, h_2, ..., h_N} such that the hat worn by wizard i has hat number h_i and h_0 is the number of the hat that is being worn by no wizard.

Let P be the set of promoted wizards. The goal is to make |P|, the minimal number of wizards to be promoted, as large as possible.

We have three possible cases:

1) In the first case, the hat not being worn is hat number 0, i.e. h_0=0.
2) In the second case, the hat being worn by Wizard 1 is hat number 0, i.e. h_1=0.
3) In all other cases, neither the hat not worn nor the hat worn by wizard 1 is hat 0, i.ei. h_0 > 0 and h_1 > 0.

For cases 1 and 2, wizard 1 sees all the hats except for hat 0 and another hat and cannot determine which of the two he is wearing. Let wizard 1 choose the hat that is not hat 0. Thus, if h_0=0, he gets it correct and is promoted, but if h_1=0, he gets it wrong and is not promoted.

For i>1, wizard i will see not see two hats that have not been guessed. One of the two hats is hat 0 the other is the one he is wearing, h_i. Obviously, he chooses hat h_i and is correct.

Thus, if one of the first two hats is hat 0, all but the first wizard will guess the correct hat. If h_0 = 0, then wizard 1 will also guess the correct hat and |P|=N. If h_1 = 0, then wizard 1 guessed the wrong hat, but all the others guessed the right hat and so |P|=N-1.

For the third case, wizard 1 will look and see the hats ahead and see that two hats are missing, neither of which are hat number 0. One of the two will be h_0 and the other will be h_1, but he won't know which. He then chooses hat h_0+h_1 where + is addition modulo N+1.

At some point in the future, some wizard, wizard number j, will not see hat h_0+h_1 and those wizard 1 for i<j will see that h_j, the hat worn by wizard j will be h_0+h_1.

For i<j, those who see hat h_0+h_1 ahead of them, they will have a choice of three hats to choose from: h_0, h_1, and h_i. Knowing that wizard 1 guessed hat h_0+h_1, it is clear that only two of the numbers, h_0, h_1, and h_i can add up to that. For example, if Wizard W_1 didn't see hats 250 and 500, then he would say hat 750. The rest of the wizards would know that wizard 1 said 750. Thus, if wizard i does not see hats 7, 250, and 500, he knows that neither 7+250 nor 7+500 add up to 750 but that 250+500 does add up to 750. So he will select hat 7 which is his hat, h_i and he is promoted.

For wizard j, the Wizard wearing hat h_j=h_0+h_1, he will only have two choices, h_0 and h_1 becasue h_0+h_1 was chosen by Wizard j. If one of the two hats was zero, he would have chosen the other, but that is covered in the first two cases. Here, neither h_0 nor h_1 is hat 0. Here's the surprise -- instead of choosing hat h_0 or h_1, both of which he knows is wrong and instead of choosing hat h_0+h_1 which is his hat but was already chosen by Wizard 1, he looks to the front of the line and chooses h_N, the hat worn by the very first Wizard in line! He is, of course, wrong, and does not get promoted. (Note that if wizard j is the first wizard in line, that is wizard N, then he will choose either of the two hats and get it wrong.)

For each wizard k ahead of wizard j and not wizard N, i.e. j<k<n, he will determine that three hats are missing: h_0, h_1, and h_k. Like for the case for the Wizards 1<i<j, Wizard k can easily determine that h_0 and h_1 are the hat two hats worn by wizard 1 and not worn by any wizard and so he correctly chooses the third choice, h_k.

Finally, for wizard N, his hat was already chosen and his choices are h_0 or h_1. It doesn't matter which he picks -- he will be wrong.

Note that we can have that wizard j above is Wizard N, that is that Wizard N is wearing hat h_0+h_1. In this case, all but wizards 1 and N will be promoted and so |P|=N-2. Otherwise, all but izards 1, k, and N will be promoted and so |P|=N-3.

To sum it up, then: wizard 1 chooses h_0+h_1 and gets it correct only if h_0=0.

At the very front of the line, wizard N will have a choice between two hats. If one hat is hat 0, he chooses the other. Otherwise, he just randomly chooses a hat.

After wizard 1, if a wizard has two hat numbers from which to choose and one of which is zero, he chooses the other hat number.

For any wizard not at the back of the line, if he has two choices from which to choose and neither is hat number zero, he chooses the hat of the wizard at the head of the line unless he is the wizard at the head of the line. Finally, if he has three choices, the sum of two of the choices is the hat selected by wizard 1 and so he chooses the third choice.

Thus we have an algorithm for |P|=N-3.

Don't know if this has been solved but 999 wizards can be promoted with certainty because they can all see the numbers in front of them. The wizard at the back of the queue AND at the front of the queue has a 1/2 chance of getting his hat wrong. Since every wizard past that point may assume that their hat has been seen and thus is not being guessed, they may correctly deduce their hat number from those that have been said and those that have not been said.

Thus 999 guesses can be guessed right. However the 1st or 1000th guess has a 1/2 chance.

You don't really need advanced maths for this or probabilities. It's just a case of ordering and the concept that in a straight line with the wizards facing one direction, there are only two wizards will not guess the pattern - the first and the last.

I don't understand where the extra hat is - is one of the wizards wearing two hats? Is one hat not in the room? I can comprehend everything else, but I somehow missed the location of the extra hat at the start of the contest.

One hat is set aside an no wizard is able to see what the number is on the hat. Think of it as being in another room. Therefore, the first wizard can see every hat but two: the hat he is wearing and the hat noone is wearing.

K, thanks. Ok, so... the first wizard can hold 999 numbers in his head and identify the missing two. From that information, he has reduced his guess to a 50/50 coin toss.

The puzzle posits that the wizards can hear each other's choices, but not the correctness of the choice. I'm going to assume that these are all sentient wizards, occupying a real room, though, and can walk around and such.

So, in my first scenario, the first wizard takes a guess, and either is right or wrong. Each of the other wizards can, once they have heard his guess, determine by looking at the number on his head whether or not his guess was correct. This subverts the assertion that the wizards cannot hear whether a guess is correct or not, but since the riddle is composed of wizards, rather than dumb hat-reading automata with no free will of their own, I'm taking that. I'm still not sure it's gonna help me any, but I'm taking it anyways.

I'm gonna decide, since I'm a deity here, that the missing number is 87.

Wizard #100 looks at the group and determines that he is either 87 or 100. He decides to guess (since the proof asked for requires only 999 Wizards, I'm assuming that the first wizard always guesses - could be wrong about that, and I have a few ideas if this doesn't work) number 100, all the other wizards hear his guess and see his number, determine that his guess was correct... and the remaining 999 Wizards, each in succession, are left with the same 50/50 coin toss.

Now, my understanding of statistics is that based on each successive wizard making the same 50/50 guess, it should allow about half of them to pass - does this satisfy the first part of the riddle? I suspect not, since you asked for certainty, and something in my head tells me that statistics do not provide *certainty* - only a high degree of probability. But I don't know statistics, beyond the basic idea that a bunch of coin tosses will average out half and half.

So that *might* have solved the first part, or else I'm just barking up the wrong tree... though I suspect that a statistician would probably insist that he had theoretically provided a way for 500 wizards, on average, to pass each examination.

So now I assume that the first wizard guessed wrong, and each of the wizards has now seen, plain as day, that the number he guessed was not the number on his head... well, each of those wizards, I am again assuming, has that aspie-like facility for tabulating nearly a thousand individual numbers and identifying the missing two. In such a case, in my scenario, here's what we do:

-The first wizard deduced that 100 and 87 were the missing numbers, guessed 87, and thus identified the missing hat to all the other wizards. He will not pass, but 999 other wizards can now stand at the back of the group, each in turn.

So next comes Wizard #674. HE stands at the back of the group and determines that #87 and and #674 are the missing two numbers in his case. He knows 87 is wrong, because 100 guessed it and he's 100.

At this point, I think you'll agree that by the stated rules of the puzzle, it is now possible for all 999 remaining wizards to pass - in each case, they determine the missing number that is not 87, and they pass. If any particular wizard, when it comes to his turn, does not actually *want* to pass, he could deliberately choose 100, which has not been guessed yet, but is known to not be the number on one's own head, because it's over there on #100's head.

Yes?

No.

The last wizard can see 999 out of 1001 hats. If he guesses one of the two hats, he may or may not be correct.

The next wizard can see 998 out of 1001 hats and also knows what hat was guessed by the last wizard. That gives him two choices. One of the choices is the hat not guessed by the last wizard, but he has no way of knowing which of the two hats that could be. So he can randomly choose one hat.

And so on.

Thus, if they just guess, they could all be wrong and thus |P|=0.

Also, they aren't allowed to pass. They must provide a valid number for a hat that has not already been picked.

And they don't take turns standing at the back of the line. The line is fixed. Each wizard can see only those hats in front of him. The wizard at the front of the line can see no hats at all. No wizard ever gets to see the hats of any wizard behind him at least until it is over.

Thus, no wizard will see what the last wizard in line is wearing because everyone else is in front of him. Wizard 100 can only see the hats of wizards 1 to 99. Wizard 99 can only see the hats of wizards 1 to 98. For any N>i>0, wizard i can only see the hats of wizards 1 to i-1.

Ok, I misunderstood. You also described them as a "row" in your initial description, so I didn't see them as a line, just a bunch of wizards in a room playing a mathematical version of that "who am I" thing people play at parties. I'm terrible at math, so if they're chained in place I'm probably not gonna solve this. :>

(did this get solved further back in the thread?)