Most of The Time

Time to solve out the hat problem from last time. There are probably a reasonable number of forms of the solution, but I suspect that they are all equivalent to the one I am about to give.

First of all, consider one of the three people (I will name this person Bob), he must have some strategy on when to guess and when to pass. Guessing all the time or passing all the time must each be non-optimal, since any guess has only a 1/3 chance of being right, you want to ensure that your guesses line up with your partners guesses in such a way that you are all wrong together, but you are right alone. Clearly the only trigger on when to guess must be the other players hat colours, so let us assume that Bob will guess when we see that the other two hat colours are the same, and he might as well guess that his hat is of the same colour (this is possibly not the most general solution, but I think most other forms of guessing for the first person can be mapped onto this isomorphically).

Bob will assume that the three hat colours are the same, and if that is not possible, he will pass.

Next, consider Alice, she will look at the hats that Bob and Eve are wearing (I'll just name people on the fly now). Bob will guess if Alice and Eve share a hat colour and in that case he will be guessing right or wrong and Alice can do nothing about it. So Alice may as well assume her hat colour is different from that of Eve, since if it is the same Bob is going to be guessing anyway. A reasonable guess for Alice is to guess her hat colour is the same as Bobs, unless Bob and Eve have the same hat colour in which case she should pass. In this way, she will sometime guess correctly, but will never guess correctly at the same time that Bob does it (and we know from similar problems that we want people to guess wrong together but correct alone).

If Alice sees that Bob and Eve have the same hat colour she will pass, otherwise she will guess the same as Bobs hat colour.

Eve might as well obey the same strategy as Alice, just to cover the case where Eve and Bob actually do share a hat colour and Alice does not.

If Eve sees that Bob and Alice have the same hat colour she will pass, otherwise she will guess the same as Bobs hat colour.

Looking over this, we can see that the players will win if somebody shares a hat colour with Bob, and will lose if nobody does. One can see that the probability of winning is then 5/9, or 15 of the 27 cases.

For a theoretical upper bound, imagine the possible space of hat distributions as some continuous region (I chose to imagine a disc). In that region, each person can choose a part of it for where their strategy will call for them to guess, and in that part they will guess correctly 1/3 of the time and incorrectly 2/3 of the time. So, take some region and colour it 1/3 green and 2/3 red.

Now take another region, which may have some overlap with the first region, you must also colour this one 1/3 green and 2/3 red, but if some part is coloured both green and red, it stays red (a right guess and a wrong guess is a loss). Clearly if we want more green and less red, it is best to have exactly the red parts overlap and the green parts be distinct. Finally we take a third region and colour it 1/3 green and 2/3 red. Any regions left uncoloured at this point are red (since if nobody guesses we lose).

If we have done this optimally we have 3/5 green and 2/5 red, since each person had one part green to two parts red, but they can all use the same red, there are three green parts at most. So theoretically the players can win at most 3/5 of the time, this comes out to 16.2 of the 27 cases, so 16 at best. We can see that our solution is slightly short of this theoretical optimal.

Ben has given me an argument for why 16 is not actually attinable, basically by just breaking down possible strategies, but its not particularily interesting to give here, so I won't bother with it, unless somebody really wants me to.

Hats Revisited

So, Ben has been quite a source of puzzles lately, but he gave me a really neat one the other day I just had to post.

There are 3 people in a room and they are each wearing a hat. The possible hat colours are red, green, and blue, and the standard hat rules will apply. The players must simultaneously write down a guess for their hat color, or write down "pass". The players win if somebody guesses right and nobody guess wrong, they lose if somebody guesses wrong or if everybody passes. Before the hats are assigned, they may strategise. Find a strategy that works more than 1/3 of the time.

Naturally 1/3 is trivial to reach by having Bob guess red and everybody else pass. Its a bit of a combination of two hat puzzles I have done before, but I never realised that the combination of these two puzzles is also interesting.

The Lowest One

Solution time! Last puzzle was about Infinite Hats. Actually, its funny, I found a solution and then I told it to Mark and he found a slightly different solution that had the exact same probability of working, but then those clever people over at Tanya Khovanova’s Math Blog found a better solution than mine. Anyway, lets go over my solution first, because I'm egotistical like that.

First lets consider the two person case, as soon a one person guesses we are at probability 1/2 of being correct, and we simply need to make sure that both of them are right together or that they are wrong together. Specifically, I want to make sure that if Alice guesses wrong, Bob will also guess wrong (say). In this case, suppose Alice looks at Bobs hats and writes down the smallest number that is a black hat and similarly Bob writes down the lowest number that is a black hat on Alices head. So if Bobs first hat is black, Alice will write down 1 and then if she is wrong Bob will also be wrong.

What is the actual chance of this working? We will calculate this by looking up the hats on their heads slowly, starting at the bottom. If both are black then we lose, if one is white while the other is black, then the person with a white hat is considered correct, and if both are white we move up to the next pair of hats. Let P be the chance that one person is correct, in this case we have

P=0*1/4+1*1/4+1*1/4+P*1/4

that is, 1/4 of the time we get BB and we are wrong, in the cases where we get BW or WB then we are get one person correct, and in the case of WW we haven't really changed anything. One can solve this to get P=2/3.

Now that one person is correct, what is the chance that the other person is correct? Suppose we have already seen WB go by, so person 1 is already correct, now WB and WW both have no effect, and BB results in a loss while BW results in a win. This the odds are 1/2 of the second person being correct. All in all, the probability is 1/3 of winning the game, better than 1/4.

Actually, there is a faster way to arrive at that answer of 1/3. Consider looking at the hats that occur, from the bottom up, you will see a series of things like WW, WB, BW, BB, and then look for the lowest occurrence of each of BW, WB, and BB. If BW and WB each occur before BB, then we win. That is, of those three if the highest is BB then we win, which is clearly 1/3.

Naturally this strategy generalizes to 100 quite easily. Simply look for the lowest occurrence of all black hats by your teammates and write down that number. The relevant sequences are BBB...BBW, BBB...BWB, BBB...BWBB, ...., BWBB...BB, WBB...BBB, and BBB...BBB, of which there are 101. There is a 1/101 chance that the last one is that all black one, and then we win. This generalizes to a strategy that works with probability 1/(N+1).

Marks strategy was slightly different, instead writing down the lowest occurrence of all white hats rather than all black hats (attempting the align when the players are right rather than when they are wrong). The relevant sequences are the all white and all white with one black, again N+1 of them in total. Naturally the game is won if all white occurs before any of the other ones, and that is again 1/(N+1).

The better strategy can be arrived at in a similar fashion to some other hat puzzles, using modular arithmetic. First, let K_i be the location of the lowest white hat on person i's head. Let S be the sum of all the K_i. If each person knew S, they could find the value of K_i. Fix a constant C_N (the constant can depend on N, the number of players). Each person is to make their guess assuming the following two things:

1) S mod C_N = 0
2) each K_i is no larger than C_N

