Let us proceed by a greedy approach, where we try to come up with weights such that the widest range of weight values are covered with each new weight, because why not? Besides, "higher" optimization techniques like dynamic programming are motivated by the failure of the greedy approach anyway.
What if you had a 2 gram weight: Then, with a 1 gram weight, you can measure:
- 2 grams: self-explanatory
- 3 grams: put both weights on one pan
- 4 grams: impossible
What if you had a 3 gram weight? Then, with a 1 gram weight, you can measure:
- 2 grams: put the 3 gram weight on one pan, and the 1 gram weight on the other pan
- 3 grams: self-explanatory
- 4 grams: put both the 3 gram weight and the 1 gram weight on one pan
- 2 grams: Impossible
- 3 grams: put the 4 gram weight one pan, and the 1 gram weight on the other pan
- 4 grams: self-explanatory
- 5 grams: put the 1 and 4 gram weights on the same pan
At this point, maybe we should keep the 3 gram weight. Let us select another.
What if you had a 5 gram weight? Then,
- 5 grams: self-explanatory
- 6 grams: 5 and 1 gram on the same pan
- 7 grams: 5 and 3 grams on one pan, 1 gram on the other
- 8 grams: 5 and 3 grams on the same pan
- 9 grams: 5, 3, and 1 gram on the same pan
- 10 grams onward: impossible
- 5 grams: 1 gram on one pan, 6 gram on the other
- 6 grams: Billie Eilish (duh)
- 7 grams: 6 and 1 gram on the same pan
- 8 grams: 6 and 3 grams on one pan, 1 gram on the other
- 9 grams: 6 and 3 grams on the same pan
- 10 grams: 6, 3, and 1 grams on the same pan
- 11 grams: impossible
Skipping a few, what if you had a 9 gram weight? Then,
- 5 grams: Put the 9 gram on one pan, and the 1 and 3 grams on the other pan
- 6 grams: Put the 9 gram on one pan, and the 3 gram on the other
- 7 grams: Put the 9 and 1 gram on one pan, and the 3 gram on the other
- 8 grams: Put the 9 gram on one pan, and the 1 gram on the other
- 9 grams: Duh
- 10 grams: 9 + 1 on the same pan
- 11 grams: 9 and 3 on one pan, 1 on the other
- 12 grams: 9 and 3 on one pan
- 13 grams: 9, 3, and 1 grams on the same pan
- 5 grams: Impossible
At this point, we should keep the 9 gram weight. I think we see a pattern here: as we seek the next weight to add, keep adding the candidate weight by 1 until the "minimum" becomes untenable in a sense. For example, we abandoned the 4 because there was no way to make 2, settling at 3; we abandoned the 10 because there was no way to make 5, settling at 9.
I am going to conjecture that the next weight to add is 27 grams:
- 14 grams: Put 27 on one pan, and 9, 3, and 1 grams on the other pan
- 15 grams: 27 on one pan, and 9 and 3 on the other
- 16 grams: 27 and 1 on one pan, 9 and 3 on the other
- 17 grams: 27 on one, 9 and 1 on the other
- 18 grams: 27 on one, 9 on the other
- 19 grams: 27 and 1 on one, 9 on the other
- 20 grams: 27 and 3 on one, 9 and 1 on the other
- ...
- 29 grams: 27 and 3 on one, 1 on the other
- 30 grams: 27 and 3 on one
- 31 grams: 27, 3, and 1 on one
- 32 grams: 27 and 9 on one, 3 and 1 on the other
- 33 grams: 27 and 9 on one, 3 on the other
- 34 grams: 27, 9, and 1 on one, 3 on the other
- 35 grams: 27 and 9 on one, 1 on the other
- 36 grams: 27 and 9 on one
- 37 grams: 27, 9, and 1 on one
- 38 grams: 27, 9, and 3 on one, 1 on the other
- 39 grams: 27, 9, and 3 on one
- 40 grams: 27, 9, 3, and 1 on one
- 14 grams: Impossible
I do not think that any other solutions are possible; either you will have some weights that you cannot make, or you will end up needing more than 4. Thus, this is in fact optimal.
I suppose you can extend the puzzle and help them develop a more precise understanding by making the weight bigger, asking more questions, et cetera:
- Suppose that you need to be able to measure up to 121 grams now.
- If you have a 41 gram weight...
- How far can you measure up to?
- How many more weights would you need to go up to 121?
- Repeat the questions for a 43 gram weight, 75 gram weight.
- What is the minimum number of weights needed to be able to measure up to 121? How much should each weight weigh?
No comments:
Post a Comment