Home > Algorithms
| Optimizing Potency (Posted on 2015-11-19) |
 |
My pills, which I buy 31 at a time, come in an airtight canister. Last month (December), I opened the canister 31 times, removing (and swallowing) one pill every day. The problem is that the last pill I took on December 31 was exposed to the air 31 times, which diminishes its potency. The December 1 pill was only exposed to air once. On average, the pills that I took were exposed to the air 16 times, calculated as (1 + 31)/2.
But I can do better in January, because now I have an empty canister!
On January 1, I could swallow one pill and transfer 15 to the empty canister. If I make no more transfers, the remaining 30 pills will be exposed an additional 8 times on average, i.e (15+1)/2, in addition to the once that they have already been exposed. Average time exposed for all 31 pills is (1 + 30*(8+1))/31 = 271/31 = 8.742. A significant improvement from 16! I feel healthier already!
I think that I can do better if I transfer pills between my two canisters more frequently. What is the best I can do? How?
|
|
Submitted by Steve Herman
|
|
Rating: 4.6667 (3 votes)
|
|
|
Solution:
|
(Hide)
|
Well, let's give the winning algorithm first, and then a solution method.
ALGORITHM
-----------------
Clearly, using Broll's notation, a solution is to transfer some pills from the 1st container (call it R for Reserve) to the 2nd container (call it C for Current) and then take daily pills from C. If you need a pill and C is empty, then remove r pills from R, swallow 1, and place the remaining (r-1) pills in the C. The only question is if R contains R pills, what is the optimal r?
Well, let T(n) be the nth triangular number. (ie, 1,3,6,10,15,21,28, etc.). For R <= 31, and probably for any larger value of R, the winning algorithm is as follows:
If R = T(n), then r = n. In effect, form the pills into the shape of an equilateral triangle, and then remove one edge of the triangle!
If R is between T(n) and T(n-1), then remove either n or n-1. Either one will result in a minimum number of total exposures.
Jer's solution does this.
Starting with R = 31, remove 7 or 8. Jer removed 8, leaving 23 in R.
When the C is empty and R = 23, remove 6 or 7. Jer removed 7, leaving 16 in R.
When the C is empty and R = 16, remove 5 or 6. Jer removed 6, leaving 10 in R.
10 is a triangular number, so now there are no options.
When the C is empty and R = 10, remove 4, leaving 6 in R.
When the C is empty and R = 6, remove 3, leaving 3 in R.
When the C is empty and R = 3, remove 2, leaving 1 in R.
When the C is empty and R = 1, remove 1, leaving 0 in R.
Total exposures = 164. Average exposures = 164/31 = 5.258.
SOLUTION METHOD
-----------------------
Instead of focusing on the average, focus on the total number of exposures.
Both Jer and I solving this using what back in the day was referred to in my Operations Research class as "Dynamic Programming". Specifically, we approached this as a "Stagecoach Problem", solving the problem first for c= 1, then 2, then 3, all the way up to 31. This approach reduces a problem that requires exponential time to solve (as a function of R) to a problem that only requires polynomial (geometric) time.
At any rate, let f(R) = the two container minimum exposures. f(31), we both found, = 164.
Let T(c) = total exposures for a one container situation = the cth triangular number = c*(c-1)/2
At each stage, calculate the r which minimizes R + f(R-r) + T(r-1). This is easily done by looking up earlier rows in the table below which is built up one row at a time.
R T(R) f(R) r R-r
1 1 1 1 0
2 3 3 1 or 2 1 or 0
3 6 5 2 1
4 10 8 2 or 3 2 or 1
5 15 11 2 or 3 3 or 2
6 21 14 3 3
7 28 18 3 or 4 4 or 3
8 36 22 3 or 4 5 or 4
9 45 26 3 or 4 6 or 5
10 55 30 4 6
11 66 35 4 or 5 7 or 6
12 78 40 4 or 5 8 or 7
13 91 45 4 or 5 9 or 8
14 105 50 4 or 5 10 or 9
15 120 55 5 10
16 136 61 5 or 6 11 or 10
17 153 67 5 or 6 12 or 11
18 171 73 5 or 6 13 or 12
19 190 79 5 or 6 14 or 13
20 210 85 5 or 6 15 or 14
21 231 91 6 15
22 253 98 6 or 7 16 or 15
23 276 105 6 or 7 17 or 16
24 300 112 6 or 7 18 or 17
25 325 119 6 or 7 19 or 18
26 351 126 6 or 7 20 or 19
27 378 133 6 or 7 21 or 20
28 406 140 7 21
29 435 148 7 or 8 22 or 21
30 465 156 7 or 8 23 or 22
31 496 164 7 or 8 24 or 23
Having done this, the relationship of the algorithm to triangular numbers is striking and unexpected. Not, I think, a coincidence.
The sequence f(R) is OEIS A060432, but it is not a particularly illuminating lookup.
I might go and solve the 3 container problem. I am hoping it involves something like tetrahedral numbers. That would be exciting.
|
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (15)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
