Whole Tablet, Half Tablet

Posted on Thu 31 August 2017 in misc

Five Thirty Eight - Riddler Express (August 25th)¶

You take half of a vitamin every morning. The vitamins are sold in a bottle of 100 (whole) tablets, so at first you have to cut the tablets in half. Every day you randomly pull one thing from the bottle — if it’s a whole tablet, you cut it in half and put the leftover half back in the bottle. If it’s a half-tablet, you take the vitamin. You just bought a fresh bottle. How many days, on average, will it be before you pull a half-tablet out of the bottle?

Extra credit: What if the halves are less likely to come up than the full tablets? They are smaller, after all.

The problem is screaming for Markov modelling but I felt it could be solved using basic probability concepts alone and went ahead with the following approach.

Algebraic Solution¶

In [56]:

from sympy.abc import i, j, k, n, z 
from sympy import Product, factorial, Sum, oo, evalf, factor
from sympy import *
init_printing()

Average number of days before one pulls a half-tablet out is $\sum_{k=2}^{101}\;k.P(\;First\;Ever\;🚦 🚥_{k^{th} day})$

And $P(\;First\;Ever\;🚦 🚥_{i^{th} day})\;=\;P(\;💊\;_{1^{st} day})P(\;💊\;_{2^{nd} day})....P( \;💊\;_{i-1^{th} day})P(\;🚦 🚥_{i^{th} day})$

After a few simplifications, the required answer can be expressed as

In [51]:

simplify(expectedDays)

Out[51]:

$$\sum_{j=2}^{99} \frac{j}{100} \left(j - 1\right) \prod_{i=0}^{j - 2} \left(- \frac{i}{100} + 1\right)$$

This is probably the point where something cool can be done, say for example, using inequalities to get upper and lower bounds or conjuring up some distribution / arrangement that maps to these coefficients. I chose the boring method of letting the computer handle these calculations though. I was more interested in implementing a simulation for this problem and wanted the get the answer algebraically so that I can compare it with the number the simulation spits out.

In [59]:

expectedDays = Sum(Product(1-i/100, (i, 0, j-2) )*j*(j-1)/100, (j, 2, 99))
expectedDays.evalf()

Out[59]:

$$13.209960630216$$

Bonus Credit Solution¶

In case, a whole-tablet is $\lambda$ times more likely than a half-tablet to be picked

In [49]:

def modifiedExpectedDays(Lambda):
    return Sum(Product((Lambda*(100-i)/(Lambda*(100-i) + i)),
                       (i, 0, j) )*(j+1)*(j+2)/(Lambda*(100-j-1) + j+1),
                       (j, 1, 99)).evalf()

In [57]:

factor(modifiedExpectedDays(z))

Out[57]:

$$- \sum_{j=1}^{99} \frac{1}{j z - j - 99 z - 1} \left(j + 1\right) \left(j + 2\right) \prod_{i=0}^{j} \left(- \frac{i z}{- i z + i + 100 z} + \frac{100 z}{- i z + i + 100 z}\right)$$

In [58]:

modifiedExpectedDays(2) # If the whole-tablet is twice as likely to be picked

Out[58]:

$$17.7366576915744$$

How the expected number of days varies with Lambda¶

In [41]:

b = [int(modifiedExpectedDays(factor)) for factor in range(1,1000,100)]

In [63]:

import plotly.plotly as py
import plotly.graph_objs as go

data = [go.Scatter(
            x=[1,101,201,301,401,501,601,701,801,901],
            y=b,
            mode='lines+markers',
            line=dict(shape='spline')

    )]

py.iplot(data, filename='spline-interpolation')

Out[63]:

In [60]:

modifiedExpectedDays(2000000000000000)

Out[60]:

$$100.999999999998$$

Converges to 101 just as expected

Simulation Solution¶

In [3]:

import numpy as np
import plotly
import random
import sympy
from sympy import *
init_printing()
import plotly

Bottle, Day Zero¶

In [22]:

bottle = np.ones(100)

Tablet eject logic¶

In [39]:

def takeMedicine(sizeMatters=False, verbose=False):
    global bottle
    if sizeMatters:
        glottle = bottle[bottle > 0.5]
        pill = random.choice(np.concatenate((bottle,glottle)))
    else:    
        pill = random.choice(bottle)
    if pill == 1.0:
        bottle[np.argmax(bottle==1.0)] = 0.5
        if verbose:
            print("Whole Tablets {}, Half Tablets {}     💊".format(currentStatus()[0], currentStatus()[1]))
        return 1
    else:
        bottle = np.delete(bottle, np.argmax(bottle==0.5) )
        if verbose:
            print("Whole Tablets {}, Half Tablets {}     🚦 🚥".format(currentStatus()[0], currentStatus()[1]))
        return 0

