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?

I decided to enumerate the optimal total number of pill exposures rather than the average.

The situation described in January I'll call the one container solution.  For x pills it yields T(x)=x(x+1)/2 exposures (the triangle numbers).

I'll call f(x) the solution for two bottles where all the pills start in one bottle.

g(x) is the solution for pills starting in two separate bottles.  (Where there may be an optimal number of pills (a,b) in each bottle where x=a+b.)

Note that for a given x=a+b, g(x)=f(a)+T(b)
Because while one bottle is occupied, the best we can do is take all the pills from one [T(b)] but once it is exhausted we have a fresh two bottle situation [f(a)].

Also f(x+1)=g(x)+x+1 because you can open the bottle containing all the pills, take one, and rearrange the rest into two bottles.

What is sought in the problem is f(31)=g(30)+31

To find this I worked my way up from n=1
But the ultimate solution for g(30)=122 is a=23, b=7

Explanation:
Day 1 take a pill and split the remainder into (23,7)
Exposures = 31
Days 2 through 8 take a pill a day from the second container
Exposures = 28
Day 9 take a pill and split the remainder into (16,6)
Exposures = 23
Days 10 through 15 take a pill a day from the second container
Exposures = 21
Day 16 take a pill and split the remainder into (10,5)
Exposures = 16
Days 17 through 21 take a pill a day from the second container
Exposures = 15
Day 22 take a pill and split the remainder into (6,3)
Exposures = 10
Days 23 through 25 take a pill a day from the second container
Exposures = 6
Day 26 take a pill and split the remainder into (3,2)
Exposures = 6
Days 27 through 28 take a pill a day from the second container
Exposures = 3
Day 29 take a pill and split the remainder into (1,1)
Exposures = 3
Day 30 take the pill in the second container
Exposures = 1
Day 31 take the pill from the first container
Exposures = 1

Sum of exposures=164

Notes: There are actually two splits that optimize most values of x.  For example when x=31 the split on day 1 could have been (24,6).
In solving this I made a table on paper.  There is a definite structure to f(x) and g(x) that could lead to recursive and explicit formulas but I haven't set out to find them.  They are not quite polynomials and likely involve floor functions.

Posted by Jer on 2015-11-20 15:32:57