Random People Numbers

So, a new puzzle that I was chatting about with Ben last night which has a slightly surprising solution in a simpler case:

Three people are assigned real numbers from (0,1), chosen uniformly at random. Each person knows their own number, but knows nothing about anybody elses number. You may ask a single yes/no question to the three people (one question, all three people will answer is at the same time). After that question, you must select which person has the largest number. What question maximizes your chance of success?

If you feel up to it, generalizing from three to N is the hard part. I'm still working on that.

Domino Marriage

About time to post the solution for the covering problem from last time. I though I had come up with a good way to post pictures in blogger, but I apparently forgot what it was, so I don't think I'll bother, the solution is easy enough to describe anyway.

Picture a horizontal line of four squares, numbered 1,2,3,4. Add a square we will call 5 above square 2, and a square we will call 6 below square 3.

It is clear this cannot be tiled, as both 1 and 5 only touch 2 (as well as 4 and 6 only touching 3), but if we add a 2x1 block below 1 and 2, this gives a new option for 1 and 6 to connect, and the tiling works.

Easy enough solution, and it got me thinking, is there an easy way we can check when a tiling is possible or impossible? The general problem is that we have two equally sized groups of things (in this case white and black squares) and you want to have a 1-1 matching between group 1 and group 2, but there are restrictions on what may match with what. In my solution example, we have squares 1,3,5 in group 1 and 2,4,6 in group 2. 1 and 5 may match to 2, and 3 may match to any of 2,4,6. Clearly in this case a matching is impossible, since we will not be able to match different things to 1 and 5, also on the other side we won't be able to match 4 and 6.

We can see a necessary condition here:

For each subset S of group 1, the set of things that subset can match with needs to have at least as many elements as S.

So in our example, the set S can be {1,5} and the set of things they match to is {2} and so it violates this condition. Of course, I could have put group 2 instead of group 1, but as it turns out I don't need to, as we will see.

I spent some time wondering if it was possible to satisfy this condition and still not have a possible matching, but I wasn't able to find anything, I started to suspect that this condition was not just necessary, but also sufficient. Then somebody pointed me to the Hall marriage theorem which proves that this statement is in fact sufficient, and also having this statement proves the equivalent statement on group 2.

Anyway, neat stuff, and a new theorem I didn't know. Thats all for now.

Covering Problem

As promised, the follow up problem:

Find a connected arrangement of squares such that it is not possible to tile it with 2x1 dominoes, but if you increase the shape by adding a 2x1 shape to it, you can now tile the new shape with 2x1 dominoes.

Naturally, I mean 'tile' in the sense of the domino problem. Note that the solution to this problem requires a connected shape. I hope I don't need to define connected, I mean, I could, but its annoying.

Covering Solution

Alright, I'm pretty sure I still have this blog, and now I have something of a backlog of puzzles to post. Something of an embarrassment of riches that I don't bother to post as often as I learn new puzzles, but thats life I guess. Anyway, time for the solution to the domino problem from last time.

The solution is very simple: Consider naming the squares on the chessboard black and white, with no two of the same colour adjacent (the way chessboards are actually coloured). A given domino must cover exactly 1 white and 1 black square. The standard chessboard has 32 squares of each colour, but opposite corners are always the same colour so removing two of opposite corners will leave us with 32 squares of one colour and 30 of the other. It will not be possible to cover this with 31 dominoes.

Thats it really, I'll follow this with a post about the follow up problem.

Dominoes on a Board

Alright, time for a new puzzle. I have one I found recently I want to post, but some of the discussion first requires I post a puzzle I learned many years ago from my students in physics labs at UBC. It isn't a hard puzzle, which is why I never posted it, but the solution is very elegant, and it is one I like.

Consider an 8x8 chess board with two corner places deleted, in opposite corners. Attempt to tile this board with 2x1 dominoes. Prove or disprove whether such a tiling is possible.

Naturally such a tiling requires exactly (64-2)/2=31 dominoes to do this, as each domino will cover 2 squares and each square must be covered exactly once. Anyway, yeah, its not too tricky.

