Numbers Are Crazy

Probably enough time has passed since my silly math problem. If you have spent some time working on it, you will see that you can basically create every number around 21 easily, but getting to 21 is a bit harder.

To start, we might as well try to make 21 by constructing 7x3, thats basically all 21 is, getting there by any sort of addition is going to be pretty tricky. We already have a 7, so how can we make a 3 from {1,5,6}? Well, basically we can't. We do have a 6 though, so if one considers 21 to be 7x6/2, we just need to use the 5 and the 1 to make a 2 (also clearly impossible). The real trick though is to use grade school division trick that a/(b/c)=ac/b, so 21 is also 6/(2/7). We now need to use {1,5,7} to make 2/7, and that one is pretty easy to do. Of course, the solution is:

6 ÷ (1 - (5 ÷ 7))

The neat blind spot is that people tend to dismiss division right out when they are given this puzzle. There is no division that you can do with these numbers that will not exit the integers, and people tend to assume that once you leave the integers you won't get back.

The double division is also the solution for the "{3,3,8,8} makes 24" puzzle, so I won't bother saying the solution specifically, its pretty simple now.

Silly Math

Alright, I've once again run out of standard "find the optimal strategy" type problems, its time for a seemingly simple math problem. I can't recall when I first learned this one, I've known it since at least grade 9:

Using the numbers 1, 5, 6, and 7, each once and only once, and +, -, x, and ÷ as much as you like, construct a formula for the number 21. You may also use as many brackets as you like.

To be clear, there are no stupid tricks in this problem, like sliding the 1 and 5 together to make 15. The solution is exactly of the form _*_*_*_, where _ is replaced by the numbers from {1,5,6,7} each used once, and * is replaced by {+,-,x,÷} (and can use repeats). You also have as many brackets as you need to control order of operations.

I always find this problem rather interesting because typically this sort of problem is either trivial or impossible, but this one is neither. There is a funny blind spot people tend to have with this.

Also, if you are in the mood, try using 3,3,8,8 to make 24 with the same rules. This one will be much easier after you have solved the first one.

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.