/sci/ - Science & Math

For details, this riddle appeared in the Tournament of the Towns competition (http://en.wikipedia.org/wiki/Tournament_of_the_Towns)) where it was worth 12 points: the most they ever awarded for a problem.

Get together in groups of two and have the guy in front of you tell you your number?

100% succes

>>5662652
if he just tells you your number you can't guess it on your own turn, obviously

See, this is tricky because one number would not show up, otherwise they could just use elimination

If the wizards can hear other guesses can they identify the position of those guesses in the line?

On which end does the guessing begin --the back or the front?

If it begins in the back then the first Wizard's guess will be correct because he can use the process of elimination. Then the one in front of him can do the same, after hearing the guesses before him and seeing those in front of him and so on allowing all Wizards to be promoted.

I must be missing osmething here, in what order do they guess?

>>5662667
I think without the detail that guesses can't repeat, it would still be trivial: have the first wizard say the sum of all the hats he sees mod 1001.

>>5662643
I didn't read through the whole message but I suspect it's related to this
http://xkcd.com/blue_eyes.html

By the way, what's the answer to OP's pic?

>>5662671
OP here, they can infer the position in the line because they hear all the guesses sequentially.

The trial begins with the furthest wizard to the back.

But your solution isn't correct because the first wizard cannot use the process of elimination: there are 1001 possible hats and only 1000 wizards.

The wizard at the back can see the 999 numbers in front of him, leaving him with 2 possible numbers for himself. So he'll need to choose first, and choose in a way that communicates to the adjacent wizard (and maybe all wizards?) which of his own two choices is best.

Dunno what, though.

>>5662676
The picture is actually an equally difficult, but more IQ-ish riddle. I haven't been able to solve it.

(a) Split up into 2 groups. Have group 1 use x-ray on group 2, and guess all the numbers that do not appear in group 2. Then have group two use x-ray on group 2; elimination will do the trick.

>>5662684
Of course I haven't listed the possible answers so nobody here would be able to solve it either (or they could, but it wouldn't count because their answer wouldn't be based on the possible patterns that can be inferred from the answers).

>>5662685
this doesn't work because there are 1001 hats.

>>5662680
I knew my answer was too good to be true and I misread the amount of hats. It would have been easy that way.

I'm trying to figure out the optimal strategy but whatever successful strategy the first wizard employs will allow the second wizard to eliminate but the unused hat and the first wizard's hat allowing the chain of elimination to occur for all possible Wizards.

Unless the displacement of the remaining hat occurs with the last wizard.

Wizard 1 see all hat but his own and one n/a hat
He takes one for the team and says 1XXXXYYYY where XXXX and YYYY are the 2 hats he didn't see.
Now all other wizards know what to say and he didn't ruin anyone's else guess

999 get promoted

Otherwise they all have a 50% chance of guessing right and roughly 500 make it.

>>5662680
>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.

Nevermind. It said 1000 hats but then said numbered 1-1001.

>>5662698
OP here. The guesses must be actual guesses, i.e. numbers between 1 and 1001.

>>5662702
Does not say that in the question

>>5662707
I didn't explicitly state it. Want a medal?

>>5662711
How so?

It would be easier if it was 101 hats and 100 wizards

>>5662680
I got it!

If the Wizards all agree to "guess" the number on the hats of the Wizard in front of them then 999 would be promoted.

The problem would be of similar complexity involving 2 wizards and 3 hats.

>>5662715
No, in that case the two wizards just decide that the first to guess guesses one number higher than what the next wizard has (and 1 if the next wizard has 3)

>>5662715
The fact it's an even number seems to be important for (a), at least.

>>5662717
No, in that case only the last one would be promoted.

>>5662722
Actually nobody would, because the last one wouldn't be allowed to say the number on his own hat.

(a) Have every other wizard say the number of the wizard in front of him.

>>5662722
If they're all able to agree on a strategy beforehand then they could construct a system of wizards identifying the hats on those in front of them using their x-ray function. First wizard sees the hat on the wizard in front of him and says his number than 999 wizards get promoted with the exception of the first wizard.

>>5662727
correct that, they should go one below or above, selected from the numbers remaining.

>>5662727
The same number can't be said twice, so if I say the number in front of me the next wizard can't say it himself.

>999 wizards

the strategy is to start at the back of the line and work forward. there are 2 cases.

case 1) the last wizard sees 500 even numbers and 499 odd numbers. WLOG he sees 2-1000 inclusive. that means he's either 1 or 1001. he says the larger of the two numbers that he doesn't see (1001).
the guy ahead of him knows that he's in this scenario since the last wizard said an odd number. that means his own number must be even (since before him there are 499 evens and 499 odds). however, since he sees all the even numbers EXCEPT his own, he knows he has the even number which is missing (say it's 1000). he confidently calls out 1000.
the third guy from the end sees 499 odd numbers and 498 even numbers; WLOG he sees 2-998. that means he could be 1,2,1000,or 1001. but the guy behind him is even and the first wizard saw 500 even numbers so he MUST be even too. so he's either 998- but the guy behind him knows that he is 1000 for certain. therefore the third to last guy is 998.
the rest is by induction.

