Dots On A Line

Alright, I think I've finally run out of puzzles if I'm going to post this one. It is a rather crazy one that I solved with Matt many years ago and I absolutely love the answer to it. Sadly there isn't really a clean way to solve the puzzle, you have to do it the hard way, and its really not very illustrative of why the final answer is what it is, but thats just life. I initially found this puzzle at cut the knot:

Consider the unit interval between 0 and 1. Select N points randomly on that interval (random with uniform distribution). From each selected point "color in" the part of the interval between it and the closest neighboring point. In the limit as N goes to infinity, what fraction of the interval is colored in on average?

Terrible, I know. To clarify, suppose we had N=5 and selected the points 1/10, 2/10, 4/10, 7/10 and 8/10. Then from 1/10 we would color to 2/10, from 2/10 we would color back to 1/10 (not that that does anything), from 4/10 we color back to 2/10, from 7/10 we color to 8/10 and from 8/10 we color back to 7/10 (again does nothing). Then the colored region would be [1/10,4/10] ∪ [7/10,8/10] so in total 4/10 of the interval was colored in, in this case.

Balancing It Out

Time for the solution to the recent balance scale puzzle.

First, notice that there is a symmetry in the problem that needs to be broken, specifically there is no real distinction between "fake" and "genuine", if you swapped those labels the problem is identical. Let us break that symmetry by selecting a single coin and then we are going to show that all the other coins weigh the same as that special one. In effect, I will declare any coin with the same mass as that one to be "genuine" and a coin of any other mass to be "fake".

Now that we have one genuine coin, take the other nine coins and divide them up into three disjoint sets, one of two coins, one of three coins, and one of four coins. We will denote these sets of coins as 1, 2, 3, and 4, so if I say we weigh 3 vs 1+2 I mean to take the set of three coins and weigh them against the set of two coins plus the single genuine coin.

Naturally, our three weighings are going to be some coins against some other coins, equal in number, such that if a weighing is ever imbalanced we are done immediately (we would have proven there is at least one fake and one genuine coin), so we are free to assume that all weighings are balanced (as opposed to other balance scale problems where you have to divide up the tree into "if left heavy", "if right heavy", and "if balanced").

First weighing, 3 vs 1+2. When this is balanced, we know that the number of fakes in 2 (call that x) equals the number of fakes in 3 (so, x is also the number of fakes in 3). Second weighing, 4 vs 1+3. When this is balanced, we know the number of fakes in 4 is also x. Finally, we weigh 1+4 vs 2+3. When this is balanced we know that x=x+x, guaranteeing that x is 0 and there are no fake coins.

It is sort of neat that you can do those weighings in any order you want, since you don't gain information after a weighing (or rather if you did, you were done right away). But if you do the weighings in another order the information is a bit less natural to analyze.

More Masses?

Alright, new puzzle I found today at Tanya Khovanova’s Math Blog:

Consider you have a collection of 10 coins. The coins can either be genuine or fake, a fake coin weights a slightly different amount than a genuine coin. All fake coins weigh the same and all genuine coins weigh the same. Using three measurements on a balance scale, prove either that all the coins have the same mass or that they do not.

For the balance scale rules, see the old counterfeit masses puzzle. These constant balance scale problems and total lack of hat problems are making me want to rename the blog "Standard Balance Scale Rules Apply".

All Drunk

So, whats the solution to running out of interesting puzzles? Stop posting. I guess the other solution is to post non-interesting puzzles, or possibly interesting non-puzzles, but that seems like so much more work than not posting at all. Anyway, I guess one should post the solution to the drinking game puzzle from last time.

First of all, it is obvious that Alice can get a 1/2-1/2 split with Bob if she wants, so the only question is if she can do any better than that. Bob being forced to drink from the bottle at least once is a disadvantage for him, if not for that rule it is clear that the optimal strategy is 1/2-1/2 in general. Since Bob being forced to drink from the bottle is a disadvantage, we can assume he will try to get rid of that, specifically if the bottle ever has less poison than the cup, Bob will immediately drink from the bottle and the remaining bottles will get split 1/2-1/2.

