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

Home > Algorithms
Optimizing Potency (Posted on 2015-11-19) Difficulty: 4 of 5
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.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Small typo in the official solutionSteve Herman2015-11-28 08:57:31
re(2): Triangular numbers and Pascal's Triangle (spoiler)broll2015-11-27 21:42:19
re: Triangular numbers and Pascal's Triangle (spoiler)Jer2015-11-26 22:26:07
Triangular numbers and Pascal's Triangle (spoiler)Steve Herman2015-11-26 09:14:27
re: Well, I was wrong!Steve Herman2015-11-21 09:26:18
Well, I was wrong!broll2015-11-20 20:16:56
re: I think I got it.Steve Herman2015-11-20 16:51:16
SolutionI think I got it.Jer2015-11-20 15:32:57
Possible improvementJer2015-11-20 14:12:58
Possible approach.broll2015-11-20 03:06:03
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information