Box Stacking

New puzzle time I suppose, this is one that Ben told me, but it was pretty quick for me to solve since the correct approach uses some logic that I had been trying to use on that last puzzle:

There is a collection of boxes, and the boxes are coloured either red, green, or blue. You are going to be building a triangle of boxes, with a row of 10 on the bottom, 9 in the next row, 8 in the next row, and going all the way up to a single box on top. They are arranged in the sort of obvious triangle pattern, so that each box is on top of exactly two boxes below it.
The color of a box is chosen according to an algorithm, if two neighbouring boxes have the same colour, then the box on top of them is also that colour, if two neighbouring boxes are different colours, then the box on top of them is of the third colour.
Given the colours of the 10 boxes on the bottom row, is there a simple method to determine the colour of the box on top of the triangle?

"A simple method" essentially means one without having to actually go through the process of building the whole triangle.

Yeah, hopefully a simple one, but its sort of neat.

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.

All Lined Up

A month between posts, thats about right. I guess I should post more frequently for the next little while, as I have learned a few new puzzles from Ben as of late, but we will see if that actually gets me to post more.

Anyway, time for the solution to the lineup puzzle that I posted last time.

So, its not hard to work out what the solution is for a few simple N, but it might be a bit tricky to see what the pattern is if you don't recognise it. For some small N values, the solution F(N) is given by:

F(1)=1
F(2)=3/2
F(3)=11/6
F(4)=25/12
F(5)=137/60

Gets sort of ugly, but if you take the differences:

F(2)-F(1)=1/2
F(3)-F(2)=1/3
F(4)-F(3)=1/4
F(5)-F(4)=1/5

The solution being the sum of 1/k from 1 to N seems like the obvious solution. You can go ahead and prove it by induction if you like, but there is a much cleaner solution.

Consider the people enter the lineup into random positions, starting with the tallest person. You can see the tallest person with probability 1, and shorter people added to the lineup cannot change that. You can see the second tallest person with probability 1/2, and shorter people added to the line cannot change that, you can see the k^th tallest person with proably 1/k, and shorter people added to the lineup cannot change that. This gives the solution of the sum of 1/k (also known as the harmonic numbers).

In The Line

Time for a new puzzle. I first found this one on the internets:

N people are standing in a lineup. There is a person at the front of the line (who is not one of the N) who can look down the line and see a given person if nobody taller than that person is in front of them. Each person in the line is of a unique height. What is the expected number of people that the person in front can see if each permutation of people is equally likely?

Just to make sure the wording is clear, with N=3, there are 6 cases (and assuming the line starts on the left and the person I name 1 is shortest and 3 is tallest):

123 -> three are visible
132 -> two are visible
213 -> two are visible
231 -> two are visible
312 -> one is visible
321 -> one is visible

So, on average, 11/6 people are visible in the N=3 case.

Spinning Robots

Ok, that was quite the break from blogging. Time to solve out the robot chasing puzzle I put up last time.

First of all, it is easiest to work in polar coordinates, r and θ, the robot starts at r=0 and moves along θ=θ₀ and you start at r=r₀ and θ=0 The robots path given

r(t) = v_rt
θ(t) = θ₀

We get to pick our r(t) and θ(t) and choose a path such that we will meet up with the robot path for any arbitrary value of θ₀.

First of all, we might as well move straight to the robot, assuming that θ₀ is 0. We move toward r=0 and would meet the robot at r=r₀*(v_r/(v_p+v_r)) This value, which I will call R, will be our effective starting point.

Next, we must move outward in a spiral, such that our r(t) continues to match the robot r(t), but our value of θ takes on all values between 0 and 2π. This is simple enough, find r(t) and θ(t) such that:

r'(t) = v_r
(r(t)θ'(t))²+r'(t)² = v_p²

Solving it out, you get

r(t) = v_rt+R
θ(t) = √(v_p²/v_r²-1)ln((v_rt+R)/R)

Note the problem we would have if the robot were faster than the player. Anyway, since the logarithm is unbounded from above, you know that this θ will eventually reach 2π, solving the problem. This also finds the smallest disc you can solve the problem on, since you just find that t where θ is 2π and put it back into r.

Not too tricky of a problem once you hit on the solution really, but at first it did look somewhat impossible.

Robot Chasing

New puzzle time, because I actually have more than one in mind and I don't want to forget them.

I found this one somewhere random on the internets, I'll try to dig it up agian when I do the solution:

You are playing a game where you have to catch a robot. You and the robot are on an infinite 2-dimensional plane and you can see where the robot is. When the game starts the lights will be turned off and the robot will select a random direction and move in that direction at a constant speed. You may move around, and your top speed is some number which is greater than the robots constant speed (call them v_r and v_p for the robot speed and the player speed if you like). You naturally cannot see or hear the robot once the game begins. Find a strategy that guarantees you will find the robot.

So you must find a path (x(t), y(t)) which starts at a point (x₀, y₀) which never has a speed exceeding v_p and that path much intersect the robots path such that there is a t where they meet.

As a bonus problem, assume the game is played on a disc of radius R, with the robot starting in the center of the disc and the player on some point a distance P away from the robot. If the robot reaches the edge of the disc it escapes and the player loses. What is the smallest R for which your strategy works?