case 2) the last wizard sees 499 even numbers and 500 odd numbers. WLOG he sees 1-999 inclusive, which means he's either 1000 or 1001. he says the even number (1000)
since the second-to-last guy hears an even number, he knows he's in this scenario (otherwise the last wizard would have said an odd number). WLOG he sees 1-998 inclusive. he could therefore be 999,1000,or 1001. however, he can't be 1000 or the wizard behind him would have said an odd number (since then there would be 500 total even numbers; scenario 1). so he's either 999 or 1001. but the last wizard said 1001, so he must be 999.
the rest is by induction.

there you go.

A) is simply one wizard takes one for the other. If a strategy is allowed beforehand they could just simply say "The person in the back will tell said person what his number is but add 1" I.E second last guy has 50 so the last guy says 51. Wizard 51 is disqualified for the wizard numbered 50.

>>5662737
>999 wizards

This is totally a typo on my end, sorry. It's 1000 wizards.

>>5662741
you're saying can all the wizards know for certain?

>>5662740
You can't guarantee that this strategy would work because, for some n, n+1 might have already been said. Consider the ordering: 1 3 2 4 (with 5 possible hats)

>>5662643
Responding to top post for visibility. Some corrections:

1. In (b), it's 1000 wizards, not 999.
2. For clarity's sake, wizards are only allowed to guess numbers between 1 and 1001. Guessing a number is the same as saying it. Also a lot of people seem to be forgetting that guesses cannot repeat (otherwise both sections would be rather trivial, the second one slightly less so).

>>5662752
DISREGARD THIS I SUCK COCKS

I didn't make any typo in (b), fuck me. It's 999 wizards to be promoted from a line of 1000 wizards.

Inb4 nobody is sure what the riddle is anymore.

>>5662643
A simple code is pre-arranged between the wizards (e.g. +2000). Starting from the back, each wizard calls out the coded value of the next person's number, followed by their own, which they know from the wizard behind them. Everybody after the first wizard will thus answer correctly.

This answer feels like it should be disallowed, but it doesn't contradict any of the rules OP has stated. Nowhere is it said the wizards can't talk to each other, or that they're only allowed one guess.

so the person at the back of the line sees the hats of everyone else and provided he has a godo enough eyesight and memory he can deduce which hat is missing and therefore which hat he's wearing, then he says his hat number and the person in front of him does the same, etc.

all 1000 hats.

Of course the question must have meant something different since that's trivially easy but I don't really know what.

>>5662643

The answer to the pic is 2 upward matches, am I right?

>>5662763
"1000 hats are randomly placed on their heads numbered between 1 and 1001"

There are more hats than there are wizards, so the back wizard only has a 50% chance of guessing his hat number.

>>5662737

almost but not quite. let's make this concrete. i'll do it for three different permutations with 10 wizards and 1-11 for hat choices. i used mathematica to generate random permutations.

{1, 2, 11, 3, 4, 9, 5, 7, 6, 10}