If these statements are actually true, then this is enough for the players to guess correctly. What is the chance that those two statements were actually correct? Well, the largest K_i is going to be about as large as lg(N) (lg being log base 2), so if C_N - lg(N) gets large as N goes to infinity, we should be safe as far as the second point is concerned. As for the first one, it will be on average probability 1/C_N, since S is just a random number, and the two points are approximately independent. For example you could use C_N=2lg(N) and then you have a chance of winning of about 1/2lg(N), maybe a little worse, but this is asymptotically much better than 1/(N+1). One of the posters at Tanya Khovanova's Blog showed that it is basically optimal to use C_N=lg(N)+lg(lg(N))-lg(lg(lg(N))), but thats neither here nor there.

It is interesting that this better solution always attempts to find the location of the lowest white hat on your head, rather than any hat at all, so it seems clear one should be able to do better than this, but it is not clear how much better.

Infinite Hats

Time for a new puzzle. I found this one on Tanya Khovanova’s Math Blog, as so many of my puzzles are:

There is a room with 100 logicians, and each of them have an infinite number of hats in a tower upon their head. Each hat can be either white or black, and the sequence of hats upon a given logicians head is random. Standard hat rules apply of course.

At a specified time, each logician must simultaneously write down a number. For each logician, the hat of the number they wrote down is checked (so if Bob wrote down 13, we look at the 13^th hat on his head), and if that hat is white, that logician is "correct". If all the logicians are correct, they win, if any of them are incorrect they will play the game again tomorrow with new random hats.

Before the game, they may strategize. The naive strategy gives you a 1/2¹⁰⁰ chance to win, so it will take about 2¹⁰⁰ days to be released, but they do not want to wait that long. Find a strategy that will probably get them out within the year.

Because the hats are random you may use a strategy that only will specify a number with probability one. For example, Bob could look at Alice's hats and look for "the first occurrence of 578 consecutive black hats", which will appear somewhere on her head with probability one.

Correlated Hats

