Modular Boxes

So, there is a bit of a follow-up to my puzzle last time I had intended to post, but then life got all busy on me, or I am just a slacker or something, but I noticed something funny about the puzzle last time.

When I had worked out that the elements of the 9th row of Pascals triangle (getting 1,9,36,84,126,126,84,36,9,1) and I noticed that they were all multiples of 3 (except for the 1's, of course) I instantly knew that this row must need a minus sign, without having to count and realize that the odd rows get a minus sign and the even rows do not. The reason is that if this particular row did not have a minus sign, then the statement "first box + last box = top box (mod 3)" would depend on how you mapped the boxes to the numbers. If blue=0, red=1, and green=2, then red+red would be green, but if blue=2, red=1, and green=0, then red+red would be blue. Clearly it cannot be the case that the solution to the puzzle depends on how you map the boxes to the numbers, so there must be a minus sign (and -red-red comes out to red in any mapping).

So does this mean something fundamental about the numbers that appear in Pascals triangle? Did I stumble on to some new property that I hadn't seen before? I couldn't quite see what it meant, really.

Talking about it with Ben, he noted that the statement "the answer comes out independent of how you map the colours" it actually a statement about linear functions made up of rows of Pascals triangle (so for example 1,3,3,1 makes 1w+3x+3y+1z). It must be the case that shifting all the variables by a constant shifts the answer by that same constant, and multiplying all the variables by a constant multiplies the answer by that same constant (and any 1-1 mapping of {red, green, blue} to {0,1,2} can be shifted to any other mapping by adding constants or multiplying by constants).

Since the linear functions in question are, well, linear, the multiplying by a constant thing is trivial. As for adding a constant, if we shift (w,x,y,z) to (w+a,x+a,y+a,z+a) then 1w+3x+3y+1z becomes 1w+3x+3y+1z+8a, where 8 is the sum of the elements of that row of Pascals triangle, and naturally -1w-3x-3y-1z becomes -1w-3x-3y-1z-8a. Since 8 mod 3 is -1, we can see that the expression with the minus sign is the one that shifts by exactly a when you shift all of its inputs by a.

This means that a row will shift correctly under this linear transformation if it has a minus sign when the sum of the row is -1 mod 3, and no minus sign if the row sums to 1 mod 3, and where will be a problem if any row sums to 0 mod 3.

Of course, we know the sum of a row of the kth Pascals triangle is 2^k, and that is (-1)^k mod 3, so this is exactly the property we needed, the rows alternate summing to 1 and -1.

I'm not sure anybody else found that as interesting as I did, since it was mostly about stuff that went on in my own head and ended with a fact that anybody who knows about Pascals triangle already knew, but I decided it was worth a post anwyay.

Box Box Box Box

I wonder if I will ever get back to something like weekly blogging instead of monthly. Anyway, time to do the solution to the box puzzle from last time.

First, we might as well use numbers instead of colours, because thats the sort of people we are. Let the colours be called 0, 1, and 2. In this case, "all three the same" and "all three different" is the same as "the three add to 0 mod 3".

This means the top box is negative the sum of the two boxes in the second row. The second row left box is negative the sum of the two left boxes in the third row, and the second row right box is negative the sum of the two right boxes in the third row, meaning that the top box is made up from the third row by adding the first box + 2*the second box + the third box. We can see quickly that Pascals triangle and the occasional minus sign is all we need.

The 9th row of Pascals triangle (calling the top row zero, which I do) is 1,9,36,84,126,126,84,36,9,1, so add the boxes on the bottom row with these coefficents mod 3 to get the box on the top. As it turns out, 9, 36, 84, and 126 are all multiples of 3, so they don't even matter, only the two end boxes contribute at all. Finally, there is a minus sign, as every other row gets one.

Thus the solution is, if the bottom two end boxes are the same colour, then the box on top will be that colour, if they are different colours, the box on top will be the third colour.

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.