Days taken to pull a half-tablet out¶

In [6]:

def daysTaken(sizeMatters=False, verbose=False):
    global bottle
    days = 0
    for day in range(1,201):
        if takeMedicine(sizeMatters, verbose):
            days += 1
        else:
            bottle = np.ones(100)
            break
    return days + 1

Average of a million first half-tablet sightings¶

In [7]:

def averageDays(sizeMatters=False, verbose=False, numberOfRuns=1000000):
    totalDays = 0
    for element in range(numberOfRuns):
        totalDays += daysTaken(sizeMatters, verbose)       
    return totalDays/numberOfRuns

Results¶

results

Extra: Entire State History¶

In [20]:

def completeRun():
    global bottle
    days = 0
    for day in range(1,201):       
        days += 1
        print("On Day {}: ".format(days))
        takeMedicine(1, 1)
    bottle = np.ones(100)

In [17]:

def currentStatus(noHalfPills=True, noMorePills=False):
    global bottle
    unique, counts = np.unique(bottle, return_counts=True)
    uniqueCounts = dict(zip(unique, counts))
        
    try:
        numFullPills = uniqueCounts[1.0]
    except KeyError:
        numFullPills = 0
    try:
        numHalfPills = uniqueCounts[0.5]
    except KeyError:
        numHalfPills = 0    
    return numFullPills, numHalfPills

In [40]:

completeRun()