Well, my thesis is essentially done, now its just time for the eternal editing of the damn thing (also, its only like 65 pages, somehow I had hoped for more). Anyway, time to post the solution the the hat problem from last time.

For the first part of the puzzle, consider that the logicians have some sort of strategy, which must be based on the hats of their fellow logicians and possibly some constant which varies for each individual logician and possibly some random variable. You get into the room ("you" being one of the logicians) and you check your strategy, and it says to say that your hat was white. OK, great, but since your strategy is independent of your own hat colour, your hat colour could randomize as we do this and your answer won't change. Thus you are 50% to be correct, no matter what. This is true for each and every logician. This means that no strategy can save more than 50% on average. In fact, no strategy can save less than 50% either. All strategies have an expectation value of saving 50 of the logicians.

You might think that is weird, since in so many other hat puzzles it has been that case that the logicians pull off something amazing with no information about their own hat colours. If you check carefully though, in all of those, when they were going to guess they were 50% chance to be correct, the most they ever pulled off was correlation with the other logicians being right.

Alright, now, is there a strategy that guarantees saving 50? Note that if the logicians knew if the total number of white hats was even, they could always guess their own hat, and similarly if they knew the total number of white hats was odd. So, the strategy is to have half of the logicians assume the total number of white hats is even, the other half assume that it is odd. Exactly one of those two groups will be right, and you will save 50 of them.

Finally, a strategy that saves all or none of them. This is simple given the last paragraph, simply have everybody assume the total number of white hats is even (or odd, if you prefer). They will either all be correct or all be wrong, with 50-50 chance.

Friendly Hats

Been some time since I have done an actual hat puzzle. There was one recently on Tanya Khovanova’s Math Blog that I had assumed I had done before, since it was so basic. Interestingly enough, I have never actually done this one, so I might as well put it up now:

There is a room of 100 logicians wearing hats. Each hat can be either black or white, and standard hat rules apply. The logicians must simultaneously guess what colour hat they have. Every logician who guesses right is released and every one that guesses wrong is killed.

Before the hats are assigned, they logicians may get together and plan. What strategy maximizes the number of logicians you can save on average?

Thats simple enough, there are a few follow up questions that Tanya also added though:

Suppose the maximum you can save on average is N, is there a strategy that guarantees that you will save N of them?

and,

Suppose the logicians are close friends, and they do not want to see their friends die, they would rather die with them. Is there a strategy that guarantees that they will all live together or die together?

Fairly simple if you have been following all the other hat posts, most of the basic results you need to solve this out have been proven somewhere or another on this blog.

Axiom Of Hats

Man, I meant to blog one more time before the go congress, but blogging is so hard. Anyway, solution time. Puzzle from last time was another hat one. The solution is rather similar to puzzles I have posted here before, but it still took me a little while to get it.

As always, it is easier to start with the two person, two colour case. Suppose the two colours are white and black, and we have two rooms. Label the two rooms white and black and go into the room that corresponds to the hat colour of the other person. If you both have the same colour, you will go to the same room, but if you have different hat colours you will go to different rooms.

Naturally, a strategy for the more general case must just be a function that maps from the hats you see to the room you go to. Lets try two hat colours and N people next.

We have two rooms again, call one room even and one odd. If you see an odd number of black hats, go to the odd room, if you see an even number of black hats, go to the even room. Then, if the total number of black hats is even, white-hatted people will go to the even room and black-hatted people will go to the odd room. Naturally it works the other way if the total number of black hats is odd. One could also arrive at this strategy by assigning the rooms numbers 0 and 1 and call white 0 and black 1. Then add the hat colours you see mod 2 and go to that room.

This generalizes to the strategy for N people and K colours. First number the hat colours 0 through K-1 and number the rooms 0 through K-1. Then add the hats colours you see together mod K and go to that room. We can see this strategy works by considering the sum of all the hats (call that S), then a person with hat colour x will go to the room S-x mod K. If two people with hat colours x and y go to the same room, then S-x=S-y mod K and so x=y mod K and so x=y, two people go to the same room means they have the same hat colour, so this solution works.

Generalizing this to the case of countably infinite hat colours is trivial, you can just use the same solution and forget the mod K stuff. Each hat is a natural number, and add together the hats you see and go to that room.

With infinite logicians it is a bit more tricky. In this case there are infinitely many of them to add together, so you can't just go to the 'infinity room' and be done with it. Since we have been handed the Axiom of Choice, we might as well make use of it.

