Pills puzzle
Jun. 30th, 2012 10:15 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ciphergothThe following puzzle appears on Futility Closet:
My doctor wants to establish a dosage for a new drug, so he gives me a bottle of 48 pills and tells me to take them throughout the month of June. I can take as many or as few as I like on any given day, so long as I take at least 1 pill each day. Show that there’s a sequence of consecutive days during which I take exactly 11 pills.
You can click through that link for their solution. Here's what I want to know.
In their proof, they write 2 numbers on each of 30 days, and they write 59 different numbers, and invoke the pigeonhole principle to show that some number must be written twice. I think we can take this further: if we're writing cumulative totals, we should write them between days, not on days. So we start before 1 June by writing 0 pills, and finish after 30 June by writing 48 pills, then write the row above. So we really write the 60 numbers from 0-59 in 62 places.
There therefore must be an interval between which I took 12 pills, since this still only gives us the 61 numbers 0-60 to write in the 62 slots.
First question: is the above correct? Must a 12-pill interval exist?
Let's suppose I take one pill each day except for the 15th, on which I take the other 19 pills. Then there is no interval during which I take exactly 16, 17, or 18 pills; any interval that doesn't include the 15th has at most 15 pills in it, while any that does has at least 19.
Second question: does the above counterexample work? Can you extend it to handle any other intervals?
If we have p pills to take over d days, where d < p < 2d, the above proof shows that there must be an interval in which we take exactly l pills for 0 <= l <= 2d - p. The above counterexample shows that there need not be such an interval where d < 2l and l <= p - d.
Supposing we take 19 pills over 11 days like this:
x
x
x
xxxxx
x
x
x
xxxxx
x
x
x
Then there's no interval in which we take 4 pills. So there's a counterexample for l if there's some k > 0 for which d < l(k+1) and p >= d + kl.
Obvious third question: given d days and p pills, where d < p < 2d, what is the rule that tells us whether an interval of l pills has to exist?
jack suggested a different way of looking at this puzzle on Facebook. Instead of imagining the days as slots in which you have to fit the pills, imagine the 48 pills laid out in a row in front of you. The midnight at the start of June is at one end, and the one at the finish at the other. You have to fit the other 29 midnights in the gaps between the pills in such a way that there's at most one midnight in each gap, and no two midnights are exactly 11 pills apart. From this it follows immediately that having more days can only hurt, never help, and the above counterexamples flow from a simple "greedy" strategy of going from gap to gap, putting in a midnight in each gap if you can without breaking the rule. If we can prove that this greedy strategy is optimal, the problem is solved.
Update I'm now convinced that there is always a greedy strategy. Arrange the pills in rows of 11; now the rule is simply that no midnight may have a midnight directly below it. So for any allowable arrangement, I think you can turn it into a greedy arrangement by shuffling midnights upwards, moving whole columns leftwards, and taking midnights from the end to move them into empty columns. Need to think about the immovable midnights at either end to make this rigorous.
Update with answer: There is a way of taking p pills over d days with no l-pill intervals iff p ≠ l and d < floor((p+l+1)/2). Update to the update: This answer is slightly wrong. Update with new answer: There is a way of taking p pills over d days with no l-pill intervals iff p ≠ l and 2d ≤ p + min(p mod 2l, 2l - (p mod 2l) -2)
My doctor wants to establish a dosage for a new drug, so he gives me a bottle of 48 pills and tells me to take them throughout the month of June. I can take as many or as few as I like on any given day, so long as I take at least 1 pill each day. Show that there’s a sequence of consecutive days during which I take exactly 11 pills.
You can click through that link for their solution. Here's what I want to know.
In their proof, they write 2 numbers on each of 30 days, and they write 59 different numbers, and invoke the pigeonhole principle to show that some number must be written twice. I think we can take this further: if we're writing cumulative totals, we should write them between days, not on days. So we start before 1 June by writing 0 pills, and finish after 30 June by writing 48 pills, then write the row above. So we really write the 60 numbers from 0-59 in 62 places.
There therefore must be an interval between which I took 12 pills, since this still only gives us the 61 numbers 0-60 to write in the 62 slots.
First question: is the above correct? Must a 12-pill interval exist?
Let's suppose I take one pill each day except for the 15th, on which I take the other 19 pills. Then there is no interval during which I take exactly 16, 17, or 18 pills; any interval that doesn't include the 15th has at most 15 pills in it, while any that does has at least 19.
Second question: does the above counterexample work? Can you extend it to handle any other intervals?
If we have p pills to take over d days, where d < p < 2d, the above proof shows that there must be an interval in which we take exactly l pills for 0 <= l <= 2d - p. The above counterexample shows that there need not be such an interval where d < 2l and l <= p - d.
Supposing we take 19 pills over 11 days like this:
x
x
x
xxxxx
x
x
x
xxxxx
x
x
x
Then there's no interval in which we take 4 pills. So there's a counterexample for l if there's some k > 0 for which d < l(k+1) and p >= d + kl.
Obvious third question: given d days and p pills, where d < p < 2d, what is the rule that tells us whether an interval of l pills has to exist?
jack suggested a different way of looking at this puzzle on Facebook. Instead of imagining the days as slots in which you have to fit the pills, imagine the 48 pills laid out in a row in front of you. The midnight at the start of June is at one end, and the one at the finish at the other. You have to fit the other 29 midnights in the gaps between the pills in such a way that there's at most one midnight in each gap, and no two midnights are exactly 11 pills apart. From this it follows immediately that having more days can only hurt, never help, and the above counterexamples flow from a simple "greedy" strategy of going from gap to gap, putting in a midnight in each gap if you can without breaking the rule. If we can prove that this greedy strategy is optimal, the problem is solved.Update I'm now convinced that there is always a greedy strategy. Arrange the pills in rows of 11; now the rule is simply that no midnight may have a midnight directly below it. So for any allowable arrangement, I think you can turn it into a greedy arrangement by shuffling midnights upwards, moving whole columns leftwards, and taking midnights from the end to move them into empty columns. Need to think about the immovable midnights at either end to make this rigorous.
Update with answer: There is a way of taking p pills over d days with no l-pill intervals iff p ≠ l and d < floor((p+l+1)/2). Update to the update: This answer is slightly wrong. Update with new answer: There is a way of taking p pills over d days with no l-pill intervals iff p ≠ l and 2d ≤ p + min(p mod 2l, 2l - (p mod 2l) -2)