As soon as Bob has drank from the bottle, the remaining bottles get split 1/2-1/2. If we get to the last bottle and Bob has not yet drank from the bottle, Alice will do a 1-0 split, forcing Bob to drink all of the poison in the bottle. Thus, if there are two bottles left, let us assume Alice does an x-y split (x>y and x is the amount in the bottle). If Bob choses x, he will have free choice on the next one and in the end Bob will have drank x+1/2 and Alice will have drank y+1/2. If Bob choses y, Alice will be able to force him to drink all of the last bottle and so Bob will drink y+1 and Alice will drink x. Bob will see this coming and choose whichever one is lower, so Alice does best to make them equal.

We have x+1/2=y+1 and x+y=1, so we get x=3/4 y=1/4, so if there are two bottles left and Bob must still drink from a bottle once, Alice splits 3/4-1/4 and forces Bob to drink 5/4. Obviously if there are two bottles left and Bob does not have to drink from a bottle, then Bob drinks half of each of the remaining bottles for a total of 1.

Now, if there are three bottles left and Bob must drink from the bottle once (the original problem), then Alice splits the first bottle x-y (x>y and x the bottle) and Bob can select either x+1 or y+5/4. Setting those equal and using x+y=1 we get x=5/8 y=3/8. So Alice divides up the first bottle 5/8-3/8 and forces Bob to drink 13/8 in total, whereas Alice only drinks 11/8.

Drinking Game

New puzzle time? It seems like that can only cause disaster when I finally run out of puzzles. My usual sources seem to be drying up, but I guess I have a few left. This one is from the xkcd forums (though, reworded):

Alice and Bob are going to be playing a game where they must drink poison. There are three bottles of poison to be divided among the players and the goal is to drink as little as possible (as some amount of the poison is lethal, but the players do not know how much). The game begins with Alice pouring some amount of the first bottle into a cup, then Bob selects if he would like to drink everything in the cup or everything in the bottle. Whichever one he does not choose Alice must drink. Then Alice pours some of the second bottle into a cup and Bob chooses who will drink from the cup and who will drink from the bottle, finally the third bottle is divided the same way. A special rule is in place however, Bob is not allowed to select from the cup all three times, he must select the bottle at least once. How should Alice divide up the bottles to minimize the amount she must drink?

Poker Time

Guess its time to blog again. The double draw poker problem has been up for ages, and my readership (yes, you) is probably bored of it.

The solution isn't hard to get at, the first thing is to notice that if Bob is able to grab an ace-high straight flush with his first move then the game is over right away (one might call an ace-high straight flush a "royal flush", but I absolutely hate that notation). So we see that Alice must block all four of the ace-high straight flushes right away, perhaps by taking all four aces and some other random card.

If Bob responds to this by taking any straight flush, Alice can get an ace-high straight flush and win (Bob cannot match that hand because he cannot access any of the aces). However, if Bob responds by grabbing all the kings, then Alice cannot do anything. She can get a queen-high straight flush, but Bob can beat that easily. Apparently just grabbing all the aces does not work.

One can try all the kings or whatever, but it is pretty apparent pretty fast that taking all the tens is the solution. After Bobs next move, Alice grabs an ace-high straight flush if she can, or a ten-high straight flush if she cannot. Without any tens, the best Bob can do is a nine-high straight flush.

Pretty simple, I know, but for some reason I like it.

Double Draw Poker

Alright, a bit of an unusual puzzle this time, but I thought it was sort of neat. I first found this on the xkcd forums:

Alice and Bob are going to play a poker variant. A standard 52 card deck is laid out face up in front of them. Alice goes first, and gets to select any 5 cards from the deck. Then Bob gets to select any 5 cards that are still in the deck (not being allowed to select any cards Alice selected). Then Alice may discard any of her cards and replace them with cards still in the deck (discarded cards are removed from the game and do not return to the deck). Then Bob may discard any of his cards and replace them with cards from the deck. At this point, the game ends and whoever has the better poker hand of 5 cards wins. If both players have equal ranked hands, then Bob wins the game (that being the compensation for going second). Who wins this game when played optimally?

If you don't know the rankings of poker hands, you are beyond help. I guess you could look them up, but I actually would say you won't find this puzzle even slightly interesting so don't even bother.