Ask if he knows if one of Porthos or Aramis got at least two gold coins. If Athos got two of the three gold coins, he knows the answer is no. If Athos got no gold coins, then given that all three were given out he knows that the answer is yes. If Athos got one gold coin then he will not be sure.Of course, you can switch "gold" for "silver" in that solution if you like. Anyway, simple, like I said, but I sort of thought it was neat. I would love to hear any alternate solutions, I haven't thought of any but they probably exist.
Showing posts with label coins. Show all posts
Showing posts with label coins. Show all posts
Just One
OK, time for the solution to the coins puzzle from last time.
Not much derivation to do, so I'll just sort of post my solution:
Coins Again
Alright, new puzzle time. I have a bit of a backlog of decent puzzles, so its important for me to waste them as soon as possible so I go back to not blogging again.
I got this one off of Tanya Khovanova's math blog, well, sort of, I misread the puzzle and solved a variant, but I think the variant is better so I'm going with it:
Athos, Porthos, and Aramis were rewarded with six coins: three gold and three silver. Athos got two coins. Athos doesn’t know what coins the others got, but he knows his own coins and he knows all the coins were given out. Ask him one question to which he can answer “Yes,” “No,” or “I do not know,” so that you will be able to figure out his coins.My misread was that in the initial puzzle, instead of "Athos got two coins", it was "Each got two coins". My solution worked for both, and I somehow feel that my version is harder (being that you have less information), but its not clear that taking away information from Athos (which my variant also did) actually makes it harder. Anyway, yeah, its simple, solve it out.
Odd Coins
So, apparently I just stop blogging when I have a semi-academic job, but don't have an office to go with it. Anyway, its about time for the solution to the coin puzzle from last time.
So, I suspect that somebody who works with the Fibonacci numbers alot will not really have much of a problem with this puzzle, there are a reasonable number of relationships the Fibonacci numbers obey that make the puzzle quite straightforward. First of all, I will give my definition of the Fibonacci numbers for the purpose of this puzzle:
f1=1 f2=2 fk=fk-1+fk-2I call this "my definition for the purpose of this puzzle" because nobody would ever normally start the Fibonacci numbers off with 1 and 2, 1 and 1 is most common, and 0 and 1 sometimes, but 1 and 2 is being chosen for this so that there are no repeats in the sequence {fk} for k>0. Next, I will derive an identity that will be needed for the solution:
2fk=fk+fk-1+fk-2 =fk+1+fk-2A short derivation, but an important one. Alright, now suppose the set of Fibonacci numbers is not a greedy set. Then there is a number C such that C can be expressed as a sum of K Fibonacci numbers {fi1,fi2,...fiK} and the greedy algorithm uses at least K+1 such numbers. We will assume that C is chosen to be the smallest such number (if any exist, there must be a smallest one). Naturally C is not one of the fn, so let M be the largest number such that fM<C. I claim that fM is not in the list {fi1,fi2,...fiK}. If it were, then the greedy algorithm would use the coin fM and then optimize C-fM. However, the list {fi1,fi2,...fiK} adds to C and so if it contains fM then C-fM can be expressed using K-1 Fibonacci numbers, but the greedy algorithm would be able to optimize this, as C was the smallest counterexample. Alright, so we have proven that the list {fi1,fi2,...fiK} does not contain fM. It is also obvious that it does not contain two consecutive Fibonacci numbers (if it did, we could make it more efficient). Finally, it can be made to not contain the same number twice, for if it did we could use our earlier identity to replace 2fk with fk+1 and fk-2. I claim that a list of Fibonacci numbers fj with J less than M with no consecutive numbers and no repeats cannot add to larger than fM. This can be proven as follows:
fM=fM-1+fM-2 =fM-1+fM-3+fM-4 =fM-1+fM-3+fM-5+fM-6Continue on this logic, until you get down to f1. We see that our list {fi1,fi2,...fiK} cannot add to larger than fM, but C was larger than fM, so we have a contradiction, proving there is no smallest counterexample. Thats all I got for now, I might post the full solution to the greedy sets of the form {1,a,b} next time, or I might just move on to a new puzzle, we will see.
Halfway
I guess its about time I post the solution to the coin puzzle from last time. I guess I could solve out the n=1 case first and then generalize, but it isn't particularly interesting to do that, so I think I'll just solve the general problem outright.
So we have 4n+1 coins and in a single step we can find the median of 2n+1 of them, and we have n+2 steps to work with. Now, the goal is to identify the median coin, which I shall call M. We will know a particular coin is coin M if there are exactly 2n coins heavier than it and 2n coins lighter than it.
Begin by selecting any 2n+1 coins and putting then in the machine (there is no other first step, of course), take the median coin and paint it red (I will be painting coins as we move along so that I can refer to particular groups of coins). Set the red coin aside and grab any other coin to measure with those same 2n coins. Repeat this process until you have done n+1 measurements and have n+1 red coins. Paint the other 2n coins involved in those measurements yellow, and the remaining n coins blue.
I claim that if you sorted the yellow and red coins by weight, the order would be n yellow coins, followed by all n+1 red coins, followed by the other n yellow coins, that is to say that each red coin has exactly n yellow coins lighter than it and n yellow coins heavier than it. This happens because if you were to start with the 3n+1 yellow and red coins and measure any 2n+1 of them, each time a coin from the middle n+1 of them will come out, that is, by finding medians and setting them aside, you find the middle n+1 of them, and those are the ones we are calling the red ones.
Now, with our last measurement, measure the n+1 red coins with the n blue ones, and call the median of that measurement P. I claim the P is the median coin M. We can see this in two cases, first if P is red, we know that P has n yellows above it and n yellows below it in weight. But P also has n non-yellows above and n non-yellows below it in weight (because it was the median of the final measurement), proving P is M. If P is blue, then it must lie strictly between two reds, since there must be n non-yellows above it and n non-yellows below it and n+1 of the non-yellows are red. Since it lies between two reds, it must have n yellows above it and n yellows below it. So this coin is had n yellows and n non-yellows above it, and also n yellows and n non-yellows below it.
Fun stuff.
So we have 4n+1 coins and in a single step we can find the median of 2n+1 of them, and we have n+2 steps to work with. Now, the goal is to identify the median coin, which I shall call M. We will know a particular coin is coin M if there are exactly 2n coins heavier than it and 2n coins lighter than it.
Begin by selecting any 2n+1 coins and putting then in the machine (there is no other first step, of course), take the median coin and paint it red (I will be painting coins as we move along so that I can refer to particular groups of coins). Set the red coin aside and grab any other coin to measure with those same 2n coins. Repeat this process until you have done n+1 measurements and have n+1 red coins. Paint the other 2n coins involved in those measurements yellow, and the remaining n coins blue.
I claim that if you sorted the yellow and red coins by weight, the order would be n yellow coins, followed by all n+1 red coins, followed by the other n yellow coins, that is to say that each red coin has exactly n yellow coins lighter than it and n yellow coins heavier than it. This happens because if you were to start with the 3n+1 yellow and red coins and measure any 2n+1 of them, each time a coin from the middle n+1 of them will come out, that is, by finding medians and setting them aside, you find the middle n+1 of them, and those are the ones we are calling the red ones.
Now, with our last measurement, measure the n+1 red coins with the n blue ones, and call the median of that measurement P. I claim the P is the median coin M. We can see this in two cases, first if P is red, we know that P has n yellows above it and n yellows below it in weight. But P also has n non-yellows above and n non-yellows below it in weight (because it was the median of the final measurement), proving P is M. If P is blue, then it must lie strictly between two reds, since there must be n non-yellows above it and n non-yellows below it and n+1 of the non-yellows are red. Since it lies between two reds, it must have n yellows above it and n yellows below it. So this coin is had n yellows and n non-yellows above it, and also n yellows and n non-yellows below it.
Fun stuff.
Median Coins
Where the heck did that month go? Anyway, I finally managed to get another puzzle to put up. Technically, its a varaint of one I found on Tanya Khovanovas math blog:
And a somewhat generalized version:
In Tanyas version, Baron Münchhausen identifies the coin of median weight ahead of time, and you must use the machine no more than n+2 times to confirm if he is right. When I found my solution to the problem though, I noticed that I didn't need that extra information, I could simply confirm if he was right by using my method and checking if his median was the same as mine. Anyway, I guess its still possible I did something stupid and am wrong, so if you are unable to solve the problem as I posted it try Tanyas version instead, mine might just be impossible.
You have 5 coins of distinct weights, and you have a machine that if you put in 3 coins of distinct weights it will identify the coin of median weight. Of the 5 coins, find the coin of median weight using the machine no more than 3 times.
And a somewhat generalized version:
You have 4n+1 coins of distinct weights, and you have a machine that if you put in 2n+1 coins of distinct weights it will identify the coin of median weight. Of the 4n+1 coins, find the coin of median weight using the machine no more than n+2 times.
In Tanyas version, Baron Münchhausen identifies the coin of median weight ahead of time, and you must use the machine no more than n+2 times to confirm if he is right. When I found my solution to the problem though, I noticed that I didn't need that extra information, I could simply confirm if he was right by using my method and checking if his median was the same as mine. Anyway, I guess its still possible I did something stupid and am wrong, so if you are unable to solve the problem as I posted it try Tanyas version instead, mine might just be impossible.
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.
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:
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".
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".
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:
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
Just looking at integer values of D and maximizing min{A,B,D} the solution is when D=42
So this guarantees getting 13 genuine masses. One funny point, there is a "better" solution at D=300/7=42+6/7 with
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.
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.
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.
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.
Two At Most
Time to post the solution to the follow-up coin problem from last time. The solution isn't hard to come by, and is basically an extension of the first move of the solution from last time. Last time the first measurement was the 1,2,3 against the 6 and since they balanced, you knew for a fact that the 6 was in fact the 6 (it is the only single coin that can weigh as much as three others). This time you weigh the 1,2,3,4,5 against the 7,8. They will come out balanced, but there is no way the left side weighs less than 15 and no way the right side weighs more than 15, so they must each be exactly those weights. This leaves the 6 uniquely identified.
Actually, this question has an interesting generalization, if we have N coins with masses 1 through N and we know their masses, how many measurements of a balance scale does it take to prove the mass of one of the coins? It is easy to prove that you can always do it in three or fewer measurements as follows: N can be written as a sum of 3 triangle numbers (this is a result of the Fermat polygonal number theorem, though for triangle numbers it was initially shown by Gauss). Call these numbers A, B, and C, assume that A ≥ B ≥ C. Weigh 1,2,3,4...k against A such that they balance (we know such a k exists, A is triangular), the balancing proves that the weights on the right has a mass at least A. Next weight 1,2,3,4,...m and A against (B+A), (B+A) being the single mass of mass B+A, and m is defined by 1+2+3+4+...+m=B. When they balance it proves that B+A is at least B+A. Finally weigh the 1,2,3,...j and (B+A) against N, where j is defined by 1+2+3+4+..+j=C. When they balance it proves that N is at least N. But N is at most N, so N is identified.
Actually, two weighings is always sufficient to prove that you can find one mass, this was proven in a paper entitled Baron Munchhausen’s Sequence, which also contains the proof from the previous paragraph. The proof is rather long though, and there is little sense in reproducing it here.
Actually, this question has an interesting generalization, if we have N coins with masses 1 through N and we know their masses, how many measurements of a balance scale does it take to prove the mass of one of the coins? It is easy to prove that you can always do it in three or fewer measurements as follows: N can be written as a sum of 3 triangle numbers (this is a result of the Fermat polygonal number theorem, though for triangle numbers it was initially shown by Gauss). Call these numbers A, B, and C, assume that A ≥ B ≥ C. Weigh 1,2,3,4...k against A such that they balance (we know such a k exists, A is triangular), the balancing proves that the weights on the right has a mass at least A. Next weight 1,2,3,4,...m and A against (B+A), (B+A) being the single mass of mass B+A, and m is defined by 1+2+3+4+...+m=B. When they balance it proves that B+A is at least B+A. Finally weigh the 1,2,3,...j and (B+A) against N, where j is defined by 1+2+3+4+..+j=C. When they balance it proves that N is at least N. But N is at most N, so N is identified.
Actually, two weighings is always sufficient to prove that you can find one mass, this was proven in a paper entitled Baron Munchhausen’s Sequence, which also contains the proof from the previous paragraph. The proof is rather long though, and there is little sense in reproducing it here.
Probably Correct
Alright, Canada day seems like a good time to post the solution for the labeled masses problem. Working on it yourself you probably found it is best to assume that the coins are labeled correctly and attempt to prove that rather than something else. Any method that would actually prove the coins are labeled correctly would also show that they are labeled incorrectly if they are not (if it didn't do that, one would hardly accept that it proves they are labeled correctly). Actually, this gives us something of a rewording of the problem, which I will later transform into the followup problem. Assume the coins are unlabeled, but you know which coin is which, you must prove to an audience (of mathematical puzzle solvers) that you know which coin is which using only 2 measurings.
Anyway, moving on to the solution (to the problem as initial worded). Its tricky to do anything involving weighing 1 coin against 2 right away, since if you weigh 1+2 against 3, even if it balances you cannot be sure that it was not the 1+3 against 4 or the 2+4 against the 6 or something. You could also try having 4 coins on one side, but that cannot work since on the second measurement you must split up those 4 coins or you cannot tell them apart. Perhaps something involving 2 vs. 2 works, but I didn't find anything. The thing that does work is to weigh the 1+2+3 against the 6. If it is imbalanced, we are done, if it is balanced then you have identified the 6 (it is the only one that can have as much mass as 3 others combined) and you have identified a group that is the {1,2,3}, since they are the only 3 light enough that a single coin could balance them.
So, in one measurement we have identified the {1,2,3}, the {4,5} and the {6}. The next measurement is to do the 6 and the 1 against the 5 and the 3.
If they are labeled correctly, the 5+3 should be heavier than the 6+1 (so, if that doesn't happen we are done). Since the 6 is identified, and the 1 must weight at least 1, the 6+1 must weigh at least 7, but since the 5+3 came out heavier, the 5 could not be any lighter and neither could the 3, so the 5 and 3 are correct. By a similar logic, the 5+3 cannot together weight more than 8, so the 1 cannot afford to be any heavier if the 6+1 is to be less than 8, thus the 1 must be the 1. That leaves the 2 and 4 both uniquely identified.
This completes the solution. I cannot prove that there aren't any other solutions, but I greatly doubt their existence.
Next, the follow-up:
You may assume that the audience knows that the coins have masses 1 through 8, but they do not know which one is which. After one measurement, the mathemagician must be able to select a single coin and say "I have now proven this one is the x" for some value of x. You may also assume the audience is a bunch of mathematicians, they will not be tricked by some sort of lies.
Anyway, moving on to the solution (to the problem as initial worded). Its tricky to do anything involving weighing 1 coin against 2 right away, since if you weigh 1+2 against 3, even if it balances you cannot be sure that it was not the 1+3 against 4 or the 2+4 against the 6 or something. You could also try having 4 coins on one side, but that cannot work since on the second measurement you must split up those 4 coins or you cannot tell them apart. Perhaps something involving 2 vs. 2 works, but I didn't find anything. The thing that does work is to weigh the 1+2+3 against the 6. If it is imbalanced, we are done, if it is balanced then you have identified the 6 (it is the only one that can have as much mass as 3 others combined) and you have identified a group that is the {1,2,3}, since they are the only 3 light enough that a single coin could balance them.
So, in one measurement we have identified the {1,2,3}, the {4,5} and the {6}. The next measurement is to do the 6 and the 1 against the 5 and the 3.
If they are labeled correctly, the 5+3 should be heavier than the 6+1 (so, if that doesn't happen we are done). Since the 6 is identified, and the 1 must weight at least 1, the 6+1 must weigh at least 7, but since the 5+3 came out heavier, the 5 could not be any lighter and neither could the 3, so the 5 and 3 are correct. By a similar logic, the 5+3 cannot together weight more than 8, so the 1 cannot afford to be any heavier if the 6+1 is to be less than 8, thus the 1 must be the 1. That leaves the 2 and 4 both uniquely identified.
This completes the solution. I cannot prove that there aren't any other solutions, but I greatly doubt their existence.
Next, the follow-up:
A mathemagician has 8 coins, with masses 1 through 8, he knows which coin is which. He intends to prove to an audience that he knows the correct mass of at least one of the coins using a single measurement of a balance scale. What measurement can he perform to prove the mass of any one of the coins?
You may assume that the audience knows that the coins have masses 1 through 8, but they do not know which one is which. After one measurement, the mathemagician must be able to select a single coin and say "I have now proven this one is the x" for some value of x. You may also assume the audience is a bunch of mathematicians, they will not be tricked by some sort of lies.
Labeled Masses
So, Mark seems to be quite the source of new puzzles recently, I guess its those crazy people in his office or something. Anyway, here is the latest one from him:
It is the same balance scale as the counterfeit masses puzzle, that is to say, using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it, or that they are balanced. The button will work 2 times and then the scale will break.
There are 6 coins on a table, having masses of 1,2,3,4,5,6 grams. They are also labeled 1 through 6. Using two weighings of a balance scale, you must prove if they are correctly labeled or that they are not.
It is the same balance scale as the counterfeit masses puzzle, that is to say, using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it, or that they are balanced. The button will work 2 times and then the scale will break.
The Value Of One Bit
I was looking over my "solution" threats, and it seems that about 90% of them begin with "time to post the solution to", so I figure I'm about sick of that. Sick of it this week anyway, next time I'll be back to it. Anyway, now that I have actually began the post with something different, time to post the solution to the bit in a bottle problem.
First I will give my formulation of the solution, and then I will show that it is optimal in a sense (a pretty convincing sense as well, not just some esoteric one). First, consider what happens if you just bet heads all the time. Your total money will simply preform a random walk on the integers starting with N, and will terminate if it ever hits zero. With probability 1, it will hit zero in finite time.
Now, I will construct two strategies, first define the following strategy
Similarly, define a strategy for tails
Now, we can show that one of these strategies will hit $0 and the other will hit $2N (this should be pretty intuitive, but lets prove it anyway). For a particular sequence of flips, let M(S,k) be the amount of money that strategy S will have after k flips. Then I claim that
This is easy to prove by induction, as it is true when k=0 and every time strategy H gains $1, strategy T loses $1 and vice-versa. The strategies also terminate at the same time, as failing to do so would violate the equality. It is theoretically possible that the strategies do not ever terminate, but that has zero probability of happening.
Now, the question we ask the genie is simple. First define strategy H for the genie, then ask:
If the answer is yes follow strategy T, if the answer is no follow strategy H. This guarantees that you will end with $2N (where "guarantees" means "with probability one"). You can also change strategy H to any specific betting sequence rather than all heads if you like, as long as strategy T is the compliment of that sequence, this will still work.
Next I want to prove that this solution is optimal. It might seem surprising that we can optimize over the space of all possible questions, since math usually is not very good at handling human language. To deal with this, first consider C to be the set of all the possible coin flip results, so C contains things like HHTHH..., THTTH.., TTTHT..., and so on. Next consider a possible yes or no question, denoted Q, that for every element of C the question must answer exactly "yes" or "no". Thus Q partitions C into two disjoint subsets, called Y and N. Really, any Q is equivalent to selecting the sets Y and N and asking the genie "is the coming sequence of coin flips in Y?" So, to optimize over all questions Q, we really just need to optimize over choice of sets Y and N, and it is less surprising that math can handle that.
Before moving on, I must state an obvious but important fact of probability theory. Consider we have two disjoint events, X and Y (that is to say, exactly one of them must happen (thats not actually what disjoint means, but I don't know the correct term)), and a third event called A. Let P(x) is the probability that event x happens, and P(x|y) is the probability that event x happens given that event y happened. Then, the probability that event A happens can be written as:
That is, A must happen with X or Y, so we calculate the chance it happens with X plus the chance it happens with Y. We need not subtract the chance it happens with both, as X and Y are disjoint. It is easy to generalize this to more disjoint events X,Y,Z,... We can also make a similar statement about expectation values, let E(A) be the expectation value of some variable A and E(A|x) is the expectation value of A given that event x is true. Then for disjoint events X and Y we have:
An intuitive result, to be sure, but an important one anyway.
OK, now that that is out of the way, the next important step in the proof is to consider what will happen with no genie. Suppose you have some strategy S, and after k flips the strategy has an expected value E(S,k). The expected value will be determined by the chance that you went up a dollar on that flip (call that P(+)) and that chance that you went down a dollar on that flip (call that P(-)), and the chance that your strategy had told you to stop (call that P(O)). Specifically:
It is clear that P(+)+P(-)+P(O)=1 (since every round you either gain a dollar or lose a dollar or stop), and also P(+)=P(-) since without access to a genie we have no knowledge about the coin flips. This means that:
So, E(S,k) is a constant, and that value must equal $N, since E(S,0) is $N. This proves that with no genie, all strategies have the same expectation value after a fixed number of flips. Note that something funny happens if you just let k=∞ since strategies such as "play until I run out of money" are guaranteed to have zero money at the end, even though after a finite number of flips there is a chance of the player having a large amount of money for the time being (this is known as the "gamblers ruin").
Alright, now let us find what is the best we can do given our genie scenario. First let x represent the coming sequence of coin flips, the genie knows the value of x. Consider that we have a strategy specified by a question Q (which simply selects the sets Y and N), a strategy S(Y) (which is what we will do if the genie tells us x is in Y), and a strategy S(N) (which is what we will do if the genie tells us x is in N). We want to find E(S,k), the expectation value of our strategy S (=(Q,S(Y),S(N))) after k flips. Letting Y represent the event "x is in Y" and N represent the event "x is in N", we see that Y and N are disjoint events, so that:
I really should have some k's in there also, but they are going to get cumbersome so I am just going to drop them for now. Now, E(S|Y) is just E(S(Y)|Y), since S says to play S(Y) when Y is true, also E(S|N)=E(S(N)|N) for the same reason. That is to say
To get any more information out of this, consider again what would happen to us with no genie. We could just play S(Y) anyway, but we already know that E(S(Y))=$N (one would expect that E(S(Y)|Y) would be higher, since then we also know that x is in Y, but if we just play S(Y) with no other information then its expectation value is $N) (I must say this is only true after k flips, if the number of flips is infinite weird things might happen). How else could we calculate E(S(Y))? we could just consider if x is in Y or N, specficially
That is the value of strategy S(Y) when Y is true plus the value of strategy S(Y) when N is true (remember, we have no genie right now). Now since E(S(Y)|N) cannot be negative, and P(N) cannot be negative, that second term cannot be negative. Thus we have a bound on E(S(Y)|Y)P(Y), given by
Similarly, switching Y for N we have
and therefore
We can put this together in our last equation for E(S) to get
Proving the optimality of the solution presented earlier. It appears that the value of one bit is to exactly double your cash. If you can instead ask the genie a question with possible answers 1,2,3,... up to some fixed K then you can extend this proof to show it is optimal to multiply your money by K.
Naturally, it is possible to get other strategies to end with more than $2N, they just cannot guarantee ending with that much. Even with no genie one can simply play the game and only quit if you hit $0 or $3N, you might end with $3N in this case, but it cannot be guaranteed. I will also point out that the proof relied on the game not taking an arbitrarily long amount of time, my intuition is that the result is still valid even without that assumption, but I do not see a good proof.
I do like this solution in that it is practical, one would reasonably use it if actually presented with this situation, and the genie does not even need to do an infinite amount of work (probably not anyway, its possible that the random walk never terminates, but thats probability zero). The genie can even be replaced by a mathematically competent human who simply has access to the coming flips.
There is a harder problem posed of the xkcd forums where losing a flip costs you a $1 and winning a flip gains you $(1-q) where q is a small positive number. I have not made any real progress to finding a solution to this problem, but anything involving random walks seems risky, so another approach might be needed.
First I will give my formulation of the solution, and then I will show that it is optimal in a sense (a pretty convincing sense as well, not just some esoteric one). First, consider what happens if you just bet heads all the time. Your total money will simply preform a random walk on the integers starting with N, and will terminate if it ever hits zero. With probability 1, it will hit zero in finite time.
Now, I will construct two strategies, first define the following strategy
Strategy H: Every game, bet heads until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.
Similarly, define a strategy for tails
Strategy T: Every game, bet tails until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.
Now, we can show that one of these strategies will hit $0 and the other will hit $2N (this should be pretty intuitive, but lets prove it anyway). For a particular sequence of flips, let M(S,k) be the amount of money that strategy S will have after k flips. Then I claim that
M(H,k)+M(T,k)=$2N
This is easy to prove by induction, as it is true when k=0 and every time strategy H gains $1, strategy T loses $1 and vice-versa. The strategies also terminate at the same time, as failing to do so would violate the equality. It is theoretically possible that the strategies do not ever terminate, but that has zero probability of happening.
Now, the question we ask the genie is simple. First define strategy H for the genie, then ask:
If I follow strategy H, will I end with $0?
If the answer is yes follow strategy T, if the answer is no follow strategy H. This guarantees that you will end with $2N (where "guarantees" means "with probability one"). You can also change strategy H to any specific betting sequence rather than all heads if you like, as long as strategy T is the compliment of that sequence, this will still work.
Next I want to prove that this solution is optimal. It might seem surprising that we can optimize over the space of all possible questions, since math usually is not very good at handling human language. To deal with this, first consider C to be the set of all the possible coin flip results, so C contains things like HHTHH..., THTTH.., TTTHT..., and so on. Next consider a possible yes or no question, denoted Q, that for every element of C the question must answer exactly "yes" or "no". Thus Q partitions C into two disjoint subsets, called Y and N. Really, any Q is equivalent to selecting the sets Y and N and asking the genie "is the coming sequence of coin flips in Y?" So, to optimize over all questions Q, we really just need to optimize over choice of sets Y and N, and it is less surprising that math can handle that.
Before moving on, I must state an obvious but important fact of probability theory. Consider we have two disjoint events, X and Y (that is to say, exactly one of them must happen (thats not actually what disjoint means, but I don't know the correct term)), and a third event called A. Let P(x) is the probability that event x happens, and P(x|y) is the probability that event x happens given that event y happened. Then, the probability that event A happens can be written as:
P(A)=P(A|X)P(X)+P(A|Y)P(Y)
That is, A must happen with X or Y, so we calculate the chance it happens with X plus the chance it happens with Y. We need not subtract the chance it happens with both, as X and Y are disjoint. It is easy to generalize this to more disjoint events X,Y,Z,... We can also make a similar statement about expectation values, let E(A) be the expectation value of some variable A and E(A|x) is the expectation value of A given that event x is true. Then for disjoint events X and Y we have:
E(A)=E(A|X)P(X)+E(A|Y)P(Y)
An intuitive result, to be sure, but an important one anyway.
OK, now that that is out of the way, the next important step in the proof is to consider what will happen with no genie. Suppose you have some strategy S, and after k flips the strategy has an expected value E(S,k). The expected value will be determined by the chance that you went up a dollar on that flip (call that P(+)) and that chance that you went down a dollar on that flip (call that P(-)), and the chance that your strategy had told you to stop (call that P(O)). Specifically:
E(S,k+1)=(E(S,k)+1)P(+)+(E(S,k)-1)P(-)+E(S,k)P(O)
It is clear that P(+)+P(-)+P(O)=1 (since every round you either gain a dollar or lose a dollar or stop), and also P(+)=P(-) since without access to a genie we have no knowledge about the coin flips. This means that:
E(S,k+1)=E(S,k)
So, E(S,k) is a constant, and that value must equal $N, since E(S,0) is $N. This proves that with no genie, all strategies have the same expectation value after a fixed number of flips. Note that something funny happens if you just let k=∞ since strategies such as "play until I run out of money" are guaranteed to have zero money at the end, even though after a finite number of flips there is a chance of the player having a large amount of money for the time being (this is known as the "gamblers ruin").
Alright, now let us find what is the best we can do given our genie scenario. First let x represent the coming sequence of coin flips, the genie knows the value of x. Consider that we have a strategy specified by a question Q (which simply selects the sets Y and N), a strategy S(Y) (which is what we will do if the genie tells us x is in Y), and a strategy S(N) (which is what we will do if the genie tells us x is in N). We want to find E(S,k), the expectation value of our strategy S (=(Q,S(Y),S(N))) after k flips. Letting Y represent the event "x is in Y" and N represent the event "x is in N", we see that Y and N are disjoint events, so that:
E(S)=E(S|Y)P(Y)+E(S|N)P(N)
I really should have some k's in there also, but they are going to get cumbersome so I am just going to drop them for now. Now, E(S|Y) is just E(S(Y)|Y), since S says to play S(Y) when Y is true, also E(S|N)=E(S(N)|N) for the same reason. That is to say
E(S)=E(S(Y)|Y)P(Y)+E(S(N)|N)P(N)
To get any more information out of this, consider again what would happen to us with no genie. We could just play S(Y) anyway, but we already know that E(S(Y))=$N (one would expect that E(S(Y)|Y) would be higher, since then we also know that x is in Y, but if we just play S(Y) with no other information then its expectation value is $N) (I must say this is only true after k flips, if the number of flips is infinite weird things might happen). How else could we calculate E(S(Y))? we could just consider if x is in Y or N, specficially
E(S(Y))=E(S(Y)|Y)P(Y)+E(S(Y)|N)P(N)
That is the value of strategy S(Y) when Y is true plus the value of strategy S(Y) when N is true (remember, we have no genie right now). Now since E(S(Y)|N) cannot be negative, and P(N) cannot be negative, that second term cannot be negative. Thus we have a bound on E(S(Y)|Y)P(Y), given by
E(S(Y)|Y)P(Y) ≤ $N
Similarly, switching Y for N we have
E(S(N))=E(S(N)|Y)P(Y)+E(S(N)|N)P(N)
and therefore
E(S(N)|N)P(N) ≤ $N
We can put this together in our last equation for E(S) to get
E(S) ≤ $2N
Proving the optimality of the solution presented earlier. It appears that the value of one bit is to exactly double your cash. If you can instead ask the genie a question with possible answers 1,2,3,... up to some fixed K then you can extend this proof to show it is optimal to multiply your money by K.
Naturally, it is possible to get other strategies to end with more than $2N, they just cannot guarantee ending with that much. Even with no genie one can simply play the game and only quit if you hit $0 or $3N, you might end with $3N in this case, but it cannot be guaranteed. I will also point out that the proof relied on the game not taking an arbitrarily long amount of time, my intuition is that the result is still valid even without that assumption, but I do not see a good proof.
I do like this solution in that it is practical, one would reasonably use it if actually presented with this situation, and the genie does not even need to do an infinite amount of work (probably not anyway, its possible that the random walk never terminates, but thats probability zero). The genie can even be replaced by a mathematically competent human who simply has access to the coming flips.
There is a harder problem posed of the xkcd forums where losing a flip costs you a $1 and winning a flip gains you $(1-q) where q is a small positive number. I have not made any real progress to finding a solution to this problem, but anything involving random walks seems risky, so another approach might be needed.
Bit In A Bottle
New puzzle time I suppose. This one looked like it was a bit of a silly one, but it turns out that there is a bit more interesting math in it than I expected. I first found this on the forums at xkcd:
Earlier I had posed the problem stating that the genie knew the future, but that can cause weird possible questions involving not having a well posed question. Anyway, the intention is that the genie be capable of answering your question solely knowing what the coin flips are going to be. If a genie who knows the outcome of random events bothers you, we can instead suppose all the flips have been determined ahead of time and the genie simply has access to all the results.
Clearly with no genie, the only thing you can do will have an expected final outcome average of $N, since the game is fair for all strategies, so the question is to find out how much the one bit of information the genie gives you is worth. One thing I found interesting about this problem is that you can also prove optimality of the correct answer.
You are playing a game where you are betting on the outcome of coin flips. Playing the game costs $1 and you get to guess either heads or tails. A coin is then flipped and if you guessed correctly you win back your $1 and another $1, if you guessed wrong you lose your $1. You may play the game as many times as you want as long as you have the money to continue, or may quit anytime. Before the game, you have access to a genie that will answer any one yes/no question about the coin flip game. The genie knows the results of all the coming flips. Given that you start the game with $N, find a strategy that maximizes your winnings.
Earlier I had posed the problem stating that the genie knew the future, but that can cause weird possible questions involving not having a well posed question. Anyway, the intention is that the genie be capable of answering your question solely knowing what the coin flips are going to be. If a genie who knows the outcome of random events bothers you, we can instead suppose all the flips have been determined ahead of time and the genie simply has access to all the results.
Clearly with no genie, the only thing you can do will have an expected final outcome average of $N, since the game is fair for all strategies, so the question is to find out how much the one bit of information the genie gives you is worth. One thing I found interesting about this problem is that you can also prove optimality of the correct answer.
Yep, Counterfeit Masses
So, its time for the solution to the final counterfeit masses problem. First, its worth nothing that the statement in the problem that you must determine if the counterfeit coin is heavy or light is irrelevant. Every coin in the collection must at some point step on the scale (as the counterfeit might not even be present at all), and since by the end you will know which coin was counterfeit and it was on the scale at some point, you know if it is heavy or light. Next, note that the "possible existence" of the counterfeit coin is essentially meaningless, as you can treat a problem with N coins and a guaranteed counterfeit equivalent to a problem with N-1 coins with a possible counterfeit by throwing one coin out the window. All that crap is really just to make the problem sound harder.
So we really only need to worry about having 41 coins with a guaranteed counterfeit and a 1 coin reserve and 4 weighings at our disposal. You will recall that with 4 weighings and an infinite reserve we could only do 41 coins at best, so apparently a 1 coin reserve is as strong as an infinite one.
One trick that makes this problem easy is just to always proceed as if it actually has a solution. We know that we will begin by weighing N coins against N-1 other coins plus the reserve coin (we might as well use the thing), and leave the other 41-(2N-1) coins to the side. But, if the N vs. N measurement comes out equal, we will have a "large" reserve and have to solve the problem with 42-2N coins with only 3 measurements. We know that at most then, 42-2N can be equal to 14, so N=14 (or more, but why make our lives harder). So, we have step one:
If this comes out balanced, we know what to do. So, lets assume the 14 come out heavy (if they are light, just switch the notion of light and heavy), so we have 14 possibly heavy coins and 13 possibly light coins. Now, we have a reserve of 15 coins (the exact size is meaningless actually, we only need about 10 of them as we will see), and we will set aside M of our "heavy" coins and perform some measurement on the others. If that measurement comes out balanced, we will have 2 measurements left and M heavy coins, so we know that we should set M=9 at most, or we can't win if the next measurement is balanced. So, lets do that:
If this comes out balanced, we can solve the remaining problem easily. If the 5 heavy and 9 light come out light, it must be the 9 light causing it (no heavy coins on the other side). If the 5 heavy and 9 light come out heavy, we now have 5 possibly heavy coins and 4 possibly light coins with a large reserve and 2 measurements left. Set 3 heavy aside (as if the next measurement is balanced, we can solve them with our 1 remaining measurement), and
If this is balanced, we know what to do. If the 3 light and 2 heavy come out light, then the 3 light caused it (no heavy on the other side). If the 3 light and 2 heavy come out heavy then we are down to 2 heavy and 1 light with one measurement left. This is easy enough:
The cases of "balanced", "heavy", and "light" each now point to a unique coin.
It is easy to use this method to solve the (3N+1)/2 coin case with N measurements and 1 reserve coin. So it is true that any nonzero reserve handed to you at the start is of equal strength. The technique of solving the problem by assuming the solution exists can actually get you pretty far in logic puzzles, in a few cases you can actually find a solution to a problem and not be able to prove that there actually is a solution. It works for logic puzzles because there typically is a solution, but I suppose mathematical research demands a bit of a higher level of rigor.
So we really only need to worry about having 41 coins with a guaranteed counterfeit and a 1 coin reserve and 4 weighings at our disposal. You will recall that with 4 weighings and an infinite reserve we could only do 41 coins at best, so apparently a 1 coin reserve is as strong as an infinite one.
One trick that makes this problem easy is just to always proceed as if it actually has a solution. We know that we will begin by weighing N coins against N-1 other coins plus the reserve coin (we might as well use the thing), and leave the other 41-(2N-1) coins to the side. But, if the N vs. N measurement comes out equal, we will have a "large" reserve and have to solve the problem with 42-2N coins with only 3 measurements. We know that at most then, 42-2N can be equal to 14, so N=14 (or more, but why make our lives harder). So, we have step one:
1. Weigh 14 coins against 13 coins plus the reserve coin.
If this comes out balanced, we know what to do. So, lets assume the 14 come out heavy (if they are light, just switch the notion of light and heavy), so we have 14 possibly heavy coins and 13 possibly light coins. Now, we have a reserve of 15 coins (the exact size is meaningless actually, we only need about 10 of them as we will see), and we will set aside M of our "heavy" coins and perform some measurement on the others. If that measurement comes out balanced, we will have 2 measurements left and M heavy coins, so we know that we should set M=9 at most, or we can't win if the next measurement is balanced. So, lets do that:
2. Weigh the 5 of the possibly heavy coins with 9 possibly light against the other 4 possibly light and 10 reserve, the other 9 possibly heavy coins are set aside.
If this comes out balanced, we can solve the remaining problem easily. If the 5 heavy and 9 light come out light, it must be the 9 light causing it (no heavy coins on the other side). If the 5 heavy and 9 light come out heavy, we now have 5 possibly heavy coins and 4 possibly light coins with a large reserve and 2 measurements left. Set 3 heavy aside (as if the next measurement is balanced, we can solve them with our 1 remaining measurement), and
3. Weigh 3 possibly light coins with 2 possibly heavy coins against 1 possibly light coin and 4 reserve coins, the other 3 possibly heavy coins are set aside.
If this is balanced, we know what to do. If the 3 light and 2 heavy come out light, then the 3 light caused it (no heavy on the other side). If the 3 light and 2 heavy come out heavy then we are down to 2 heavy and 1 light with one measurement left. This is easy enough:
4. Weigh one possibly light and one possibly heavy against 2 reserve coins, with the other possibly heavy coin set aside.
The cases of "balanced", "heavy", and "light" each now point to a unique coin.
It is easy to use this method to solve the (3N+1)/2 coin case with N measurements and 1 reserve coin. So it is true that any nonzero reserve handed to you at the start is of equal strength. The technique of solving the problem by assuming the solution exists can actually get you pretty far in logic puzzles, in a few cases you can actually find a solution to a problem and not be able to prove that there actually is a solution. It works for logic puzzles because there typically is a solution, but I suppose mathematical research demands a bit of a higher level of rigor.
Probably Counterfeit Masses
So, time for the final counterfeit masses problem. Usually I say where I first heard my puzzles from but I actually made this one up myself, with Matts help:
So, its essentially the same as the more counterfeit masses problem in that you don't know if the counterfeit is heavy or light, but now you don't even know if it exists. To make up for it, you are given a single coin reserve. Apparently that is enough to cancel out not knowing if the coin exists.
You have a balance scale and 41 coins. Most of the coins are identical but there might be a counterfeit among them. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. One of the 41 coins is set aside, that coin is promised not to be counterfeit. You may use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify which coin (if any) is the counterfeit coin and if it is heavy or light.
So, its essentially the same as the more counterfeit masses problem in that you don't know if the counterfeit is heavy or light, but now you don't even know if it exists. To make up for it, you are given a single coin reserve. Apparently that is enough to cancel out not knowing if the coin exists.
Probably Too Hard
Alright, well the solution to the second counterfeit coin puzzle actually isn't too hard, I've just run out of clever titles.
Anyway, its a pretty neat solution:
If they come out equal, then you have 3 weightings left, 14 unknown coins and a reserve of 26 coins you know are not counterfeit. That will be easy to solve:
If the 9 come out heavy (light), then you have two measuerments left and you know the coin is in those 9 and heavy (light), so we have already solved this problem. If the 9 come out even then we have a reserve of 35 coins and 5 unknown with 2 measurements left.
Again, if the 3 are heavy (light), then you have one measuerment left and you know the coin is in those 3 and heavy (light), again we have already solved this problem. Finally if they are equal then we have 1 measurement left and a reserve of 38 coins with 2 unknown coins. At this point the solution is trivial.
From the solution we have so far, it is easy to see the power of a large reserve of coins that are promised not to be counterfeit. Given an infinite reserve and N measurements, it is easy to construct a solution that works for (3N+1)/2 unknown coins (the sum of the first N-1 powers of 3, plus 1). By contrast, when you are told that the coin is heavy, you get 3N, so not knowing the relative weight of the coin approximately doubles how many coins you can solve for. This kind of makes sense, as you sort of eliminate half the hypothetical possibilites for the counterfeit coin.
Anyway, back to step one, suppose one side came out heavier, now you have a reserve of 14 coins and 13 "possibly heavy" coins and 13 "possibly light" coins:
You have left behind 9 of the possibly heavy coins and have 2 measurements left. If measurement 2b comes out equal, then you know it is in those 9 and heavy, easy to solve. If the side with the 9 light coins comes out light, then only those 9 can be to blame (there were no possibly heavy coins on the other side) and so you know it is in those 9 and light.
In the last case to solve the side with the 9 light coins came out heavy, in that case it could have either been due to the 4 possibly heavy coins of the 4 possibly light coins. We have 2 measurements left and a reserve of 32 coins. Now our reserve is large enough that we can do a more brute force soltuion:
If the coins come out heavy, we know it is in the 3 and heavy. If they come out light, we know it is in the 3 and light. We have one measurement left, so both these cases are easy. Finally if they come out even we only have 2 unknown coins left and a large reserve. We don't even need to make use of the fact that we know the coin is "either heavy and this one or light and that one".
Technically, this completes the solution. However, out of a matter of elegance it is worth pointing out that you do not need to make use of the "large reserve" when you do step 3b. You could also put 3 light with 1 heavy agaianst 1 light and 3 reserve and treat it like measurement 2b. This construction works in general, to weigh 3N light and (3N-1)/2 heavy against (3N-1)/2 light and 3N reserve. This happens because the sum of the first N-1 powers of 3 is (3N-1)/2.
In general, this solution will solve (3N-1)/2 unknown coins with N measurements. That is only 1 worse than the solution when you have an infinite reserve, so apparently a reserve isn't as powerful as I had stated earlier. Really having a reserve just makes the solution easier to access.
Alright, next time I will post the hardest version of this puzzle that I know (though truthfully it won't be that hard, now that you have seen this solution).
Anyway, its a pretty neat solution:
1. Weigh 13 coins against 13 coins.
If they come out equal, then you have 3 weightings left, 14 unknown coins and a reserve of 26 coins you know are not counterfeit. That will be easy to solve:
2a. Weigh 9 unknown coins against 9 in the reserve.
If the 9 come out heavy (light), then you have two measuerments left and you know the coin is in those 9 and heavy (light), so we have already solved this problem. If the 9 come out even then we have a reserve of 35 coins and 5 unknown with 2 measurements left.
3a. Weigh 3 unknown against 3 from the reserve.
Again, if the 3 are heavy (light), then you have one measuerment left and you know the coin is in those 3 and heavy (light), again we have already solved this problem. Finally if they are equal then we have 1 measurement left and a reserve of 38 coins with 2 unknown coins. At this point the solution is trivial.
From the solution we have so far, it is easy to see the power of a large reserve of coins that are promised not to be counterfeit. Given an infinite reserve and N measurements, it is easy to construct a solution that works for (3N+1)/2 unknown coins (the sum of the first N-1 powers of 3, plus 1). By contrast, when you are told that the coin is heavy, you get 3N, so not knowing the relative weight of the coin approximately doubles how many coins you can solve for. This kind of makes sense, as you sort of eliminate half the hypothetical possibilites for the counterfeit coin.
Anyway, back to step one, suppose one side came out heavier, now you have a reserve of 14 coins and 13 "possibly heavy" coins and 13 "possibly light" coins:
2b. Weigh 9 of the possibly light coins with 4 of the possibly heavy coins against 4 of the possibly light coins with 9 of the reserve coins.
You have left behind 9 of the possibly heavy coins and have 2 measurements left. If measurement 2b comes out equal, then you know it is in those 9 and heavy, easy to solve. If the side with the 9 light coins comes out light, then only those 9 can be to blame (there were no possibly heavy coins on the other side) and so you know it is in those 9 and light.
In the last case to solve the side with the 9 light coins came out heavy, in that case it could have either been due to the 4 possibly heavy coins of the 4 possibly light coins. We have 2 measurements left and a reserve of 32 coins. Now our reserve is large enough that we can do a more brute force soltuion:
3b. Weigh 3 of the possibly heavy coins with 3 of the possibly light coins against 6 reserve coins.
If the coins come out heavy, we know it is in the 3 and heavy. If they come out light, we know it is in the 3 and light. We have one measurement left, so both these cases are easy. Finally if they come out even we only have 2 unknown coins left and a large reserve. We don't even need to make use of the fact that we know the coin is "either heavy and this one or light and that one".
Technically, this completes the solution. However, out of a matter of elegance it is worth pointing out that you do not need to make use of the "large reserve" when you do step 3b. You could also put 3 light with 1 heavy agaianst 1 light and 3 reserve and treat it like measurement 2b. This construction works in general, to weigh 3N light and (3N-1)/2 heavy against (3N-1)/2 light and 3N reserve. This happens because the sum of the first N-1 powers of 3 is (3N-1)/2.
In general, this solution will solve (3N-1)/2 unknown coins with N measurements. That is only 1 worse than the solution when you have an infinite reserve, so apparently a reserve isn't as powerful as I had stated earlier. Really having a reserve just makes the solution easier to access.
Alright, next time I will post the hardest version of this puzzle that I know (though truthfully it won't be that hard, now that you have seen this solution).
More Counterfeit Masses
Alright, as promised, I should post the harder version of the counterfeit masses problem now. I first learned this problem from Jen:
The main difference here is that you do not know if the counterfeit coin is heavier or lighter, so when you make a measurement you only learn that the counterfeit coin is either "on the left and heavier" or "on the right and lighter", or things like that.
Of course, the rules for the balance scale are the same as for the original problem.
You have a balance scale and 40 coins. 39 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. You may only use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.
The main difference here is that you do not know if the counterfeit coin is heavier or lighter, so when you make a measurement you only learn that the counterfeit coin is either "on the left and heavier" or "on the right and lighter", or things like that.
Of course, the rules for the balance scale are the same as for the original problem.
Probably Too Easy
Alright, I was going to post this earlier because the solution to the counterfeit masses problem is really easy, but then my weekend got really occupied.
So, the solution is as follows:
Its really a simple trinary search, this problem will only trip people up if they try to do a binary search not realizing that you always gain information about the coins you don't weigh.
Its also easy to see (and prove by induction) that with N measurements you can solve the problem with 3N coins. Also this solution is optimal, you cannot do more than 3N coins with only N measurements (also provable by induction).
I'll post the more difficult problem later today.
So, the solution is as follows:
Split the 27 coins into 3 piles of 9. Weigh two of the piles against eachother, whichever is heavier has the counterfeit coin and if neither is heavier the coin is in the third pile. Next, split the 9 into 3 groups of 3, and weigh two of those against eachother to find which pile of 3 has the counterfeit coin. Finally weigh two of the coins in the final pile of 3 against eachother to find the coin.
Its really a simple trinary search, this problem will only trip people up if they try to do a binary search not realizing that you always gain information about the coins you don't weigh.
Its also easy to see (and prove by induction) that with N measurements you can solve the problem with 3N coins. Also this solution is optimal, you cannot do more than 3N coins with only N measurements (also provable by induction).
I'll post the more difficult problem later today.
Counterfeit Masses
So, a recent discussion with Simon caused me to remember an old puzzle I've been meaning to post for some time. There are multiple versions of this puzzle though, so I'm going to start off with the easiest one and move up. I don't know where I first learned this puzzle, I've known it since childhood:
Of course, the amount by which the counterfeit coin is heavier is imperceptible to a human, only a balance scale can tell. Using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it. The button will work 3 times and then the scale will break.
You have a balance scale and 27 coins. 26 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it is slightly heavier than other coins. You may only use the balance scale to make 3 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.
Of course, the amount by which the counterfeit coin is heavier is imperceptible to a human, only a balance scale can tell. Using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it. The button will work 3 times and then the scale will break.
Subscribe to:
Posts (Atom)