each wizard sees all the numbers in front of him. the last wizard sees 6 odd numbers and 3 even numbers. he could be 8 or 10, so he knows he's even. he signals this by guessing the smallest even he doesn't see, 8 (incorrectly).
the second to last wizard sees 6 total odd and 2 total even. he knows he must be even since the first wizard guessed even (see why later). he sees 2,4, so he must be 6,8, or 10. however, he can't be 8 since the guy behind him guessed it. so he's either 6 or 10. if he were 10, the guy behind him would have guessed 6, which he didn't, so he must be 6.
the third to last wizard sees all numbers except 7,6,8,10. 6 and 8 have been guessed, so he's 7 or 10. if he's 10, the last wizard guesses 6; he concludes he's 7.
fourth to last sees all except 5,6,7,8,10. eliminates 6,7,8,10, so he's 5. etc.

{4, 3, 10, 7, 5, 6, 2, 11, 8, 9}

each wizard sees all the numbers in front of him. the last wizard sees 4 odd numbers and 5 even numbers. he could be 1 or 9, so he knows he must be odd. he signals this by guessing the largest odd he doesn't see, 9 (correctly).
next to last sees all except 1,8,9. he clearly can't be 9. is he 1 or 8? if he was 1, then the guy in front sees 6 odds and would have guessed an even number. so he must be 8. the rest follow.

{4, 9, 8, 5, 2, 11, 6, 7, 3, 10}

each wizard sees all the numbers in front of him. the last wizard sees 5 odd numbers and 4 even numbers. he could be 1 or 10, so he doesn't know if he's even or odd. he guesses the smaller of the two numbers, 1 (incorrectly).

>>5662737
So anyhow, this is slick as fuck. It's not the proof I had in mind (it's better) but I don't see a problem with it. Will reserve final judgement for a while because subtle problems tend to pop up with this riddle.

Non-constructive solution for (a):

The first 500 wizards will guess 500 hats that aren't worn by the next 500 wizards. This leaves us with 501 possibilities as to what set of numbers is worn by the next 500 wizards. If we know which possibility we're in, we're done, because the wizards can then guess their hat by process of elimination (501st wizard knows which hat he wears by elimination, 502nd knows which hat he wears by trusting the 501st wizard's guess + elimination, etc).

So how do we discern between the possibilities? Well, there are 500! orderings in which the first 500 wizards can call out their hats, so all we need to do is pick 501 random orderings out of those.

>>5662806
i'd say this is a constructive solution, but we'd be arguing semantics

>>5662687
Humph, without the patterns there's no way to pick the correct solution. Damn you OP!

>>5662764
my guess is six upward matches
am i the correct one?

>>5662755
the last wizard just picks the smallest number he doesn't see.

>>5662825
no

What's the answer to OP's pic?

>>5662790
dude you are smart°_°
really impresisve sollution

>>5662643

OP, when they're ordered in a row, are they forced to guess in that order? So the wizard that has nobody in front of him is forced to guess first?

>>5662903
The wizard that can see all the hats but his guesses first, then the wizard that can see 998 hats, and so on.

>>5662907
why didn't you just copy paste the original text

>>5662907
you forgotten to mention that
i thought the first is the one who cant see anyones hat!

>>5662895
not really. i fucked up somewhere. it looks like it'd work, but there are permutations that give you trouble. still working on it.

>>5662919
you didn't
think about it...
you already solved it but nobody noticed

>>5662920

don't understand at all

>>5662926
neither do i
why wouldnt it work
give a permutation that wouldnt work?

This is a pretty stupid version of the problem, because the hats are only a permutation of the wizards since there are as many hats as wizards and they are distinct. The problem in which there are 1000 wizards but only 100 distinct numbers on the hats, and two wizards are allowed to guess the same number, is more interesting.

It happens that in both cases, you can promote 999 wizards, but in the 2nd case, it requires a tiny little bit of effort, instead of being completely trivial.

Posting my solution before reading the thread. Probably won't bother to read the thread.

>Let S be the sum of all numbers that the first wizard sees on everybody's hat
>Let S(n) be the sum of all numbers that the n-th wizard sees in front of him.
>A(n) is the answer that each wizard says
For every n wizard:
{
> A(n) = S - S(n)
> S = S - A(n)
}