What can one do with the Axiom of Choice? In most cases, the most efficient thing to do is the same old equivalence class thing. Let us construct an equivalence class of hat sequences. Two sequences are said to be the same if they differ in only finitely many places. Now we can use the axiom of choice to construct a set S which contains exactly one element from each equivalence class. Since each logician can see all but their own hat, they can all determine what equivalence class we are in, and thus can select an element x in S that differs from the real sequence of hats in finitely many places. We will add together those finitely many hats to construct our solution.

Alright, so everybody sees most of the full sequence of hats y_i and they all have agreed on a sequence x_i that differs from the sequence y_i in finitely many places, they must now choose a room to go to. Let us suppose that all the hats are correct. Then it is simple, you just go to the room that x_i says you go and it will all work (the hats and the rooms have both been numbered as naturals). Now, let us suppose that person j is wearing the wrong hat colour, that is x_j ≠ y_j but all the other x_i=y_i. Now he is going to go to the room suggested by the hat x_j, which is x_j-y_j too many, so everybody else must also go x_j-y_j too many also. It is possible for this number to be negative, so first we must number the rooms as integers instead of naturals. So, the strategy is that when you are person n and you see hat j wrong, you go to room x_n+x_j-y_j. Naturally, if you see more than one wrong hat, just add up x_i-y_i of all the hats that are wrong (there are only finitely many) and add that to your own x_n and go to that room.

Tanya Khovanova has a complaint with this solution that even though the Axiom of Choice allows you to select the set S that we will use for the solution, it does not guarantee that there is a method of distributing the set S to a collection of people. If they cannot distribute the set S, they cannot guarantee that they all have the same one (and I would suppose they almost certainly do not, but that is a bit of an odd statement to make). I am not sure if I agree with her on this point, but I generally am against the Axiom of Choice in the first place, so it is a bit of a non-issue for me. At any rate, I suppose one could distinguish another axiom where you have the Axiom of Choice, and you may actually describe the set it gives you, then this puzzle simply needs that more powerful axiom, to solve.

Hats Again

Time for new puzzles that Mark told me but he actually got from Tanya Khovanova's math blog:

1000 logicians are going to play a game against The Adversary. The Adversary has a collection of hats that come in 6 different colours. There are also 6 rooms. The Adversary is going to gather all the logicians together and put a hat on each of their heads, and then the logicians must simultaneously decide what room they are going to enter. After the logicians have each gone to their chosen rooms, each room must have logicians with only one colour of hat. The logicians may strategize before the hats are assigned, find a strategy that guarantees that each room will have a unique hat colour in it. Standard hat rules apply, of course.

You can assume that the logicians know what colours are available. If you like, you can also generalize to N logicians and K hat colours, its not much harder. What is harder is allowing N and K to be infinite, you will need the axiom of choice in this case, but its also an interesting puzzle.

Two Is Not Enough

Alright, I'm going to be gone for a week soon, so I better post the solution to the latest hats in a line problem.

The solution starts with the standard thing of spending the ones you can afford to get wrong right off the bat and then having everybody else correct. Surprisingly, you can use the two people in the back to tell the next three people their hat colours. Numbering the people from back to front, person 1 can see all the way to person 5. First, person 1 will volunteer if person 3's hat colour is black, and person 2 will volunteer if person 3's hat colour is white. Person 1 will make his guess equal to person 4's hat colour, and person 2 will make his guess equal to person 5's hat colour. In this way, we now have the back three people knowing their hat colour and we cannot afford any more incorrect answers.

If you had tried solving this problem but did not notice a way to get three people to know their hat colours, you might want to stop reading and go try again, that first step is crucial.

Alright, now for the rest of the solution:

Call the current back people A,B,C,D,E,F, and G. A can see all the way to E. A and B will guess their hat colours next, A will guess first if D and E have the same colour hat, B will guess first if D and E have different colours of hat.

