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.
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:
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 2k+M, for some M less than 2k (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 2k be the largest power of 2 less than or equal to N, and let M=N-2k. 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?
Subscribe to:
Posts (Atom)