Example with 5 wizards with hats numbered 1-6:
> 2 6 3 4 1

First wizard : 14 ~( 6 + 3 + 4 + 1 )
Second wizard : 6 ~[14 - (3 + 4 + 1)]
Third wizard : 3 ~[(14-6) - (4 +1)]
Fourth wizard : 4 ~[(14-6-3) - 1]
Last wizard : 1 ~ [(14-6-3-4) - 0]

Every wizard has to remember the number the first one calls out and substract the ones being called out to get the sum of all the remaing wizards.

>>5662701
Yeah... this... it doesn't make sense. You can't have "1000 hats" that have the numbers 1 to 1001 on them. Is it supposed to mean that one of the numbers from 1 to 1001 is missing?

The puzzle in the image is far more interesting than your riddle, OP.

>>5663008
you're an idiot

>>5663074
Read it again. The hats are numbered between 1 and 1001, so the number on each hat is between 1 and 1001, and the numbers are all distinct. Doesn't mean the hats have all the numbers from 1 to 1001.

>>5663070
What the hell are you talking about? I'm saying your problem is very simple, and proposing a harder version of it. How does that make me an idiot in any way?

>>5662680
> The trial begins with the furthest wizard to the back.
> Wizards are allowed to hear each other's guesses
> allows them to see all the hats in front of them

The first guy can see all 999 of the other hats. So why doesn't he just guess the one number that's not there? Or is the problem that there's one extra hat? You wording, "between 1 and 1001" is ambiguous.

>>5662737
>>5662790
>>5662806
the only champions here

>>5663072
If you are allowed to say a number above 1001, why don't you just completely encode the whole state of what you can see, without forcing people to wait for what the others said before they can give their number? Sure, it uses O(n) digits instead of O(ln n), but whatever, there doesn't seem to be any constraint on the number of digits used.

>>5663088
You haven't understood the details of the problem and have proposed an inanely more trivial problem instead.

>>5663091
Again, there are 1000 hats, but the number on each hat can be any number from 1 to 1001. The only restriction is that no number appear twice. Thus, the first guy sees 999 hats, but he can't infer what his own hat is from this because there are *two* possibilities.

>>5663096
can you think of any encoding? Remember you are allowed to say only numbers (how do you separate numbers?)

Also the first wizard is going to say either 501501 or 501500. It seems plausible since the human mind can store only up to 7 digits(no trolling here, pls).

You can even make the first wizard make a guess between the 2 numbers that are missing-> the lower denotes 501500, the greater 501501. This way you have a 50% chance of getting all correct and 50% of getting 999 correct. (just as efficient as the guys with the odd/even solution)

>>5663121
If we're allowed to go above 1001, it's pretty easy to give as much information as anyone would like. The first wizard can say: XXXX0000YYYY, for the two numbers that he doesn't see, and then everyone can know their hat.

But even going by the terms of the riddle, and disallowing guesses above 1001, we can still solve this riddle very easily if we allow for repeated guesses: the first wizard can tell us the sum of all the hats he sees mod 1001 (and I'll leave it to you to work out how it goes from there).

The problem arises when no guess can repeat itself, and all guesses are 1 <= x <= 1001.

>>5663121
One second, this only works if you start numbering from 1 or 2. The sum is unknown.
So yeah, you will only get 999 promoted.
The first takes one for the team.

>>5663074
number 0 isn't on any hat

>>5663101
>>5663110

Alright, my bad, I read it as having numbers from 1 to 1000 on the hats.

So, promoting 500 (guaranteed), with an expected 750 promotions.

We apply the common strategy of using the first guy's answer to encode information that propagates to the other guys.

He has two possible answers, and knows that the guy in front of him hesitates between 3 possible answers. Let's call a1, a2 and a3 the 3 numbers between which the 2nd to last hesitates with a1<a2<a3. We now only need a bijective function f that takes as its input the index i in {1,2,3} that corresponds to the a_i that the 2nd to last has, and gives us the index j of the a_j that the last guy has to say (with i and j distinct).

For instance, we can choose f(i)=i+1 mod 3 (taking the modulo in {1,2,3}).

With this choice of f, let's consider an example scenario.

The last guy's hat is 238. The 2nd to last guy's hat is 974. The unused hat is 42.

a1=42, a2=238, a3=974. i=2 because the 2nd to last guy's hat is a2=238. f(i)=3. The last guys will therefore say a3=974 (luckily it means he gets promoted, but it wasn't guaranteed). The 2nd to last guy now knows his hat was <span class="math">a_{f^{-1}(3)}=a_2=238[/spoiler].