Now D knows his own hat colour (he can see E's), and E knows his hat colour relative to D's. Next C and D will guess. C will guess first if F and G have the same hat colour, and D will guess first if F and G have different hat colours. When D makes his guess (either first or second), E will learn his hat colour. F knows his hat colour (he can see G's) and G knows his hat colour relative to F. The part of the solution in this paragraph is stable and can propagate all the way forward.

And at the end, when everybody knows their own hat colour, everybody can just volunteer and finish things off.

Slightly Less Myopic Hats In A Line

So, you can tell that I've been wandering through the xkcd forums for puzzles when I manage to make four posts in one month after having done about one post a month for so long. Anyway, here you go:

One hundred people are standing in a line, each of them wearing either a black hat or a white hat. They all can see the hats on the four people directly in front of them, no hats behind them and not their own hat. Each round, a man in a black suit will ask each person in the line if they would like to guess their own hat colour now, the answer they give is secret, nobody else in the line can hear. The man will then select one of the people who volunteered and ask their hat colour. That person is then removed from the line and a hole in left in the line. Everybody in the line is made aware of who was selected to guess their hat colour and what they guessed. The people may only guess "black" or "white". Then a new round starts with the man asking who would like to guess their hat colour now.

The players lose the game if ever more than two people get their hat colour wrong, or if during any round nobody volunteers to guess. The players win if everybody has finished guessing their hat colour and no more than two people are wrong. Before the hats are assigned the players may strategize, find a strategy that is certain to win assuming the man in black (who also assigned the hat colours) is an adversary.

Its the same as the other hats in a line problem (I basically copy-pasted it), but now holes will be left when people leave and they have a sight range of 4.

Just to be clear, if we number the people starting from the back, person 1 can see the hats on each of {2,3,4,5}. If person 3 now makes a guess and leaves the line, person 1 can now see the hats of {2,4,5}, but still cannot see the hat on 6.

Two Is Enough

Time for the solution to the hat problem from last time. Not really much to the solution, as Mark pointed out in the commentary its just about parity.

To start, we will number the people from 1 to 100, with the person at the back on the line numbered 1, so N can see the hats of people N+1 and N+2. First thing we need to do is have the two people at the back of the line know their hat colours:

First, person 1 volunteers to guess, and guesses the hat colour of person 3. Next, person 2 volunteers to guess and guesses the hat colour of person 4.

The adversary will ensure that both of those guesses were wrong, so now we have a new problem where the back two people know their own hat colour and we cannot afford anybody to guess wrong. Fortunately, they can now see the hat colour of person 5. They use that to decide who guesses next:

If person 5 has a white hat, person 3 guesses what he knows his own hat to be. If person 5 has a black hat, person 4 guesses what he knows his own hat colour to be.

They are no longer transmitting information by what they guess, it is instead done by who makes the guess. Naturally, whatever happens, the line will shift back and you have the two people at the back of the line with full knowledge of their own hat colour. The person at the very back guesses if the next "unknown" hat is white, and the second person from the back guesses if it is black. The solution works by induction, until only two people are left in the line, when they both know their own hat colour and both of them volunteer to guess (letting the adversary helplessly decide how it ends).

If one states the problem differently, so that instead of a "win-loss" scenario there was some sort of bet based on how many you got wrong, this solution also has the advantage that a mistake by one of the players only results in one extra person being wrong, rather than an entire chain.

Actually come to think of it, that would be a better way to word the problem, to minimize the number of people who guess wrong rather than saying outright how many you can afford. When I post the harder version of this problem I might word it that way.

Myopic Hats In A Line

That counter thing on the right for my blog posts seems to suggest that its been some time since I've had more than one post in a given month... I guess its time to do something about that. Anyway, this puzzle is one I found on the forums at xkcd:

One hundred people are standing in a line, each of them wearing either a black hat or a white hat. They all can see the hats on the two people directly in front of them, no hats behind them and not their own hat. Each round, a man in a black suit will ask each person in the line if they would like to guess their own hat colour now, the answer they give is secret, nobody else in the line can hear. The man will then select one of the people who volunteered and ask their hat colour. That person is then removed from the line and the line is shifted back a step to fill the hole. Everybody in the line is made aware of who was selected to guess their hat colour and what they guessed. The people may only guess "black" or "white". Then a new round starts with the man asking who would like to guess their hat colour now.

The players lose the game if ever more than two people get their hat colour wrong, or if during any round nobody volunteers to guess. The players win if everybody has finished guessing their hat colour and no more than two people are wrong. Before the hats are assigned the players may strategize, find a strategy that is certain to win assuming the man in black (who also assigned the hat colours) is an adversary.

Its some sort of variation on "standard line hat rules", the people are also short-sighted.

End Of The Line

So, its time for the solution to the Hats in a line problem. I've always like this problem, because when I first learned it I got lucky and managed to solve it in under an hour. Its not uncommon though to take a few days.

Anyway, the solution is easy enough:

Treat the hat colours as 0 or 1, the person at the back states the value you get by taking the XOR of the front 99 hats. The next person from the back can see the front 98 hats and knows the parity, so that is enough for them to be correct. The next person can see the front 97 hats and knows that the person second from the back was correct, and knows the parity of the first 99 hats, so that is enough information for them. It is easy to see that each person will be correct now except possibly the one at the back, who is 50/50 to survive.

Its not hard to see this is optimal, as the person at the back cannot possibly do better than 50/50 with zero information, and everybody else is 100%. Its also interesting to note that having on "idiot" in line will not kill everybody in front of them. They will be wrong, and they will screw up the person in front of them, but after that the two mistakes will cancel out. This is even true if the person at the back of the line is incorrect for some reason.

Hats In A Line

Alright, time for a new puzzle. I haven't put much thought into what puzzle I wanted to post next, so I guess I'll just go with one I have known for ages. Possible that most of my readership has already seen this also (all two of you), but I'm also just posting it for my own archiving purposes.

Anyway, I first learned this one from Bart:

There are 100 people in a line wearing hats. Each hat is either white or black, and each person can see all the hats in front of them, not their own hat or any hat behind them. Then, some disreputable men in black suits will come and ask each man a simple question: "What colour hat are you wearing?". They begin asking at the back and move forward in the line one person at a time. The people can only answer with "white" or "black". For each person, if that person is correct they are silently released, if that person is incorrect they are silently killed. Every person in front of them can hear their answer.

The people may get together and plan before the hats are assigned. What strategy guarantees the maximum number of people survive?

I would like to call the rule about seeing all the hats in front of you and none behind you "standard line hat rules", but theres only one other problem I know of that even uses that rule, and it involves the axiom of choice.

Hamming Hats

So, I hope everybody is ready for the solution to the hat problem from last time. Its a pretty good one, and combines a bunch of ideas I have set forward in previous puzzles.

First, one would like to solve a few cases with small N. The N=1 case is trivial, of course, you can't get better than 1/2 chance of success. Sadly, the two person case is similar, you cannot do anything better than 1/2 again. In the three person case however, we can do better with the following strategy:

For each person, guess black if both hats you see are white, guess white if both hats you see are black, and pass otherwise.

So, if the hats are white, white, black, then the black hat guy will guess correctly and the other two will pass. If the hats are white, white, white, then everybody will guess black and be wrong.

This is good, because we know that in a puzzle where one person being right is sufficient, then we don't want two people to be right at the same time. Also, in a puzzle where one person being wrong makes it all fail, we know that we should try to make it that everybody is wrong at the same time. Our solution will work unless everybody has the same hat colour, so the chance of success is 3/4.

So, in the case of general N now. We want that in any given situation, one person will guess correctly, or everybody will guess and be wrong. I honestly can't remember the logic I followed to get to the solution in the general case, but here is the solution in the N=7 case:

Treat a distribution of hats as a binary sequence of 7 digits, call it X. Each person knows all the bits except their own. Construct the Hamming set S of binary sequences of length 7. Each person is to look at the hats around, and if it is possible (based on the one missing bit) that X is an element of S, then make a guess assuming that X is not an element of S. If it is not possible X is an element of S, then pass.

If you have forgotten about Hamming codes, take a look at the sam and ray solution. So, since each string of length N is within one bitflip of an element of S, then unless X is an element of S, exactly one person will guess and they will be correct. If X is an element of S then everybody will guess and be wrong. The probability of failure is 2⁴/2⁷ which is 1/8.

If you have 10 people, say, then you just split 7 of them off and have them use that solution, have the other 3 always pass. In general with N people, split off M people so that they construct the largest Hamming set you can (it will be when M+1 is a power of 2) and have the remaining N-M people pass. The M people have a 1/(M+1) chance of failure, which will go to zero as M goes to infinity (and M goes to infinity as N goes to infinity, just taking a different path).

Hats, Hats, And Hats Some More

Time for a new problem I suppose. This one is going to be a bit weird, because as I understand it part of this is actually an open problem. The solution is only known in a few special cases, and so part of the problem will be to find how those cases fit in. Here we go:

There are N people in a room, each of them wearing hats. The hats can either be white or black, and standard hat rules will apply. At a specified time, each person simultaneously must either guess their own hat colour or pass. The players win the game if nobody guessed their hat colour incorrectly and somebody guessed correctly. They lose the game if either somebody was wrong, or everybody passed. The players are free to strategize before the hats are assigned. Find a strategy for the N player case such that in the limit as N goes to infinity, the probability of success goes to 1.

This problem as it is stated can be solved, its not an open problem really. Solving it in the N person case optimally is an open problem, so don't worry about that.

And We All Go Down Together

OK, I feel like distracting myself from work, so its time to post the full solution to the hats in a room puzzle. You must have already seen the hint I gave, so I will go from there.

The next case to solve is the four person case. The random strategy for that case gives a 1/16 chance of success, and the 'left-right' strategy gives 1/6. Doesn't seem like there is much room to improve, but lets try. First, let us name our people Adam, Betty, Candy, and Dale (I suppose I could give them numbers as names, but the hats will also need to be numbered, and it will make my explanation a bit less transparent). Suppose we plan to have Adam and Betty look under the two hats on the left, and Candy and Dale will look under the two hats to the right. Adam will look under hat 1 first, if he sees his own name, then all is well. If he sees Betty's name in that hat, then we are still OK. However, if he sees either Candy or Dale under that hat, then there is a problem.

If Adam knows that Candy's name is under hat 1, then he knows that the plan is going to fail unless he aborts. Whats more, he knows that the plan will fail anyway unless Candy also aborted. One way that Candy will abort is if she sees Adam's name under hat 3. If Candy sees Adam's name under hat 3, she will know that the default plan is doomed, and must abort. Thus, if Adam sees Candy's name under hat 1, he should look under hat 3 next. Out of some sort of symmetry, he might as well look under hat 4 if he sees Dale's name under hat 1.

At this point you can guess the strategy (actually, lots of people guess this strategy after the hint, but few are able to convince themselves it actually works). Adam will be assigned hat 1, Betty hat 2, Candy hat 3, and Dale hat 4. Look under your own hat, and whatever name you see, look under that persons hat next. What are the odds this works? Its is easy enough just to look at all 24 arrangements of the hats and see. I will denote an arrangement like Adam under hat 1, Dale under hat 2, Candy under hat 3, Betty under hat 4, with the letter sequence ADCB, and write S for success and F for fail.

ABCD - S
ABDC - S
ACBD - S
ACDB - F
ADBC - F
ADCB - S
BACD - S
BADC - S
BCAD - F
BCDA - F
BDAC - F
BDCA - F
CABD - F
CADB - F
CBAD - S
CBDA - F
CDAB - S
CDBA - F
DABC - F
DACB - F
DBAC - F
DBCA - S
DCAB - F
DCBA - S

So, 10 successes out of 24, thats better than the 'left-right' strategy of 6 successes out of 24 (actually, those successes are a subset of these ones). Okay, its not likely that we will do better than that, as its easy to show that no matter what the first person does, he cannot win with more than 1/2 chance, so at best we can approach 12 out of 24. Back to the 100 person case.

With 100 people the strategy generalizes simply, assign each of them a number and have each person look under the hat of their number. Then go to the hat corresponding to the name of the person you saw under that hat, repeat until you either see your own name or you have looked at 50 hats. There is no concern that you get sent back to your first hat, as only seeing your own name can do that.

Easy enough strategy, does it work? More simply, given the numbers 1 to 100 in a line (an element of the permutation group) what are the odds that there is no cycle of length 51 or more?

Alright, we know that in total there are 100! ways to arrange the numbers 1 to 100, how many of them contain a cycle of length 51 or more? Well, lets assume we wanted to construct a list with a cycle of length n (with n>50), then there are ₁₀₀C_n ways to choose those elements. Given those n elements to form a cycle, there are (n-1)! ways to arrange them into a cycle (because the first one can link to n-1 others, the second one to n-2 others and so on). Finally the remaining 100-n elements can be arranged (100-n)! ways (note there is no concern of the remaining elements forming a cycle of length n, as n>50).

We can see that the total number of ways to create a list of the numbers 1 to 100 that contains a cycle of length exactly n is:

T(n)=₁₀₀C_n*(n-1)!*(100-n)!
=100!*(n-1)!*(100-n)!/(n!(100-n)!)
=100!/n

Well, isn't that nice.

So the probability that there is a cycle of length n is

Σ T(n)/100!

Where the sum has n going from 51 to 100. The sum can easily be calculated on some math program, or you can approximate is as an integral if you believe that 100 is large enough (it is). Then it is the integral from y to 2y of 1/x dx, which is simply ln(2)≈ 0.69. That is the total probability of failure.

We can see that even in the case that the number of prisoners tends to infinity, the chance of success using this strategy will, at worst, be 1-ln(2)≈ 0.31. Thus they can expect to get out in just over 3 days.

As a side note, what are the odds that the first person expects to find his name when he first enters the room? He will not find his name if it is part of a cycle of length n with n>50. There are ₉₉C_n-1 ways to choose the other n-1 elements, and (n-1)! ways to arrange them into a cycle, and (100-n)! ways to arrange the remaining elements. Thus, we are interested in summing

₉₉C_n-1*(n-1)!*(100-n)!/100!

as n goes from 51 to 100. But that term is exactly 1/100, so after summing we will have 1/2.

As one would expect, the chance of the first person (or any individual, for that matter) finding their own name is 1/2. However, if that person is wrong, then there are at least 50 other people who are wrong with them. This is standard in problems where one person being wrong ruins everything. Make sure that nobody is ever wrong alone, they must take as many people with them as possible.

On the other hand, with problems where you only need one person to be right (such as with some of my earlier hat problems), you need to make sure they are always right alone, so you don't waste any extra "rightness".

Hints In A Room

So as a follow-up to my hats in a room puzzle, I'm going to be doing something unusual this time....I'm going to be giving a hint. This puzzle is particularly difficult, and even with this hint it still is quite a trick. Before giving the hint though, lets go through some of the logic that you have probably already gone through.

First of all, you need to see just how badly the random strategy fails. Each person has a 1/2 chance to select their correct hat if done randomly, so the chance that they all happen to be correct is 1/(2¹⁰⁰). Thats pretty bad. OK, next we try to solve the two person case and try to do better than 1/4 that the random strategy gives. Its clearly a waste of time for both people to look under the same hat, so we might as well agree that one person looks in the left one, and the other person in the right one. This gives a 1/2 chance of success, huzzah. Generalizing this back to the 100 person case, if 50 people look in the ones on the left and the other 50 look in the ones on the right, you have a 1/(₁₀₀C₅₀) chance of success. This is substantially better than 1/(2¹⁰⁰), but still nowhere close to being able to get out in a week. This is the best you can do without a key realization.

The realization that you need to come to is that you do not have to choose all of the hats you will look under right away, you can look under some of them and use that information to decide where to go next.

I'll finish the entire solution some time later this week.

Hats In A Room

So, I haven't been in town for a while, I've been away at the go congress. My performance there was average, but I'm happy with the games I played. Anyway, onto the new puzzle. I first learned this one from Bart:

There are 100 prisoners in a room (we shall call this room A) and the warden of these prisoners has decided to play a game with them. In another room (room B) there are 100 hats, and each one has the name of one of the prisoners underneath it (each prisoner has a unique name). A prisoner will be selected randomly and sent into room B. While in room B, the prisoner may look underneath 50 of the hats and then will be sent into another room (room C). Room B will then be restored to its initial state before a new prisoner is sent into it.

One by one, each prisoner will have a chance to look underneath 50 hats before being sent into room C. Once they are all in room C, they will all be released if each one of them has looked under the hat that contains their own name. If any of them has not looked under the hat that contains their own name, they will be sent to their cells for another night and the scenario will be run again tomorrow, with the names randomized underneath the hats each time.

The prisoners may plan while in room A. Come up with a strategy that, on average, will set them free in less than a week.

As I understand, Bart first learned this one at a talk entitled "Seven Problems You Swear You've Heard Incorrectly".

Kittens For All

OK, time to solve the hat problem from last time. So, first it is easiest to solve the two person, two hat colours case. When we have two people with only black or white hats, the solution is as follows:

Person 1: guess the hat colour you can see on person 2

Person 2: guess the hat colour opposite to the one you can see on person 1

More simply, person 1 assumes both hat colours are the same, person 2 assumes they are different, one of them will be correct.

Its also interesting to note that either individual has a 50% chance to be right (this is trivial since hat colours are independent), but there is no way both will be right. Thus, let event A be "person 1 is right", event B be "person 2 is right", so P(A)=1/2=P(B), and the probability that at least one of them is right is given by

P(A or B) = P(A) + P(B) - P(A and B) = 1 - P(A and B)

So we see that by minimizing P(A and B) to zero, we guarantee that one of them will be right.

This idea generalizes, in the seven person case, it is sufficient and necessary to find a solution that no two people can ever be correct at the same time, and you guarantee that one of them will be correct.

I will show the full solution using modular arithmetic. All math in the following solution will be done mod 7:

Number the hat colours 0 through 6, and number the people 0 through 6. There exists a number S which is the sum of everybodys hat colour (but none of the players have enough information to fully calculate S). Person n is to assume that the value of S is n, this gives them only one choice of hat colour to guess.

Each person assumes that the sum of the hats is a different number mod 7, and one of them will be right, also never will two of them be right.

This idea of making sure that no two people are right at the same time, so that you don't waste any extra "rightness" has uses in other logic problems, I'll probably point it out when it comes up or something.