Suppose you have a very accurate balance scale. I give you 12 coins, identical in appearance and weight, except that one of them is slightly heavier or slightly lighter than the rest. How can you determine which coin is different from teh rest in just three weighings?
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
Twelve Coins
- Thread starter mjtnas
- Start date
JuicyBurger
Junior Member
- Joined
- Jan 26, 2010
- Messages
- 96
Well, you could put half of the coins on each side of the scale to determine which 6 the coin was with. Then split those up and weigh 3 coins vs 3 coins.
Now you've done two weighings and have 3 coins left... So weigh two of the coins (one against the other). If it is one of the two you will find it, if they are equal than it is the third, un-weighed coin.
You would need to know whether or not the coin was lighter or heavier, however, this would not work if the coin could be either.
Now you've done two weighings and have 3 coins left... So weigh two of the coins (one against the other). If it is one of the two you will find it, if they are equal than it is the third, un-weighed coin.
You would need to know whether or not the coin was lighter or heavier, however, this would not work if the coin could be either.
Suppose you have a very accurate balance scale. I give you 12 coins, identical in appearance and weight, except that one of them is slightly heavier or slightly lighter than the rest. How can you determine which coin is different from the rest in just three weighings?
This problem can be generalized in order to handle any number of items. If it is known whether the item is heavier or lighter at the outset, the odd item can be determined amongst 3^n items in n weighings. Thus, a problem involving 3 to the n power items can be solved in n weighings:
1. Place 3^(n - 1) items on each side of the balance scale, which will immediately tell you which group of 3^(n - 1) items contains the odd item.
2. Knowing which group of 3^(n - 1) items contains the odd item, divide that group into three equal groups of 3^(n - 2) items each. Place one of each of these groups on each side of the balance scale, which immediately tells you which of the three new groups contains the odd item.
3. The continuation of reducing the size of the groups by two-thirds at each successive weighing will ultimately leave you with the knowledge of the one odd item.
For example, in how many weighings on a simple balance scale can you determine which of 243 coins is heavier than the other coins? This process would also work with 729, 2187, 6561, and so on.
1. 243 = 3 to the fifth power, so five weighings will tell which is the odd coin.
2. Since 3^4 = 81, place 81 coins on each side of the scale, leaving 81 on the table.
3. If these balance, the third pile contains the heavy coin, and if they do not balance, the side of the scale that went down contains the group with the heavy coin in it.
4. Taking the known group with the heavy coin in it, divide it into three groups of 27 coins each, since 3^3 = 27. Place one group on each side of the scale.
5. Following the same logic of step 3, remove the group with the heavy coin in it and put the others aside.
6. Since 3^2 = 9, divide the group with the heavy coin in it up into three groups of 9 coins and place one group on each side of the scale.
7. Following the logic of step 3 again, remove the group with the heavy coin in it and put the others aside.
8. Divide this group up into three groups of 3 coins, since 3 ^ 1 = 3, and place one group on each side of the scale.
9. Following the logic of step 3 again, remove the group with the heavy coin and place the others aside.
10. Because 3^0 = 1, divide this group into three sets of 1 and place one on each side of the scale.
11. Which coin is heavier is now apparent.
Now consider 12 items. In this case, it is not known whether the odd item is lighter or heavier than the others are. The number of weighings required to solve a problem of this type can be derived from the following:
If the number of items, N, is equal to or less than (3^n - 3) / 2, where n is the number of weighings, it is always possible to determine the counterfeit item in n weighings and simultaneously determine whether it is lighter or heavier. If N exceeds (3^n - 3) / 2, then n + 1 weighings will be required. Turning this expression around, if you have N items, then 3^n = 2 N + 3, from which you can solve for n using logarithms.
For this problem, if you estimated that it would take 2 weighings, then you would have N = (3^2) - 3 / 2 = 3 and since your number of 12 items exceeds 6, you require more weighings. Trying three weighings, N = (3 ^ 3 - 3) / 2 = 12. Since this is equal to or less than your number of items, three weighings will do the trick.
The specific procedure is as follows:
1--Place 4 of the cubes on each side of the scale. We then have 3 possibilities.
A--They balance--indicating the odd cube is among the remaining 4 cubes still on the table.
B--The left side goes down--indicating the heavier cube is on the left scale or the lighter cube is on the right scale.
C--The right side goes down--indicating the heavier cube is on the right scale or the lighter cube is on the left scale.
2--In case A--replace 3 cubes on the right scale with 3 of the cubes from the table. We again have 3 possibilities.
D--The scales remain balanced--indicating the odd cube is the cube still on the table and balancing it against any of the other 11 cubes will tell you whether it is heavier or lighter on the 3rd weighing.
E--The right side goes down--indicating the heavier cube is among the 3 cubes just placed on the right scale and weighing any 2 of these 3 cubes against each other will tell you which of the 3 is the heavier.
F--The right side goes up--indicating the lighter cube is among the 3 cubes just placed on the right scale and, similarly to E above, weighing any 2 of these 3 cubes against each other will tell you which one of the 3 is the lighter.
3--In case B--remove 3 cubes from the left scale and place them on the table. Move 3 cubes from the right scale to the left scale. Place 3 cubes from the 4 originally left on the table onto the right scale. We again have 3 possibilities.
G--They remain the same (left side down)--indicating the heavier cube is still on the left scale or the lighter cube is still on the right scale. Take either one of the 2 cubes left on the scales in the second weighing and balance it against any one of the other 10 cubes. Calling them X from the down scale and Y from the up scale; if X balances with another cube then Y is the lighter cube. If the X scale goes down when balanced with another cube, it is the heavier cube. Similarly with the Y cube; if Y balances with another cube then X is the heavier cube. If the Y scale goes up when balanced with another cube, it is the lighter cube.
H--They now balance--indicating the heavier cube must be among the 3 cubes just removed from the left scale and placed on the table. Balance any 2 of these 3 against each other. If they balance, the 3rd is the heavier cube. If one scale goes down, you have the heavier cube.
J--The right scale goes down--indicating the lighter cube is among the 3 cubes just moved from the right scale to the left scale. Balance any 2 of these 3 cubes against each other. If they balance, the 3rd is the lighter cube. If one scale goes up, you have the lighter cube.
4--In case C--using the same process as used in case B (only reversed), you can achieve the same results.
I hope the explanations were not too confusing.
This problem can be generalized in order to handle any number of items. If it is known whether the item is heavier or lighter at the outset, the odd item can be determined amongst 3^n items in n weighings. Thus, a problem involving 3 to the n power items can be solved in n weighings:
1. Place 3^(n - 1) items on each side of the balance scale, which will immediately tell you which group of 3^(n - 1) items contains the odd item.
2. Knowing which group of 3^(n - 1) items contains the odd item, divide that group into three equal groups of 3^(n - 2) items each. Place one of each of these groups on each side of the balance scale, which immediately tells you which of the three new groups contains the odd item.
3. The continuation of reducing the size of the groups by two-thirds at each successive weighing will ultimately leave you with the knowledge of the one odd item.
For example, in how many weighings on a simple balance scale can you determine which of 243 coins is heavier than the other coins? This process would also work with 729, 2187, 6561, and so on.
1. 243 = 3 to the fifth power, so five weighings will tell which is the odd coin.
2. Since 3^4 = 81, place 81 coins on each side of the scale, leaving 81 on the table.
3. If these balance, the third pile contains the heavy coin, and if they do not balance, the side of the scale that went down contains the group with the heavy coin in it.
4. Taking the known group with the heavy coin in it, divide it into three groups of 27 coins each, since 3^3 = 27. Place one group on each side of the scale.
5. Following the same logic of step 3, remove the group with the heavy coin in it and put the others aside.
6. Since 3^2 = 9, divide the group with the heavy coin in it up into three groups of 9 coins and place one group on each side of the scale.
7. Following the logic of step 3 again, remove the group with the heavy coin in it and put the others aside.
8. Divide this group up into three groups of 3 coins, since 3 ^ 1 = 3, and place one group on each side of the scale.
9. Following the logic of step 3 again, remove the group with the heavy coin and place the others aside.
10. Because 3^0 = 1, divide this group into three sets of 1 and place one on each side of the scale.
11. Which coin is heavier is now apparent.
Now consider 12 items. In this case, it is not known whether the odd item is lighter or heavier than the others are. The number of weighings required to solve a problem of this type can be derived from the following:
If the number of items, N, is equal to or less than (3^n - 3) / 2, where n is the number of weighings, it is always possible to determine the counterfeit item in n weighings and simultaneously determine whether it is lighter or heavier. If N exceeds (3^n - 3) / 2, then n + 1 weighings will be required. Turning this expression around, if you have N items, then 3^n = 2 N + 3, from which you can solve for n using logarithms.
For this problem, if you estimated that it would take 2 weighings, then you would have N = (3^2) - 3 / 2 = 3 and since your number of 12 items exceeds 6, you require more weighings. Trying three weighings, N = (3 ^ 3 - 3) / 2 = 12. Since this is equal to or less than your number of items, three weighings will do the trick.
The specific procedure is as follows:
1--Place 4 of the cubes on each side of the scale. We then have 3 possibilities.
A--They balance--indicating the odd cube is among the remaining 4 cubes still on the table.
B--The left side goes down--indicating the heavier cube is on the left scale or the lighter cube is on the right scale.
C--The right side goes down--indicating the heavier cube is on the right scale or the lighter cube is on the left scale.
2--In case A--replace 3 cubes on the right scale with 3 of the cubes from the table. We again have 3 possibilities.
D--The scales remain balanced--indicating the odd cube is the cube still on the table and balancing it against any of the other 11 cubes will tell you whether it is heavier or lighter on the 3rd weighing.
E--The right side goes down--indicating the heavier cube is among the 3 cubes just placed on the right scale and weighing any 2 of these 3 cubes against each other will tell you which of the 3 is the heavier.
F--The right side goes up--indicating the lighter cube is among the 3 cubes just placed on the right scale and, similarly to E above, weighing any 2 of these 3 cubes against each other will tell you which one of the 3 is the lighter.
3--In case B--remove 3 cubes from the left scale and place them on the table. Move 3 cubes from the right scale to the left scale. Place 3 cubes from the 4 originally left on the table onto the right scale. We again have 3 possibilities.
G--They remain the same (left side down)--indicating the heavier cube is still on the left scale or the lighter cube is still on the right scale. Take either one of the 2 cubes left on the scales in the second weighing and balance it against any one of the other 10 cubes. Calling them X from the down scale and Y from the up scale; if X balances with another cube then Y is the lighter cube. If the X scale goes down when balanced with another cube, it is the heavier cube. Similarly with the Y cube; if Y balances with another cube then X is the heavier cube. If the Y scale goes up when balanced with another cube, it is the lighter cube.
H--They now balance--indicating the heavier cube must be among the 3 cubes just removed from the left scale and placed on the table. Balance any 2 of these 3 against each other. If they balance, the 3rd is the heavier cube. If one scale goes down, you have the heavier cube.
J--The right scale goes down--indicating the lighter cube is among the 3 cubes just moved from the right scale to the left scale. Balance any 2 of these 3 cubes against each other. If they balance, the 3rd is the lighter cube. If one scale goes up, you have the lighter cube.
4--In case C--using the same process as used in case B (only reversed), you can achieve the same results.
I hope the explanations were not too confusing.
Nope, quite clear Will: already got everything memorized :roll:TchrWill said:I hope the explanations were not too confusing.