Josephus Solution

Time for the solution to the Josephus problem from last time. As is common for problems that are basically induction puzzles, its easiest to see what is going on by looking at a few cases.

First of all, you can just work through who wins in the cases N=1,2,3,4,5,6,7,8 and so on, you will see that the winners are 1,1,3,1,3,5,7,1. A bit of an interesting note is that all the winners are odd numbers, of course this note is instantly less interesting when you realize that all the even numbered individuals are killed on the first pass. Actually, if N is even, that brings up a good point, specifically that for N=2K you immediately reduce to the problem with K people, with #1 going first and a bit of a renumbering that person 2m-1 is now person m. But if this new K also happens to be even, then you can half it again. From here you can see that if the initial N is some power of 2, then person #1 will be the last one standing.

At this point, we can realize that whoevers turn it is when the total number of people is a power of two is the person who is going to win. Naturally, if the total is an even number, then that is person #1, but if N is equal to 2^k+M, for some M less than 2^k (or we would just use k+1 in the power instead), then once M people die, the next person on turn will live. Clearly since M is less than half of N, those first M people will die on the first pass around the table, so when M people have died it is the turn of person #2M+1.

This gives us the general solution for an arbitrary N. Let 2^k be the largest power of 2 less than or equal to N, and let M=N-2^k. The final person standing will be person #2M+1.

Josephus Problem

Ok, time for a new puzzle, I learned this one some time ago, it is a well known problem with a somewhat cool solution. This problem is well enough known as the "Josephus problem" that you can certainly just look it up along with its solution yourself if you hate my style of writing. The original problem involved N people who, having been captured by the enemy, are performing some sort of suicide pact, where they all kill eachother and there is one person standing at the end. There is a bunch of thematic bubble wrap to go with the puzzle, but I'm going to omit it just for the math. Anyway, here is the problem:

N individuals are in a circle, numbered 1 through N starting somewhere with 1 and increasing with each person to the left. Starting with person number 1, that person will kill the person to their left, and then the next person to the left will take a turn. This will continue until one person remains, which person is it?

Since that explanation is hard to do without an example, lets do one. Suppose N=5, then we start with 1 killing 2, 3 goes next, killing 4. 5 is next to take a turn, and 1 is to their left, so 1 dies and we only have 3 and 5 remaining. 3 goes next, killing 5 and the solution to the puzzle is 3.

So, in general, for an arbitrary N, who is the last person standing?

Then a year passed

Alright, that was a good year of not blogging, but I'm back, for today, who knows for how long. Anyway, time to post the solution to the funny Knights and Knaves puzzle from last time.

First, I will refer to each person at the party by naming them with the number of truth tellers they claim to have shaken hands with. Now, you can determine right away that person 99 must be a liar, as if he did shake hands with 99 truth tellers then everybody would be a truth teller, including the individual who claims to have shaken hands with nobody. This is a contradiction, so person 99 is a liar. One can continue this down by looking at person 98 next. Since 99 is a liar, in order for 98 to be telling they truth, everybody else must be a truth teller, but this agian would make person 0 a liar, since 98 shook hands with everybody (except possibly 99) in this assumption. So 98 is also a liar.

This logic continues down, making all individuals who claim to have shaken hands with a positive number of truth tellers liars. This leaves only person 0 as a possible truth teller. As there were no other truth tellers at the party, it is certian that person 0 shook hands with no truth tellers, thus person 0 is in fact a truth teller. This gives the answer to the puzzle as 1, there is only 1 truth teller at the party.

Somebody had pointed out to me that there is a silly solution that works out, since the answer is independent of the knowledge of who shook hands with who, it is possible there were no handshakes. In that case person 0 is telling the truth, and everybody else is a liar. This has no contradictions and must be a possible solution, so if there is actually a solution to the puzzle, then the solution must be 1. I'm always reluctant to actually use this sort of solution, as it feels like something of a hack to assume a solution exists and then go from there, but it does often work to use this trick.

Knight Party