The problem is recursively repeated for the next two guys with 2 numbers out of the list (here a2 and a3).

Each pair saves 1 guy for sure and 1 guy with probability 1/2.

>>5663170

this doesn't work though, because in the problem it says that the wizards don't know if other wizards' guesses are right or not

>>5663121
A non-constructive proof that the encoding exists is by saying that there are finitely many possibilities of combinations of 999 distinct hats from 1 to 1001 (basically 1001! / 2 possibilities), so you can encode them by associating each of them with a value from {1,...,1001!/2}. A semi-constructive way to do that is to lexicographically order those possibilities and "count" them. It's still not very convenient. It requires log_2((n+1)!/2) bits, which is O(n * ln(n)) using Stirling approximation of factorial.

A more constructive and easy to use solution is to just let the last wizard build the number that is the sum for k of the 10000^k * h_k where h_k is the number of the hat of wizard number k.

>>5663178
I don't think it actually need to use that.

My induction hypothesis is that the 2nd guy in each pair is always correct, so the other wizards can actually use the fact that that guy is correct.

In the first pair of two wizards, the answer of the 2nd guy doesn't rely on knowing if the first guy was correct or not.

When it propagates to the next pair, they know that neither of the two numbers that were said before are on their hats. Therefore, they don't need to know whether the first two guys were correct or not: they just treat their instance of the problem separately without caring about the correctness of the answers of the guys before they (they only need that the guys before them each answer something in {a1,a2,a3}).

I can detail more if you want, but I'm pretty sure it's correct (for the "simple" target of 500 promotions).

>>5663183
OP has already said the guesses are restricted to numbers not bigger than 1001. You can't encode 1001/2! possibilities with 1001 numbers and no additional information.

>>5663190
I know, I'm only answer in the context of >>5663096:
> If you are allowed to say a number above 1001, why don't you just ...

which basically says that the problem is trivial and not worth working on if the numbers aren't restricted to {1,...,1001}.

>>5663194
Gotcha.

>>5663191
I'm pretty confident your solution is incorrent, mostly because a local bijection is... well, a local bijection, and it might interfere with other bijections further down the line (because guesses can't repeat). I didn't look into it deeply enough to find a counter-example.

There is a non-constructive proof earlier in this thread that I believe to be a correct solution to (a).

I tried a million things, only this makes some sense.

>>5663202
Well, let me try and sketch my view of why it works, tell me which point you think needs clarification:

1) Consider the problem in which 2 wizards each have one of 3 possible hats in {a1,a2,a3}, and their hats are distinct. Wizard A knows Wizard B's hat. Assuming a1<a2<a3 wlog, Wizard A says a_j = a_{i+1 mod 3} where a_i is Wizard B's hat. Wizard B then says a_{j-1 mod 3} = a_i, which is his own hat. Therefore Wizard B always guesses his own hat.

2) Now, to translate this problem with two wizards into the problem with 1000 wizards, consider that the first two wizards are the last two in the line. They can exclude 998 hat values out of the 1001, so they indeed have 3 values among which to choose, and 1) applies. Afterward, the next two wizards see the hats of the 996 people in front of them, and know that the two numbers that were spoken previously aren't theirs either, so they also exclude 998 numbers, so 1) can still be applied. And the same inductively applies for every further pair of wizards.

there is of course a matchbook at the ?-sign. what do you expect where else all these matches are coming from?

>>5663294
Someone told me I was wrong when I said you could make it a 2 wizards-3hats problem. But... They were just wrong. There's no loss by making this. So yeah, that makes it easier to find a solution.