On Day 1: 
Whole Tablets 99, Half Tablets 1     💊
On Day 2: 
Whole Tablets 98, Half Tablets 2     💊
On Day 3: 
Whole Tablets 97, Half Tablets 3     💊
On Day 4: 
Whole Tablets 96, Half Tablets 4     💊
On Day 5: 
Whole Tablets 95, Half Tablets 5     💊
On Day 6: 
Whole Tablets 94, Half Tablets 6     💊
On Day 7: 
Whole Tablets 93, Half Tablets 7     💊
On Day 8: 
Whole Tablets 92, Half Tablets 8     💊
On Day 9: 
Whole Tablets 91, Half Tablets 9     💊
On Day 10: 
Whole Tablets 90, Half Tablets 10     💊
On Day 11: 
Whole Tablets 89, Half Tablets 11     💊
On Day 12: 
Whole Tablets 88, Half Tablets 12     💊
On Day 13: 
Whole Tablets 87, Half Tablets 13     💊
On Day 14: 
Whole Tablets 86, Half Tablets 14     💊
On Day 15: 
Whole Tablets 85, Half Tablets 15     💊
On Day 16: 
Whole Tablets 84, Half Tablets 16     💊
On Day 17: 
Whole Tablets 83, Half Tablets 17     💊
On Day 18: 
Whole Tablets 82, Half Tablets 18     💊
On Day 19: 
Whole Tablets 81, Half Tablets 19     💊
On Day 20: 
Whole Tablets 80, Half Tablets 20     💊
On Day 21: 
Whole Tablets 80, Half Tablets 19     🚦 🚥
On Day 22: 
Whole Tablets 79, Half Tablets 20     💊
On Day 23: 
Whole Tablets 78, Half Tablets 21     💊
On Day 24: 
Whole Tablets 77, Half Tablets 22     💊
On Day 25: 
Whole Tablets 77, Half Tablets 21     🚦 🚥
On Day 26: 
Whole Tablets 76, Half Tablets 22     💊
On Day 27: 
Whole Tablets 75, Half Tablets 23     💊
On Day 28: 
Whole Tablets 75, Half Tablets 22     🚦 🚥
On Day 29: 
Whole Tablets 75, Half Tablets 21     🚦 🚥
On Day 30: 
Whole Tablets 74, Half Tablets 22     💊
On Day 31: 
Whole Tablets 73, Half Tablets 23     💊
On Day 32: 
Whole Tablets 72, Half Tablets 24     💊
On Day 33: 
Whole Tablets 71, Half Tablets 25     💊
On Day 34: 
Whole Tablets 70, Half Tablets 26     💊
On Day 35: 
Whole Tablets 69, Half Tablets 27     💊
On Day 36: 
Whole Tablets 68, Half Tablets 28     💊
On Day 37: 
Whole Tablets 68, Half Tablets 27     🚦 🚥
On Day 38: 
Whole Tablets 67, Half Tablets 28     💊
On Day 39: 
Whole Tablets 66, Half Tablets 29     💊
On Day 40: 
Whole Tablets 65, Half Tablets 30     💊
On Day 41: 
Whole Tablets 64, Half Tablets 31     💊
On Day 42: 
Whole Tablets 63, Half Tablets 32     💊
On Day 43: 
Whole Tablets 62, Half Tablets 33     💊
On Day 44: 
Whole Tablets 61, Half Tablets 34     💊
On Day 45: 
Whole Tablets 61, Half Tablets 33     🚦 🚥
On Day 46: 
Whole Tablets 60, Half Tablets 34     💊
On Day 47: 
Whole Tablets 60, Half Tablets 33     🚦 🚥
On Day 48: 
Whole Tablets 59, Half Tablets 34     💊
On Day 49: 
Whole Tablets 58, Half Tablets 35     💊
On Day 50: 
Whole Tablets 57, Half Tablets 36     💊
On Day 51: 
Whole Tablets 56, Half Tablets 37     💊
On Day 52: 
Whole Tablets 55, Half Tablets 38     💊
On Day 53: 
Whole Tablets 54, Half Tablets 39     💊
On Day 54: 
Whole Tablets 54, Half Tablets 38     🚦 🚥
On Day 55: 
Whole Tablets 53, Half Tablets 39     💊
On Day 56: 
Whole Tablets 53, Half Tablets 38     🚦 🚥
On Day 57: 
Whole Tablets 52, Half Tablets 39     💊
On Day 58: 
Whole Tablets 51, Half Tablets 40     💊
On Day 59: 
Whole Tablets 51, Half Tablets 39     🚦 🚥
On Day 60: 
Whole Tablets 51, Half Tablets 38     🚦 🚥
On Day 61: 
Whole Tablets 50, Half Tablets 39     💊
On Day 62: 
Whole Tablets 50, Half Tablets 38     🚦 🚥
On Day 63: 
Whole Tablets 49, Half Tablets 39     💊
On Day 64: 
Whole Tablets 48, Half Tablets 40     💊
On Day 65: 
Whole Tablets 48, Half Tablets 39     🚦 🚥
On Day 66: 
Whole Tablets 47, Half Tablets 40     💊
On Day 67: 
Whole Tablets 47, Half Tablets 39     🚦 🚥
On Day 68: 
Whole Tablets 46, Half Tablets 40     💊
On Day 69: 
Whole Tablets 46, Half Tablets 39     🚦 🚥
On Day 70: 
Whole Tablets 46, Half Tablets 38     🚦 🚥
On Day 71: 
Whole Tablets 46, Half Tablets 37     🚦 🚥
On Day 72: 
Whole Tablets 46, Half Tablets 36     🚦 🚥
On Day 73: 
Whole Tablets 45, Half Tablets 37     💊
On Day 74: 
Whole Tablets 44, Half Tablets 38     💊
On Day 75: 
Whole Tablets 43, Half Tablets 39     💊
On Day 76: 
Whole Tablets 42, Half Tablets 40     💊
On Day 77: 
Whole Tablets 41, Half Tablets 41     💊
On Day 78: 
Whole Tablets 40, Half Tablets 42     💊
On Day 79: 
Whole Tablets 39, Half Tablets 43     💊
On Day 80: 
Whole Tablets 38, Half Tablets 44     💊
On Day 81: 
Whole Tablets 38, Half Tablets 43     🚦 🚥
On Day 82: 
Whole Tablets 37, Half Tablets 44     💊
On Day 83: 
Whole Tablets 36, Half Tablets 45     💊
On Day 84: 
Whole Tablets 36, Half Tablets 44     🚦 🚥
On Day 85: 
Whole Tablets 35, Half Tablets 45     💊
On Day 86: 
Whole Tablets 35, Half Tablets 44     🚦 🚥
On Day 87: 
Whole Tablets 35, Half Tablets 43     🚦 🚥
On Day 88: 
Whole Tablets 35, Half Tablets 42     🚦 🚥
On Day 89: 
Whole Tablets 34, Half Tablets 43     💊
On Day 90: 
Whole Tablets 34, Half Tablets 42     🚦 🚥
On Day 91: 
Whole Tablets 33, Half Tablets 43     💊
On Day 92: 
Whole Tablets 32, Half Tablets 44     💊
On Day 93: 
Whole Tablets 32, Half Tablets 43     🚦 🚥
On Day 94: 
Whole Tablets 32, Half Tablets 42     🚦 🚥
On Day 95: 
Whole Tablets 32, Half Tablets 41     🚦 🚥
On Day 96: 
Whole Tablets 31, Half Tablets 42     💊
On Day 97: 
Whole Tablets 30, Half Tablets 43     💊
On Day 98: 
Whole Tablets 30, Half Tablets 42     🚦 🚥
On Day 99: 
Whole Tablets 29, Half Tablets 43     💊
On Day 100: 
Whole Tablets 29, Half Tablets 42     🚦 🚥
On Day 101: 
Whole Tablets 28, Half Tablets 43     💊
On Day 102: 
Whole Tablets 28, Half Tablets 42     🚦 🚥
On Day 103: 
Whole Tablets 27, Half Tablets 43     💊
On Day 104: 
Whole Tablets 27, Half Tablets 42     🚦 🚥
On Day 105: 
Whole Tablets 26, Half Tablets 43     💊
On Day 106: 
Whole Tablets 25, Half Tablets 44     💊
On Day 107: 
Whole Tablets 25, Half Tablets 43     🚦 🚥
On Day 108: 
Whole Tablets 24, Half Tablets 44     💊
On Day 109: 
Whole Tablets 24, Half Tablets 43     🚦 🚥
On Day 110: 
Whole Tablets 24, Half Tablets 42     🚦 🚥
On Day 111: 
Whole Tablets 24, Half Tablets 41     🚦 🚥
On Day 112: 
Whole Tablets 23, Half Tablets 42     💊
On Day 113: 
Whole Tablets 22, Half Tablets 43     💊
On Day 114: 
Whole Tablets 22, Half Tablets 42     🚦 🚥
On Day 115: 
Whole Tablets 21, Half Tablets 43     💊
On Day 116: 
Whole Tablets 20, Half Tablets 44     💊
On Day 117: 
Whole Tablets 20, Half Tablets 43     🚦 🚥
On Day 118: 
Whole Tablets 19, Half Tablets 44     💊
On Day 119: 
Whole Tablets 18, Half Tablets 45     💊
On Day 120: 
Whole Tablets 17, Half Tablets 46     💊
On Day 121: 
Whole Tablets 17, Half Tablets 45     🚦 🚥
On Day 122: 
Whole Tablets 17, Half Tablets 44     🚦 🚥
On Day 123: 
Whole Tablets 16, Half Tablets 45     💊
On Day 124: 
Whole Tablets 15, Half Tablets 46     💊
On Day 125: 
Whole Tablets 14, Half Tablets 47     💊
On Day 126: 
Whole Tablets 13, Half Tablets 48     💊
On Day 127: 
Whole Tablets 13, Half Tablets 47     🚦 🚥
On Day 128: 
Whole Tablets 13, Half Tablets 46     🚦 🚥
On Day 129: 
Whole Tablets 13, Half Tablets 45     🚦 🚥
On Day 130: 
Whole Tablets 13, Half Tablets 44     🚦 🚥
On Day 131: 
Whole Tablets 12, Half Tablets 45     💊
On Day 132: 
Whole Tablets 11, Half Tablets 46     💊
On Day 133: 
Whole Tablets 11, Half Tablets 45     🚦 🚥
On Day 134: 
Whole Tablets 11, Half Tablets 44     🚦 🚥
On Day 135: 
Whole Tablets 11, Half Tablets 43     🚦 🚥
On Day 136: 
Whole Tablets 11, Half Tablets 42     🚦 🚥
On Day 137: 
Whole Tablets 11, Half Tablets 41     🚦 🚥
On Day 138: 
Whole Tablets 11, Half Tablets 40     🚦 🚥
On Day 139: 
Whole Tablets 11, Half Tablets 39     🚦 🚥
On Day 140: 
Whole Tablets 11, Half Tablets 38     🚦 🚥
On Day 141: 
Whole Tablets 10, Half Tablets 39     💊
On Day 142: 
Whole Tablets 9, Half Tablets 40     💊
On Day 143: 
Whole Tablets 9, Half Tablets 39     🚦 🚥
On Day 144: 
Whole Tablets 8, Half Tablets 40     💊
On Day 145: 
Whole Tablets 8, Half Tablets 39     🚦 🚥
On Day 146: 
Whole Tablets 8, Half Tablets 38     🚦 🚥
On Day 147: 
Whole Tablets 8, Half Tablets 37     🚦 🚥
On Day 148: 
Whole Tablets 8, Half Tablets 36     🚦 🚥
On Day 149: 
Whole Tablets 7, Half Tablets 37     💊
On Day 150: 
Whole Tablets 6, Half Tablets 38     💊
On Day 151: 
Whole Tablets 5, Half Tablets 39     💊
On Day 152: 
Whole Tablets 5, Half Tablets 38     🚦 🚥
On Day 153: 
Whole Tablets 4, Half Tablets 39     💊
On Day 154: 
Whole Tablets 3, Half Tablets 40     💊
On Day 155: 
Whole Tablets 3, Half Tablets 39     🚦 🚥
On Day 156: 
Whole Tablets 3, Half Tablets 38     🚦 🚥
On Day 157: 
Whole Tablets 3, Half Tablets 37     🚦 🚥
On Day 158: 
Whole Tablets 3, Half Tablets 36     🚦 🚥
On Day 159: 
Whole Tablets 3, Half Tablets 35     🚦 🚥
On Day 160: 
Whole Tablets 3, Half Tablets 34     🚦 🚥
On Day 161: 
Whole Tablets 3, Half Tablets 33     🚦 🚥
On Day 162: 
Whole Tablets 3, Half Tablets 32     🚦 🚥
On Day 163: 
Whole Tablets 3, Half Tablets 31     🚦 🚥
On Day 164: 
Whole Tablets 3, Half Tablets 30     🚦 🚥
On Day 165: 
Whole Tablets 3, Half Tablets 29     🚦 🚥
On Day 166: 
Whole Tablets 3, Half Tablets 28     🚦 🚥
On Day 167: 
Whole Tablets 2, Half Tablets 29     💊
On Day 168: 
Whole Tablets 2, Half Tablets 28     🚦 🚥
On Day 169: 
Whole Tablets 2, Half Tablets 27     🚦 🚥
On Day 170: 
Whole Tablets 2, Half Tablets 26     🚦 🚥
On Day 171: 
Whole Tablets 1, Half Tablets 27     💊
On Day 172: 
Whole Tablets 1, Half Tablets 26     🚦 🚥
On Day 173: 
Whole Tablets 1, Half Tablets 25     🚦 🚥
On Day 174: 
Whole Tablets 1, Half Tablets 24     🚦 🚥
On Day 175: 
Whole Tablets 1, Half Tablets 23     🚦 🚥
On Day 176: 
Whole Tablets 1, Half Tablets 22     🚦 🚥
On Day 177: 
Whole Tablets 1, Half Tablets 21     🚦 🚥
On Day 178: 
Whole Tablets 0, Half Tablets 22     💊
On Day 179: 
Whole Tablets 0, Half Tablets 21     🚦 🚥
On Day 180: 
Whole Tablets 0, Half Tablets 20     🚦 🚥
On Day 181: 
Whole Tablets 0, Half Tablets 19     🚦 🚥
On Day 182: 
Whole Tablets 0, Half Tablets 18     🚦 🚥
On Day 183: 
Whole Tablets 0, Half Tablets 17     🚦 🚥
On Day 184: 
Whole Tablets 0, Half Tablets 16     🚦 🚥
On Day 185: 
Whole Tablets 0, Half Tablets 15     🚦 🚥
On Day 186: 
Whole Tablets 0, Half Tablets 14     🚦 🚥
On Day 187: 
Whole Tablets 0, Half Tablets 13     🚦 🚥
On Day 188: 
Whole Tablets 0, Half Tablets 12     🚦 🚥
On Day 189: 
Whole Tablets 0, Half Tablets 11     🚦 🚥
On Day 190: 
Whole Tablets 0, Half Tablets 10     🚦 🚥
On Day 191: 
Whole Tablets 0, Half Tablets 9     🚦 🚥
On Day 192: 
Whole Tablets 0, Half Tablets 8     🚦 🚥
On Day 193: 
Whole Tablets 0, Half Tablets 7     🚦 🚥
On Day 194: 
Whole Tablets 0, Half Tablets 6     🚦 🚥
On Day 195: 
Whole Tablets 0, Half Tablets 5     🚦 🚥
On Day 196: 
Whole Tablets 0, Half Tablets 4     🚦 🚥
On Day 197: 
Whole Tablets 0, Half Tablets 3     🚦 🚥
On Day 198: 
Whole Tablets 0, Half Tablets 2     🚦 🚥
On Day 199: 
Whole Tablets 0, Half Tablets 1     🚦 🚥
On Day 200: 
Whole Tablets 0, Half Tablets 0     🚦 🚥