# Prove that there's a consecutive sequence of days during which I took exactly 11 pills

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.

Adapted from Kenneth R. Rebman, “The Pigeonhole Principle (What It Is, How It Works, and How It Applies to Map Coloring),” The Two-Year College Mathematics Journal, January 1979.

Consider the sequence of numbers representing the total number of pills you have taken up to each day.

Its elements are all are positive integers in the range [1,48].
No element is repeated (because it is strictly increasing).
It contains 30 elements.

The statement to be proven can be expressed as the following statement about the sequence:

There exist two indices, $$x,y | x, such that $$u_y-u_x = 11$$.

### Attempt #1

We can "prove" that by the following logic:

There are 48 numbers in the range [1,48].
For each $$x$$ in the range [1,37], there exists a $$y$$ such that $$y-x=11$$ and $$y$$ is in [1,48]: namely $$y=x+11$$.
For each $$y$$ in the range [12,48], there exists an $$x$$ such that $$y-x=11$$ and $$y$$ is in [1,48]: namely $$x=y-11$$.
From the two above statements, we can prove that for every number in [1,48], there exists at least one number either above or below it that differs by exactly 11. Thus, there are at most 24 pairs of numbers that can be in the sequence without any two elements differing by exactly 11.
June has 30 days, which is more than 24.
Therefore the sequence has more than 24 elements in it.
Therefore it must contain two elements that differ by exactly 11.

This looks like it works, but there is actually a flaw in the logic here - specifically:

It's possible for two numbers to share a counterpart. For example, the among the numbers 1, 12, 23, 34, and 45, we only need to exclude 2. Thus, we can't split the 48 possible numbers into 24 pairs where we can take at most one - some of them will be triplets where we can take up to 2.

However, correcting that leads us to a correct solution.

### Attempt #2:

Consider the following table:

0 11 22 33 44
1 12 23 34 45
2 13 24 35 46
3 14 25 36 47
4 15 26 37 48
5 16 27 38
6 17 28 39
7 18 29 40
8 19 30 41
9 20 31 42
10 21 32 43

Using that table, we can then follow logic similar to the above:

Consider the set of numbers which are part of the sequence representing the total number of pills we have taken at each day.
We must always take 0, to represent the time before the experiment started. This also means that we have 31 days to consider.
If we take an element from a row, we cannot take the elements adjacent to it in the same row.
Thus we can take a maximum of $$\lceil\frac{rowlength}{2}\rceil$$ of the elements from each row - that is 3 each from the first 5 rows, and 2 each from the remaining 6 rows, for a total of 27 elements.
Because June has more than 26 days (remembering that we count the day from before the experiment started, and 26+1 = 27), we must violate this condition on at least one row.

