Choice Problem: choose 5 days in a month, consecutive days are forbidden

Question

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand.

Example 3.19. A medical student has to work in a hospital for five days in January. However, he is not allowed to work two consecutive days in the hospital. In how many different ways can he choose the five days he will work in the hospital?

Solution. The difficulty here is to make sure that we do not choose two consecutive days. This can be assured by the following trick. Let $a_1, a_2, a_3, a_4, a_5$ be the dates of the five days of January that the student will spend in the hospital, in increasing order. Note that the requirement that there are no two consecutive numbers among the $a_i$, and $1 \le a_i \le 31$ for all $i$ is equivalent to the requirement that $1 \le a_i < a_2 — 1 < a_3 — 2 < a_4 — 3 < a_5 — 4 \le 27$. In other words, there is an obvious bijection between the set of 5-element subsets of [31] containing no two consecutive elements and the set of 5-element subsets of [27].

*** Instead of choosing the numbers $a_i$, we can choose the numbers $1 \le a_i < a_2 — 1 < a_3 — 2 < a_4 — 3 < a_5 — 4 \le 27$, that is, we can simply choose a five-element subset of [27], and we know that there are $\binom{27}{5}$ ways to do that.

What I don't understand here $1 \le a_i < a_2 — 1 < a_3 — 2 < a_4 — 3 < a_5 — 4 \le 27$:

• Why do the subtracting numbers increment with every other $a_i$?
• Why 27?

And the very last sentence (***) is unclear to me.

• Why is there no talk about "non-consecutive"? Why choosing 5 elements of 27 is equivalent to choosing 5 non-consecutive elements out of 31? I miss the connection.

I'd be very thankful if you could help me to understand this example!

Answer 1

The prohibition on consecutive days means the constraints are really $$1 \le a_1$$ $$a_1+1 \lt a_2$$ $$a_2+1 \lt a_3$$ $$a_3+1 \lt a_4$$ $$a_4+1 \lt a_5$$ $$a_5 \le 31.$$ Rewrite these so that the right hand side of each line is the same as the left hand side of the next line as $$1 \le a_1$$ $$a_1 \lt a_2-1$$ $$a_2-1 \lt a_3-2$$ $$a_3-2 \lt a_4-3$$ $$a_4-3 \lt a_5-4$$ $$a_5 -4 \le 27$$ and you can now combine these as a single line $$1 \le a_1 < a_2 — 1 < a_3 — 2 < a_4 — 3 < a_5 — 4 \le 27$$

Added for extended question:

Having done that, you could let $b_1=a_1$, $b_2=a_2-1$, $b_3=a_3-2$, $b_4=a_4-3$, and $b_5=a_5-4$, so $$1 \le b_1 < b_2 < b_3 < b_4 < b_5 \le 27$$ and so the number of integer solutions for the $b_i$ is obviously the same as the number of ways of choosing $5$ distinct integers from $27$, i.e. ${27 \choose 5}$.

Having chosen the $b_i$ in order from smallest to largest, you can get back to the $a_i$ (the working days) by adding $0$ to the smallest, $1$ to the next, $2$ to the middle one, $3$ to the next, and $4$ to the largest. It is obvious that this will give five dates with at least ones day's gap between them.

Answer 2

Let's look at a simpler example - choosing 3 days from 6, such that there are no two consecutive days. Obviously there are four ways to do this - any of $(1,3,5)$, $(1,3,6)$, $(1,4,6)$ or $(2,4,6)$.

Formalizing the problem, you need to choose $(a_1,a_2,a_3)$ such that $1 \leq a_i \leq 6$ and there are no consecutive choices. Without loss of generality, let $a_1 < a_2 < a_3$ (which ensures the days are unique). Since you require $a_1$ and $a_2$ to be at least two days apart, you require $a_1 \leq a_2 - 2$, which is equivalent to $a_1 < a_2-1$ (since the $a_i$ are integers). You also require $a_2 \leq a_3-2$, which is equivalent to $a_2 < a_3-1$, which is equivalent to $a_2-1 < a_3-2$. Clearly you require $a_3 \leq 6$, which is equivalent to $a_3-2 \leq 4$, so you can put your constraints together as

