All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 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: 5.0000 (2 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.

 Subject Author Date Small typo in the official solution Steve Herman 2015-11-28 08:57:31 re(2): Triangular numbers and Pascal's Triangle (spoiler) broll 2015-11-27 21:42:19 re: Triangular numbers and Pascal's Triangle (spoiler) Jer 2015-11-26 22:26:07 Triangular numbers and Pascal's Triangle (spoiler) Steve Herman 2015-11-26 09:14:27 re: Well, I was wrong! Steve Herman 2015-11-21 09:26:18 Well, I was wrong! broll 2015-11-20 20:16:56 re: I think I got it. Steve Herman 2015-11-20 16:51:16 I think I got it. Jer 2015-11-20 15:32:57 Possible improvement Jer 2015-11-20 14:12:58 Possible approach. broll 2015-11-20 03:06:03

 Search: Search body:
Forums (0)