• 25 > 24, but the following 25-day schedule has no consecutive sum of 11: 2 1 1 12 1 1 1 1 1 1 1 1 1 1 12 1 1 1 1 1 1 1 1 1 1 Commented Aug 15 at 22:19
• @RobPratt - Ah, I see where I went wrong; it's possible for two numbers in the set to correspond to the same number which is not in the set, so splitting it into 24 distinct pairs of numbers isn't correct. Commented Aug 15 at 22:59
• @RobPratt - I've fixed the logic. With this correction, I believe the minimum is actually 27 days. Commented Aug 15 at 23:11
• Yes, with 48 pills, a 26-day 11-free schedule is possible, but a 27-day 11-free schedule is not. Commented Aug 16 at 1:30
• I cleaned up my answer a bit to make it clear which part of it was originally incorrect (since it's now the accepted answer). I don't think my answer should have been accepted, as Ankoganit's answer was posted before mine and also supplies a sufficient proof. Commented Aug 17 at 5:39

Suppose I record the number of pills I take each day, and write down a sequence of numbers that shows:

how many total pills I have taken so far, after each day. So if I take 2 pills on day 1, 1 on day 2, 4 on day 3, my list would start as 2, 3, 7,... because I'd have taken 2 pills by the end of the first day, 3 by the end of the second day, and so on. This list would have 30 entries, one made after each day on June.

Now let's suppose I write down a second list of numbers, and this list would have

the numbers in the previous list each added to 11. So in the previous scenario, my second list would start as 13, 14, 18, ...

What kind of numbers can appear on these lists?

The smallest number can be 1. Since there are only 48 pills, the biggest number could be 48+11=59.

Now here's where the pigeonhole principle comes in.

The two lists have 60 entries between them, and they only contain numbers between 1 and 59, so something has to repeat! This repetition cannot be in the same row: each row consists of numbers that are strictly increasing. So some entry in the first row, say the $$a$$-th entry, equals (say) the $$b$$-th entry on the second row.

Looking back at how we constructed these lists, this means,

The total number of pills I've taken till day $$a$$ is 11 more than the total number of pills I've taken till day $$b$$. This means starting right after day $$b$$ and continuing till day $$a$$, we get a stretch of consecutive days where I've taken exactly 11 pills.

• I think this is the simplest solution involving PHP already. Probably the wording/phrasing is what makes it sounds like complicated (not slighting Ankoganit, phrasing a proof is hard!). At its core, the proof is: a_i is total pills at day i, then b_i=a_i+11. The range of numbers in a_i union b_i is 1 to 59, but there are 60 numbers. a_i and b_i are strictly increasing, so there exists a_i = b_j. QED. The core idea is short. Commented Aug 15 at 13:44
• Also, 48 is not the highest number of pills with this property. You can still guarantee 11 pills with 51 total pills (with 52 it's possible to take the pills in a way there is no exact 11 pills consecutive). So since it's not a strict limit, I believe the intent of the problem setter is to use this proof, since this proof doesn't work as cleanly with 49 pills (60 numbers, 60 range instead of 59 range) Commented Aug 15 at 13:57
• @JaapScherphuis "1"x10, "12"x1, "1"x8, "12"x1, "1"x10 would be an example. Commented Aug 15 at 17:25
• IMO "intuitive" can be subjective. 30+30 = 60 and 48 + 11 = 59. I see nothing unintuitive about this. Commented Aug 16 at 8:13
• @HemantAgarwal FWIW - My answer is unintuitive enough that I got it wrong the first time I tried, and even after knowing it was wrong, it wasn't immediately obvious where the error was, because the error was in a step where the explanation was (to me) equally as "intuitively" convincing as the correct answer ended up being. "For every hard problem, there is a solution that is elegant, simple, and wrong." Commented Aug 16 at 18:59

Let $$a_1,a_2,\dots,a_{30}$$ be the finite sequence of the number of pills taken on the days respectively $$1,2,\dots,30$$. Let $$s_1,s_2,\dots,s_{30}$$ be the strictly increasing sequence of partial sums of the pills taken up to the day $$1,2,\dots,30$$, including that day. So $$s_1=a_1\ge 1$$, $$s_2=a_1+a_2=s_1+a_2>s_1$$, and so on, $$s_{30}=a_1+a_2+\dots+a_{30}\le 48$$. (I will remove the hypothesis that the pills have to be taken all at the end, thus relaxing the data of the problem.)

So the problem is equivalent to the following one. Some $$30$$ different numbers are extracted among the numbers from $$1$$ to $$48$$. Show that there are two with difference $$11$$.

Assume this is false. We are building the bins, $$A,B,C,D,E$$ as the intervals of integer numbers: \begin{aligned} A &= [1,11]\ , & C &= [23,26]\ , & D &= [27,37] \\ B &= [12,22]\ ,&&& E &= [38,48] \ . \end{aligned} Assume we have $$a,b;c;d,e$$ numbers from the bins $$A,B,C,D,E$$ respectively in our extraction.

• Each number $$x$$ from $$A$$ excludes furthermore the number $$x+11$$ from $$B$$ being taken. We mark with a cross this $$2a$$ places.
• Each number $$y$$ from $$B$$ excludes furthermore the number $$x-11$$ from $$A$$ being taken. We mark with a cross this $$2b$$ places.
• So far we have $$2(a+b)$$ crosses, that do not interfere in the bins $$A,B$$.
• By symmetry, and the same argument, we obtain $$2(d+e)$$ crosses that do not interfere in the bins $$D,E$$.
• Add the $$c$$ places from $$C$$ as crosses. We have $$2a+2b+c+2d+2e$$ distinct crosses in the interval from $$1$$ to $$48$$. So \begin{aligned} a+b+c+d+e &= 30\ ,\\ 2a+2b+c+2d+2e &\le 48\ . \end{aligned} Well, it is clear that we have an immediate contradiction. For instance from $$c\le 4$$ we have $$56= 2\cdot 30-4\le 60 -c=2(a+b+c+d+e)-c\le 48\ .$$

$$\square$$

We have a slight generalization:

The doctor gave me $$\bbox[lightyellow]{\color{red}{\ 51\ }}$$ pills, to take one or more every day of June. I may take them all till the end of the month, or not. (For instance, I may want to take only $$48$$ of them.) Then there are some consecutive days where I take exactly $$11$$ pills.

For the proof, let $$N$$ be $$51$$. The bins $$A,B$$, respectively $$D,E$$ contain the first $$22$$, respectively the last $$22$$ numbers in the interval $$[1,N]$$. The same argument gives: $$60-(N-44)\le 2a+2b+c +2d+2e=N\ ,$$ so $$104\le 2N$$, $$52\le N$$. This is a contradiction for $$N=51$$, and cannot be improved (to work with this lazy argument).

Note: In a first false answer, I wanted to get the optimal upper bound for the number of pills, the argument using three bins was not clean for the reasons pointed out by Jaap Scherphuis in the comments, (many thanks, unfortunately I cannot give points as credit for this,) and the idea could not be saved. The present five bins estimation is "generous", and may be maybe improved. But my urgent need was to have a valid answer.

Note: A second answer was given, but its generalization suffered. Thanks for putting the finger on the wound to user2357112. I hope it is all fine now.

• Oh, yes, thanks, i have to rethink, and retype... @JaapScherphuis Commented Aug 15 at 12:52
• Your generalization doesn't quite work, because adding more pills requires you to adjust the size of the bins. The 56 bound relies on the bin sizes you established for 48 pills. Adding more pills changes the bound. Commented Aug 15 at 17:54
• @user2357112 Oh, yes, i have a moving target, have to go down to $51$... Thanks for the comment! Commented Aug 15 at 18:06

If considered relevant, here is a script to simulate this problem with actual numbers, for exemplification purposes.

R code:

total_N_pills = 48

a = integer()
s = integer()
si = 0
sc = 0
pills_left_to_take = total_N_pills

#set.seed(20240816)

for (day in 1:30) {
max_pills_today = pills_left_to_take - (30 - day)
min_pills_today = ifelse(day != 30, 1, pills_left_to_take)
si = ifelse(min_pills_today != max_pills_today,
sample(min_pills_today:max_pills_today, 1, prob = 1 / (min_pills_today:max_pills_today)^2),
min_pills_today
)
pills_left_to_take = pills_left_to_take - si
a = c(a, si)
sc = sc + si
s = c(s, sc)
cat("\nDay ", day, ", min = ", min_pills_today, ", max = ", max_pills_today)
cat("\n", si, " pills taken, total = ", sc)
cat("\n", pills_left_to_take, " pills left to take in ", (30-day), " days.")
cat("\n")
}

cat("\na =", a)
cat("\ns =", s)
s_11 = s + 11
cat("\ns +  11 = ", s_11 )
inters = intersect(s, s_11)
for (inters_i in inters) {
day_a = which(s == inters_i)
day_b = which(s_11 == inters_i)
cat("\n\nDays from ", day_b + 1, " to ", day_a, " -> ", sum(a[(day_b + 1):day_a]))
}