Oh right, I have a blog I'm supposed to maintain. All sorts of new puzzles these days, means I will proably forget them all before I manage to post them.

So, this is a knights and knaves puzzle, which I have in the past said I don't like, but I keep finding interesting ones (for those that don't recall, "knights" are people who always tell the truth, and "knaves" are people who always lie, not that that is actaully relevant for this puzzle, but it sets the tone a bit).

I got this puzzle from Presh Talwalkar's YouTube channel:

There is a party with 100 people, and each person is either a truth teller or a lair. At the party, some of the people may shake hands with eachother, and after the party you ask each person "How many truth tellers did you shake hands with?". The people each give a different answer, with each integer from 0 to 99 appearing as an answer.

How many truth tellers are at the party?

Naturaly, you can take it as given that if A shakes hands with B, then B also shook hands with A, you may also assume that nobody can shake hands with themselves. It is possible that everybody shook hands with everybody else, or simply that there were no handshakes, or anything in between of course. The solution is nothing special, but it is a nice logical solution.

Pascals Cube

Well, summer has now mostly gone by with no posts from me on that puzzle about the cube of resistors, so I guess I'll solve it now.

The thing to do for the initial puzzle in three dimensions is conisder the eight vertices of the cube and apply a potential difference of V between one vertex and the opposite corner. We could then find the current and the ratio would give us the resistance. The trick is then to notice that the three vertices that are one edge away from the starting vertex are an equpotential, so they can be fused into a single vertex. Then notice that the three vertices that are adjacent to the final vertex are also an equipotential. We then have only 4 vertices, the first is connected to the second by 3 resistors, the second connected to the third by 6 resistors (takes a bit of work to confirm that 6) and the third is connected to the fourth by 3 resistors. Since M 1-Ohm resistors in parallel have an effective resistance of 1/M, the equivalent resistance of this is 1/3+1/6+1/3=5/6

