A New Question about Old Coins
I want to come back to a middle-school Olympiad problem I posted a while ago.
Streamline School Olympiad 2000 (8th grade). You have six bags of coins that look the same. Each bag has an infinite number of coins and all the coins in the same bag weigh the same amount. Each different bag contains coins of a different weight, ranging from 1 to 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times you need to weigh the coins in order to confirm that the labels are correct?
The answer is unpretentious: one weighing is enough. We can take one 5-gram coin, two 4-gram coins, three 3-gram coins, four 2-gram coins and five 1-gram coins for the total of 35 grams. This number is not divisible by 6, so we can add one more 1-gram coin and weigh all of them against six 6-gram coins. I leave it to the reader to show that this solution works and to extrapolate the solution for any number of bags.
My new challenge is to find a weighing for the above problem using the smallest number of coins. What is the number of coins in such a weighing for a given number of bags?
I manually calculated this number for a small number of bags, but I would like to get a confirmation from my readers. Starting from 6 bags, I don’t know the answer. Can you help me?
Share:
David Reynolds:
First, I present my representation.
Each bag and the number of coins from it are represented by AxB, where A is the Amount of coins, and B is the Bag they came from.
These are summed together in an equality, whose left and right sides represent the left and right sides of the balance scale.
Tanya’s solution for six bags is represented as
1×5+2×4+3×3+4×2+6×1=6×6 (22 coins)
I love the elegance of Tanya’s solution. Logic tells us that any swapping of bags must force an imbalance of the scale.
I argue, though, that if we verify the labels on five bags, the sixth bag must be correct by elimination.
Therefore, one might think that the following equation is sufficient.
0x6+1×4+2×3+3×2+4×1=4×5 (14 coins)
Watch what happens if we switch labels on bags 2 and 4, and also on bags 5 and 6.
0x5+1×2+2×3+3×4+4×1=4×6
The scales still balance, though the bags are not labelled correctly.
In other words
0x?+1x?+2x?+3x?+4x?=4x?
has more than one solution and is therefore INVALID.
To verify a solution as valid, the remaining n!-1 permutations of the bag labels must be tested to be sure that no other arrangement balances.
Better solutions do exist. And this is where a computer comes in handy.
My best six bag solution is
0x4+2×3+3×2+5×1=1×5+2×6 (13 coins)
Here are my search results. Primary criteria is fewest coins. Secondary criteria is least weight.
1: 0x1
2: 2×1=1×2 coins = 3, weight = 4
3: 0x3+2×1=1×2 coins = 3, weight = 4
4: 0x3+1×2+2×1=1×4 coins = 4, weight = 8
5: 0x4+1×3+2×2+3×1=2×5 coins = 8, weight = 20
6: 0x4+2×3+3×2+5×1=1×5+2×6 coins = 13, weight = 34
7: 0x5+1×4+2×3+3×2+4×1=1×6+2×7 coins = 13, weight = 40
8: 0x6+1×5+2×4+3×3+5×2+6×1=2×7+3×8 coins = 22, weight = 76
9: 0x6+2×5+3×4+4×3+5×2+6×1=1×7+2×8+3×9 coins = 26, weight = 100
10: 0x7+1×6+2×5+3×4+4×3+5×2+6×1=1×8+2×9+3×10 coins = 27, weight = 112
11: 0x8+1×7+2×6+3×5+4×4+5×3+6×2+7×1=1×9+2×10+5×11 coins = 36, weight = 168
12: 0x8+1×7+3×6+4×5+5×4+6×3+8×2+11×1=1×9+2×10+3×11+4×12 coins = 48, weight = 220
A surprising pattern has emerged. Although all permutations have been searched, only a certain arrangement seems to lead to the best solutions.
23 April 2015, 6:56 pmDavid Reynolds:
Tanya reminded me that there was no requirement to make the scale balance. Often, it is enough to see that one side is always heavier.
For instance, with two bags, simply weigh one coin from each bag against each other. The coin from the bag labelled one should be lighter than the coin from the bag labelled two.
I represent that as:
1×1<1×2
Here are my new search results. Primary criteria is fewest coins. Secondary criteria is least weight.
1: 0x1
24 April 2015, 5:10 pm2: 1×1<1×2 coins = 2, weight = 3
3: 0x3+2×1=1×2 coins = 3, weight = 4
4: 0x3+1×2+2×1=1×4 coins = 4, weight = 8
5: 0x4+1×3+2×2+3×1=2×5 coins = 8, weight = 20
6: 0x4+2×3+3×2+4×1<1×5+2×6 coins = 12, weight = 33
7: 0x5+1×4+2×3+3×2+4×1=1×6+2×7 coins = 13, weight = 40
8: 0x6+1×5+2×4+3×3+4×2+7×1<2×7+3×8 coins = 22, weight = 75
9: 0x6+2×5+3×4+4×3+5×2+6×1=1×7+2×8+3×9 coins = 26, weight = 100
10: 0x7+1×6+2×5+3×4+4×3+5×2+6×1=1×8+2×9+3×10 coins = 27, weight = 112
11: 0x8+1×7+2×6+3×5+4×4+5×3+6×2+7×1=1×9+2×10+5×11 coins = 36, weight = 168
12: 0x8+1×7+3×6+4×5+5×4+6×3+8×2+10×1<1×9+2×10+3×11+4×12 coins = 47, weight = 219
13: 0x9+1×8+2×7+3×6+4×5+5×4+6×3+7×2+8×1=1×10+2×11+3×12+4×13 coins = 46, weight = 240
14: 0x10+1×9+2×8+3×7+4×6+5×5+6×4+7×3+9×2+10×1<1×11+3×12+4×13+5×14 coins = 60, weight = 337
15: 0x10+1×9+3×8+4×7+5×6+6×5+7×4+8×3+10×2+11×1<1×11+2×12+3×13+4×14+5×15 coins = 70, weight = 409
16: 0x11+1×10+2×9+3×8+4×7+5×6+6×5+7×4+8×3+9×2+10×1=1×12+2×13+3×14+4×15+5×16 coins = 70, weight = 440
17: 0x12+1×11+2×10+3×9+4×8+5×7+6×6+7×5+8×4+9×3+10×2+11×1=1×13+2×14+3×15+4×16+8×17 coins = 84, weight = 572
18: 0x12+1×11+3×10+4×9+5×8+6×7+7×6+8×5+9×4+10×3+11×2+13×1<1×13+2×14+3×15+4×16+5×17+6×18 coins = 98, weight = 685
19: 0x13+1×12+2×11+3×10+4×9+5×8+6×7+7×6+8×5+9×4+10×3+11×2+12×1=1×14+2×15+3×16+4×17+5×18+6×19 coins = 99, weight = 728
20: 0x14+1×13+2×12+3×11+4×10+5×9+6×8+7×7+8×6+9×5+10×4+11×3+13×2+14×1<1×15+2×16+4×17+5×18+6×19+7×20 coins = 118, weight = 917
21: 0x15+1×14+2×13+3×12+4×11+5×10+6×9+7×8+8×7+9×6+10×5+11×4+12×3+13×2+14×1<1×16+3×17+4×18+6×19+7×20+8×21 coins = 134, weight = 1121
22: 0x15+1×14+2×13+3×12+4×11+5×10+6×9+7×8+8×7+9×6+10×5+11×4+12×3+13×2+14×1=1×16+2×17+3×18+4×19+5×20+6×21+7×22 coins = 133, weight = 1120
23: 0x16+1×15+2×14+3×13+4×12+5×11+6×10+7×9+8×8+9×7+10×6+11×5+12×4+13×3+14×2+15×1=1×17+2×18+3×19+4×20+5×21+6×22+11×23 coins = 152, weight = 1360
24: 0x17+1×16+2×15+3×14+4×13+5×12+6×11+7×10+8×9+9×8+10×7+11×6+12×5+13×4+14×3+15×2+16×1=1×18+2×19+4×20+6×21+7×22+8×23+9×24 coins = 173, weight = 1632