>>5663449
I think some solutions to the 2wizards-3hats problem might not translate directly in a solution to the 1000wizards-1001hats one. This one does, though.

Too lazy to see if anyone said it yet, but the answer is pretty trivial. First guy adds up the numbers of everyone he can see, and takes it mod 1001

>>5663545
We already covered that. It doesn't work because guesses can't repeat, and it might be that the second wizard happens to have the sum mod 1001.

>>5663294
No, that doesn't work, like he said. The possible hats could repeat.

>>5663527
Feel free to name some.
It might seem strange, but as long as there's no counter-proof, it's a fact.

>>5664239
Yeah never mind. I convinced myself. I think it can easily be proven that any solution for (2,3) problem can be extended to (2k,2k+1) with the same rate of promotion.

Actually, any solution to the (m,n) problem can be extended to the (m+k*m,n+k*m) problem with the same rate of promotion.

>>5664230
> The possible hats could repeat.
Sorry what? If you mean that two people can wear the same hat, it's specified in the problem that it cannot happen. If you mean something else, you most likely didn't understand the strategy: after each pair of wizards gave their numbers, the next pairs is leaked 1 "extra" hat number beside the ones on their heads and the ones on the heads of people in front, and they know what the set of 3 numbers (the one on the extra hat and the ones on their heads) is (they just don't know which is where). They are exactly in the same position as the first two guys.

Here's how I promote 999 wizards with certainty.

The dude in the back is screwed. He takes one for the team. He looks at all the hats in front of him, figures out which two he's not seeing (1000 wizards, 1001 hats, one is unused and one is on his head.)

His guess is "I am wearing hat number 1xxxxyyyy, where xxxx is the first hat he can't see and yyyy is the second hat he can't see.

The wizard in front of him then guesses the one hat that isn't one he can see, or xxxx or yyyy. He gets promoted. The next in line guesses the one hat that he can't see, hasn't been guessed yet, and isn't xxxx or yyyy. He gets promoted.

On down the line, and you've got 999 archmages.

>>5664386
Nevermind, I thought you were trying to solve for 999.

>>5664429
This is how we promote 999 wizards with certainty.
Ya get all the wizards standing in a line.
And one wizard looks at the like and calls the number
(a1)0(a2)0....0(a999) where (ai) is the hat number of the wizard i'th places away from the left.
Obviously, all the wizards remember this string since hey their wizards.
And they can easily compute in polynomial time the number on their hat.

GGs.

>>5664501
They are*
Excuse my stupid mistake in an otherwise perfect proof.

>>5664432
Oh, no, I was on the simple case.

I gave a try at the 3,4 problem (3 wizards, 4 hats), trying to guarantee that 2 wizards are promoted at least.

Cheating a little bit with some brute-forcing (which wasn't so trivial to implement, actually), I found a few solutions that I haven't started to try and understand. I'll write one down here and if someone wants to see if they can make some sense out of it and generalize it to save 999 wizards, go ahead.

I list every possible configuration of the hats, and what wizards say. You can manually check that in two configurations in which a wizard sees and hears the same, he also says the same thing (obviously). The format is the following:
a,b,c|d => e f g (h)
where
- a is the hat of the 1st wizard,
- b is the hat of the 2nd wizard,
- c is the hat of the 3rd wizard,
- d is the unused hat,
- e is what the 1st wizard says,
- f is what the 2nd wizard says,
- g is what the 3rd wizard says,
- h is how many wizards were correct (at least 2 here).
Hopefully my code was correct. Let me know if it doesn't work.

1,2,3|4 => 1 2 3 (3)
2,1,3|4 => 4 1 3 (2)
1,3,2|4 => 4 3 2 (2)
3,1,2|4 => 3 1 2 (3)
2,3,1|4 => 2 3 1 (3)
3,2,1|4 => 4 2 1 (2)
1,2,4|3 => 3 2 4 (2)
2,1,4|3 => 2 1 4 (3)
1,4,2|3 => 1 4 2 (3)
4,1,2|3 => 3 1 2 (2)
2,4,1|3 => 3 4 1 (2)
4,2,1|3 => 4 2 1 (3)
1,3,4|2 => 1 3 4 (3)
3,1,4|2 => 2 1 4 (2)
1,4,3|2 => 2 4 3 (2)
4,1,3|2 => 4 1 3 (3)
3,4,1|2 => 3 4 1 (3)
4,3,1|2 => 2 3 1 (2)
2,3,4|1 => 1 3 4 (2)
3,2,4|1 => 3 2 4 (3)
2,4,3|1 => 2 4 3 (3)
4,2,3|1 => 1 2 3 (2)
3,4,2|1 => 1 4 2 (2)
4,3,2|1 => 4 3 2 (3)

>>5664547
Okay, so the reason that works is because there is a function f with the following properties:

<span class="math">f: D\to \{1,2,3,4\}[/spoiler] where <span class="math">D =\{(a,b)\in \{1,2,3,4\}^2 | a\neq b\}[/spoiler]

<span class="math">\forall (a,b)\in D,\ f(a,b)\not\in \{a,b\}<span class="math">

\forall ((a_1,b_1), (a_2,b_2)) \in D^2, if b_1=b_2 and f(a_1,b_1)=f(a_2,b_2) then a_1=a_2.

\forall ((a_1,b_1), (a_2,b_2)) \in D^2, if a_1=a_2 and f(a_1,b_1)=f(a_2,b_2) then b_1=b_2.

f is the function I will use for the 1st wizard, where a and b are the two hats he sees. Because of the last property, whatever the configuration, using what the 1st wizard said (f(a,b)) and what the 3rd wizard wears (b), the 2nd wizard can recover and say a. Similarly, because of the 4th property, using what the 1st and 2nd wizard said (respectively f(a,b) and a), the 2nd wizard can recover and say b.

I think these functions are easy to find and to generalize to most wizards (promoting all except for one). I'll be trying for a while.[/spoiler][/spoiler]

>>5664579
LaTeX-fail. Reporsting.

>>5664547
Okay, so the reason that works is because there is a function f with the following properties:

<span class="math">f: D\to \{1,2,3,4\}[/spoiler] where <span class="math">D =\{(a,b)\in \{1,2,3,4\}^2 | a\neq b\}[/spoiler]

<span class="math">\forall (a,b)\in D,\ f(a,b)\not\in \{a,b\}[/spoiler]

<span class="math">\forall ((a_1,b_1), (a_2,b_2)) \in D^2[/spoiler], <span class="math">if b_1=b_2[/spoiler] and <span class="math">f(a_1,b_1)=f(a_2,b_2)[/spoiler] then <span class="math">a_1=a_2[/spoiler].

<span class="math">\forall ((a_1,b_1), (a_2,b_2)) \in D^2[/spoiler], if <span class="math">a_1=a_2[/spoiler] and <span class="math">f(a_1,b_1)=f(a_2,b_2)[/spoiler] then <span class="math">b_1=b_2[/spoiler].

f is the function I will use for the 1st wizard, where a and b are the two hats he sees. Because of the last property, whatever the configuration, using what the 1st wizard said (f(a,b)) and what the 3rd wizard wears (b), the 2nd wizard can recover and say a.

Similarly, because of the 4th property, using what the 1st and 2nd wizard said (respectively f(a,b) and a), the 2nd wizard can recover and say b.

I think these functions are easy to find and to generalize to most wizards (promoting all except for one). I'll be trying for a while.

>>5664547
You're pretty much on the right track. Also your earlier solution for 500 seems correct (I doubted it yesterday, but I was right before sleep), though there are equally simple solutions that easily have a bound of say, 980 correct guesses (think about how to encode information in sequences of numbers).

Good luck.

>>5664609
I've got a hunch that looking at the signatures of permutations might be a good way to encode information, since basically we always need to identify one out of two numbers, and there are two possible signatures for each permutation, and local changes on permutations usually change the signature. It looks like it has good properties, I'm just not sure exactly how to put it in action.

>>5664429 here. I've improved on my previous certain score of 999.

When the wizards meet to discuss strategy, one of them suggests this: Everyone wear a mirror on the back of your robe.

>>5664631
the number of people who haven't read the thread here is distressing

both your solutions don't answer the specifications of the problem