OK, thats fun, and should generalize pretty fast, but we need to see exactly how. In N dimensions, each vertex can be represented as a series of N zeros and ones, and this is a complete list of the 2^N vertices, each vertex is connected to the N vertices next to it, so any vertex has N edges on it. So N edges lead out from the initial vertex to the first equipotential. Next, the N vertices have 1 edge leading backward, and N-1 leading forward, so there are a total of N*(N-1) edges leading to the next equipotential (This is N*_N-1C₁). The next _NC₂ vertices each have N*(N-1)/_NC₂ (which is 2) edges from beind them, so there are N-2 going forward. This means there are a total of N(N-1)/2*(N-2) vertices going forward (this is N*_N-1C₂. As you can guess, the number of vertices going forward is always N*_N-1C_k, with k going from 0 to N-1.

So, in order to find the total resistance, we simply need to add up 1/N*_N-1C_k, which is 1/N times the sum of the recriprocials of the N^th row of Pascal's triangle. This doesn't really have much of a closed form, but its enough to let you figure out the specific number for any particular value of N. There is a bit of a question left of the infinite limit, and fortunately Ben found a paper called "Sum of the reciprocals of the binomial coefficients", which should be easy enough to find if you are interested, the main point here though is that the limit of the sum at large N is 2, therefore the effective resistance is 2/N. Not much of an answer I guess, but I'm always happy when Pascal's triangle shows up.

Resistor Cube

Two posts in one month? Crazy. Anyway, I got a new puzzle, which I learned from the electromagnetism course I was teaching this term....well, sort of, I expanded a simpler puzzle into a surprisingly awesome one.

Consider a cube, whose edges are 1 Ohm resistors, what is the effective resistance between opposite corners of the cube?

Sad that its really a physics puzzle, I prefer doing more math when I can, but I'm not sure how to turn this puzzle into a fully mathematical one. Anyway, the real puzzle is to generalize that puzzle into N dimensions. So, have fun with that.

Partitioning

So, I have a few new puzzles in the bank now, so I need to get to blogging again to spend them. I guess I need to start with my solution to the number puzzle from last time.

So, we have a list of numbers L, with n elements, whose sum is S, and the sum is known to both people. Further, they have a product P and if you knew P, n, and S, the list is not uniquely specified. We want to find the list that has these properties with the smallest S possible. We are looking for two lists I will call L₁ and L₂.

Its easy to see that L must have more than 2 numbers, since if you adjust two numbers and keep their sum the same, the product must get larger for the list that has the numbers closer together (you maximize the area of a rectangle by making it more square). So the list will need at least 3 numbers. Further, if L₁ and L₂ have any numbers in common, we may as well delete the common numbers from both lists, as they will still have equal total sums and products after common numbers are deleted.

At the point it is basically a matter of playing around, the first solution I found was {2,2,10} and {1,5,8}, which was just playing around with the possible prime factorizations of numbers that seems like good canditates. I was quite certian this was the smallest solution, I am quite sure (but less than 100% sure) that there are no solutions with n=3 that have a smaller S, and I had assumed there wouldn't be a smaller S that used larger n, but then Ben told me he had a solution with S=12, so I had to go looking. Eventually I found it as {2,2,2,6} and {1,3,4,4}. Ben says he has proved with a computer that there are no smaller S solutions, but I am interested if there are any solutions out there with a smaller P, however I doubt it.

Anyway, thats all I got here.

Numbers In A Room

Guess its time for a new puzzle, so I can claim to post at least once a month. This is one Ben showed me, but I am rewording it heavily from the original:

Walking through a building, you overhear a conversation two people are having in a room:
Person 1: I have written down a list of positive integers whose sum is the room number of this room.
Person 2: If you were to tell me how many numbers were on the list and their total product, would I be able to figure out what numbers were on the list, given that I already know the room number we are in?
Person 1: No, you would not.
Person 2: Alright, I now know the total product of the numbers.
What is the smallest room number they could be in?

The "theme" might be a bit thin, but it wasn't any better in the original, and at least this makes it clearer.

Order or Not

Solution time?? Solution time. Puzzle last time was the one about magical balloons. The solution is far from unique, but here is the one I found:

Step 1: Name the balloons 1,2,3,4, measure 1 and 2 in the machine. If the machine tells you that either zero or two of them are magical, you can just test the other two balloons one at a time using your remaining two measurements. So proceed assuming we got a result of one.

Step 2: Test 2 and 3 in the machine. If the result is zero, you know 1 is magical and you can test 4 alone. If the result is two, you know 1 isn't magical and agian you can test 4 alone. If the result is one, then either 1 and 3 are both magical and 2 is not, or 2 is and 1 and 3 are not.

Step 3: Test 1, 3, 4 together in the machine. The result being odd will point at 4 being magical, while being even will indicate 4 is not magical. The result being two or three will mean 1 and 3 are magical and 2 is not, while the result being zero or one will mean 1 and 3 are not magical and 2 is.

One flaw that I didn't like about this strategy is that it isn't memoryless, the tests I intend to do each step depends on the results of previous steps, and you can come up with memoryless strategies. However, if you look at the last path of my strategy: Test 1&2, then 2&3, then 1&3&4, that will work to be a memoryless strategy, you just have to analyise your results when you are done. I do not know of any strategy that is totally memoryless, that is, one that there is no path through it that you couldn't have just used from the start as a memoryless strategy.

Other things I don't know about this puzzle: how the heck to generalize it to N balloons and K measurements, so thats a thing to work on.

Magical Balloons

Alright, time to make a post so that I have at least managed to keep up 1 a year. I have a new puzzle Ben gave me ages ago, but I still haven't solved it and would feel wrong posting it when I have no ready solution. In the meantime, here is a puzzle I got from Tanya Khovanova's Math Blog:

You have 4 balloons (blue, red, green, and yellow, if you like) and some of them might be magical. You have a machine that you may put any number of balloons in and it will tell you how many balloons inside are magical. Find all the magical balloons using the machine not more than 3 times.

If you like you can also generalise, replace 4 with N and 3 with K, for which K can you solve the N balloon problem?

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.