Ok, time to solve out the weighing medals problem from last time.
First, its easy to see that the gold medal will never be on the scale, there is nothing to balance it against, so we might as well throw it away and if we can't find the fake in the others then the fake was the gold medal. Next, note that we can't leave all the silvers off the first weighing, because then they must all go on the second weighing (since the gold is never being weighed, we must weigh everything else at least once or we can't find the fake) and there is no way to divide up the 3 silvers into two piles. Similarly, we must put at least one bronze on the first weighing.
It makes the most sense to weigh 2 bronze and 1 silver against 2 bronze and 1 silver for our first one, this way, if one side is heavy we have immediately identified 2 bronze and 1 silver as the "suspect group". We can use our second measurement to weigh the two suspect bronze against eachother and figure our which of the three medals is the fake.
If our first measurement comes out balanced, we have the gold, 1 bronze, and 1 silver as our suspect group. We put the suspect bronze with a genuine silver on the left against the suspect silver and a genuine bronze. Now 'left heavy' 'right heavy' and 'balanced' all point to a unique medal.
This solves the problem, and as stated isn't very difficult. What I found sort of cool was if you reconsider that solution without the different types of medals. It is just the 9 coins and 2 weighings problem and you start by weighing 3 vs 3 to get a suspect group of size 3. Of course, if the solution to the different medals problem is to work for arbitrary values of masses of genuine medals mbronze, msilver, mgold, then it must work in the particular case where all those m's are equal (I suppose this isn't true if your solution divided by mbronze-msilver or something, but we aren't doing that).
Anyway, thats all I got.
Showing posts with label balance scale. Show all posts
Showing posts with label balance scale. Show all posts
Weighing Medals
Almost a new year already, apparently I didn't do quite as much blogging this year, as I usually get about 40 posts a year and this year I only have about 30. I choose to blame it on my thesis rather than on my general laziness.
Anyway, I found a new puzzle over at Tanya Khovanovas Math Blog that I thought was sort of neat:
Standard balance scale rules, of course. The balance scale can be envisioned as having two places to put stuff, and then you push a button and it will tell you either "left side heavy", "right side heavy", or "balanced". The button will only work two times and then the scale will break.
Its actually a pretty simple puzzle if you have done the other balance scale problems, it only took me a few minutes to get it, but I somehow was very satisfied with the answer.
Anyway, I found a new puzzle over at Tanya Khovanovas Math Blog that I thought was sort of neat:
There is a collection of medals and one of them is known to be fake. There is 1 gold medal, 3 silver medals, and 5 bronze medals. A fake medal weighs slightly less than the corresponding real medal. All real medals of the same type weigh the same amount, but medals of differing types might not weigh the same amount. Using a balance scale and two weighings, find a strategy that is guaranteed to identify the fake medal.
Standard balance scale rules, of course. The balance scale can be envisioned as having two places to put stuff, and then you push a button and it will tell you either "left side heavy", "right side heavy", or "balanced". The button will only work two times and then the scale will break.
Its actually a pretty simple puzzle if you have done the other balance scale problems, it only took me a few minutes to get it, but I somehow was very satisfied with the answer.
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.
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)
