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.

Math Is Hard

Apparently, blogging is also hard, given how often I actually do it. Anyway, time to finish off the second part of the tying strings problem.

First of all, its interesting to wonder why the method of calculating the average was worded the way it was. It was "Specifically, consider one were to select an initial piece of string and ask "what is the expected value of the length of the loop this piece of string will end up in?"". This is different than if it had been "Specifically, consider one were to randomly select a final loop from all of the loops and ask "what is the expected length of this loop?"". The first wording basically gives a heavier weighting to longer loops, and will have a larger answer. Also, it gives an answer with an actual clean mathematical form, rather than the second one which gives a total mess (feel free to work it out sometime, maybe somebody smarter than me can point out a nice form of it that I just missed).

Anyway, lets start by figuring out a few simple cases. Suppose we have N strings, and G(N) is the answer we seek. It is pretty easy to see that G(1)=1. For N=2, consider where the first end of one of the strings ends up. With 1/3 chance, it loops to itself, and we have two loops of length 1, with 2/3 chance it does not loop to itself and we have 1 loop of length 2. So,

G(2)=1/3 1+2/3 2
=1+2/3
=5/3

The 1+2/3 line is going to turn into an attempt to establish the overall pattern, the final loop the first string is in (which is as good as any other string) is at least length 1, and 2/3 of the time it is an extra length.

Next, N=3: the first end of the first string (which is the random string we are going to choose at the end) has a 1/5 chance of looping to itself. It has a 4/5 chance of not looping to itself and then a 1/3 chance of closing with length 2 and a 2/3 chance of closing with length 3. So we have

G(3)=1/5+4/5 1/3+4/5 2/3
=1+4/5+4/5 2/3
=7/3

The 1+4/5+4/5 2/3 is again an attempt at the overall pattern, the final loop of the first string starts at length 1, is 4/5 chance to be length +1 and is 4/5 2/3 chance to be another length +1.

We can already guess the overall formula, G(N)=1 + 2/3 (N-1), and if you check the next few terms you will find this still works. To prove it in general is quite the trick though. First, we can see the general formula for G(N):

G(N)=1+Σ Π (2N-2m)/(2N-2m+1)

where the sum has k from 1 to N-1 and the product has m from 1 to k. You can fiddle with this a bit using the formula:

Π (m-N)=Γ (k+1-N)/ Γ (1-N)

(product over m going from 1 to k) (Γ being the Gamma function), or you can just shove it all into Maple at once. Basically you get a bunch of garbage whatever you do.

After spending some time simplifying that garbage, you can find

G(N) = 1+2/3 (N-1)-1/(3 √π ) Γ (1/2-N)/Γ (1-N)

So, we see the term we want, and them some Gamma function garbage. This extra term shows up for a few reasons. First of all, in the first formula Π (m-N)=Γ (k+1-N)/ Γ (1-N), the math doesn't "know" if k is greater than N (in which case you need to get zero), or even if the things you are using are integers at all.

Anyway, in our case everything is an integer, so Γ (1/2-N) is simply a number one can find using the analytic continuation of the Gamma function, and Γ (1-N) is infinitely large, as Gamma has simple poles at every nonpositive integer. So the extra garbage term is just zero.

If one can find a way to solve this problem that doesn't involve the Gamma function, I would love to hear it.