$$1 \leq a_1 < a_2-1 < a_3-2 \leq 4$$

Now defining $n_i = a_i - i + 1$ you get

$$1 \leq n_1 < n_2 < n_3 \leq 4$$

and the solution is obvious.

Generalizing to the case where you have $N$ days and need to choose $K$ of them with no two adjacent, you have

$$1 \leq a_1 < a_2-1 < a_3-2 < a_4-3 < \cdots < a_K - K + 1 \leq N-K+1$$

which should allow you to solve your problem.

Answer 3

The number 27 is there because he has to work 5 days in January, and January has 31 days. So, after he picks the 1st day to work, he can only pick from among 30 days for the 2nd day, et cetera until he has 27 days from which he can pick his 5th day.

The subtractions, I believe, are just illustrating that once the student picks his 1st day, the 2nd day has to have at least 1 day between it, and these increase for the 3rd, 4th, and 5th day. For example, let's say he chooses to work January 1st. Then, he cannot work January 2nd, but he could work January 3, 4,.... So, if our $a_1 = 1$, then $a_2=3, 4, \dots$ or $a_1 < a_2 - 1$. You can just carry these reasoning to see why you have to subtract 2, 3, and 4 days as well.

Answer 4

These kind of problems can be generalized to a single formula in the following manner:

Suppose I have $n$ objects arranged in a row and I pick any $r$ objects such that no two of them are consecutive. I want to calculate in how many ways I can do this. To do that I first randomly select $r$ objects and take them out. Now there are $n-r$ objects left in the line and as a consequence there are $n-r+1$ gaps that can be filled between these objects. The number of ways in which I can fill these gaps is $\binom{n-r+1}{r}$. Since selection and deselection are equivalent in combinatorics, the answer to my problem is this only.

Now coming to your problem, in January there are 31 days and you have to select any 5 non-consecutive ones. The formula says that the answer would be:$$\binom{31-5+1}{5}$$which is nothing but $\binom{27}{5}$.

I'm sorry for not adhering to the solution in your book but I really think that this way is easier to understand.

Answer 5

Henry's answer for the first part is already very good, so this only tries to tackle the sentence ***.

Understanding the correspondence between five element subsets of $[27]$ and the non-consecutive days problem might be easier by going from the five element subsets of 27 to the days problem asked, rather than the other way around.

We know that we'll be forbidden from working on four specific days -- namely, the days after the first four workdays. (We're technically forbidden from working the day after the fifth workday, too, but since we've already filled our monthly quota who cares?) -- so let's throw them out now and worry about which days exactly we've thrown out later. We're now left with days we'll number 1 to 27.

So let's pick five workdays out of the remaining twenty seven (here's our five element subset of $[27]$) and reconstruct the monthly calendar. I'm going to use $a_i$ for the numbers we picked from $[27]$ and $c_i$ for how they'll appear as days of the month a normal human calendar. By way of example I'm going to say we picked $\{3,4,12,15,20\}$

For $a_1$ we needn't do anything, we'll just copy it down as $c_1$ and say our first workday is Jan. 3d. We're forbidden from working the next day, so we put back the first of the four days we discarded and increment our remaining $a_i$ by one. This fixes our problem with $a_2=4$, and informs us we next have work on the 5th. We do the same for the three $a_i$ left and so on.

In the end, our five element set from $[27]$ is mapped to the $a_1$ (3rd), $a_2+1$ (5th), $a_3+2$ (14th), $a_4+3$ (18th), and $a_5+4$ (24th) days of January. (Proof that this is actually a bijection is left out, but not really difficult so eh).