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.

Genuine Coins

Research is hard, blogging is easy.... In conclusion, time for the solution to that mass puzzle from last time.

I guess I will go through the solution as I found it. First of all, note that if your first measurement is imbalanced, you are probably home free. If the left is heavier than the right, then the right cannot have more than 1 fake mass, and therefore you can divide the right into two piles (throwing out an odd mass if you need to) and use those for your second weighing. Whichever side is lighter cannot have any fakes, and if they are both equal then neither has fakes. Thus if the first measurement has N masses to a side, then if it is unbalanced you can find N/2 genuine masses (or (N-1)/2 if N is odd).

This means that we only need to solve the case where the first measurement is balanced, and this is much more difficult to deal with (as you almost certainly found if you tried to solve it). My first solution found at least 10 genuine masses as follows: Begin by dividing up the masses into 4 groups, A has 10 masses, B has 20, C has 30 and D has 40. Next, weigh A+B against C, if this is imbalanced, use the method above to find at least 15 genuine masses. If it is balanced, this means that A+B and C each have the same number of fakes, either 0,1, or 2 each. This means that D must have 0,2, or 4 fakes, this restriction is very important. Next, weigh A+C against D. Suppose this is balanced as well. Then D must have 2 fakes (it can't have 0, for C would have 2 then), but if D has 2 fakes and this measurement is balanced, then B is free of fakes. Alright, suppose this measurement has D heavy, then if D has 2 fakes, C must have 1 and A+B has 1, but its not in A, so A is genuine, if D instead had 4 fakes, A is still genuine. Finally, if A+C is heavy, then D has 0 fakes.

So, each result in our second measurement points to one coin pile, D heavy implies A, balanced implies B and A+C heavy implies D. Thus we are guaranteed to find at least 10 genuine masses.

We can generalize this, have 4 yet unspecified piles, A,B,C,D and use the method above. This means we must obey the equations:

A+B=C
A+C=D
A+B+C+D=100

Three equations for 4 unknowns, so there is a one-dimensional degree of freedom. We use that freedom to maximize min{A,B,D}. To be strict we also want to make sure that (A+B)/2 isn't too small, just in case the first measurement is balanced, but that isn't really an issue.

One can solve those equations as to get

A=3D/2-50
B=100-2D
C=50-D/2

Just looking at integer values of D and maximizing min{A,B,D} the solution is when D=42

A=13 B=16,C=29

So this guarantees getting 13 genuine masses. One funny point, there is a "better" solution at D=300/7=42+6/7 with

A=100/7=14+2/7
B=100/7=14+2/7
C=200/7=28+4/7

So, if you can use fractional masses, this is better.

Anyway, on Tanya Khovanova’s Math Blog they discuss a solution with 14 masses, but never explain it fully. This might be related to my fractional solution, but that is slightly crazy. Anyway, this solution can be constructed using the following structure for piles: A=14, B=14, C=29, D=42, E=1

First weigh A+B+E vs C, if it is imbalanced, then you can find 14 genuine ones. If it is balanced, then D again has 0,2, or 4 fakes in it, corresponding to C having 2,1, and 0 fakes in it.

Next weigh A+C vs D+E. If this is balanced, then D must have 2 fakes, C has 1 and A has 1, so B+E are all genuine (had D no fakes, C would have 2 and E cannot make up for it). If this measurement has D+E heavy, then D cannot have 0 fakes (C would have 2) so if D has 2 fakes, C has 1 and A cannot have any, so A is genuine (if D has 4 fakes, A is also genuine). Finally, if our measurement has A+C heavy, then D cannot have 2 fakes in it, so D is genuine.

So we have A+C heavy implies D is genuine, D+E heavy implies A genuine, and balanced implies B+E genuine. This guarantees at least 14 genuine masses are found. The word genuine has lost all meaning to me at this point.

Masses Again

Alright, another puzzle from Tanya Khovanova’s Math Blog. This one is another counterfeit mass thing.

There is a pile of 100 masses, and 4 of them are slightly heavier than the others. The 96 'true' masses are identical to eachother in weight, and the 4 'fakes' are slightly heavier than the others, but also identical to eachother in weight. Using 2 measurements on a balance scale, identify at least one 'true' mass.

As a follow-up, you can try to identify a collection of true masses, how many can you find in those two measurements? For rules on the balance scale, it is the same as the old one from the counterfeit masses puzzle.

I know that typically people make the counterfeits lighter than the genuine ones, but then it screws me up when I write the solution because I want the heavy ones to be the odd ones out.