Selecting 3 non-consecutive days of the week [duplicate]

$\begingroup$

We need to find how many groups of $3$ days of the week there can be, given that no two days should be consecutive. The answer should be $7$, but I do not know how to get to the answer. Thanks in advance.

$\endgroup$ 6

4 Answers

$\begingroup$

Use 1010100 to represent that you 'pick' the first, third, and fifth day of the week. What ways are there to pick three non-consecutive days?

$1010100$

$1010010$

$1001010$

$0101001$

$0100101$

$0010101$

$0101010$

And that's it.

It turns out to be equal to the number of days in the week since as you can see there is one time where you have two days that you don't pick (the two 0's), and that 00 bit can start at any of the 7 days, fixing the rest of the sequence.

$\endgroup$ 7 $\begingroup$

For each day of the week $X$, there is exactly one way to select an arrangement so that $X$ is not one of the three days nor one of the three days immediately following them. So there are exactly seven possible arrangements, one for each choice of $X$.

$\endgroup$ $\begingroup$

You can find a recurrence relation to solve this question. Let $\{1,\ldots, n\}$ be an n element set and let $f(n,k)$ be the number of $k$ element subsets with no two elements consecutive where we identify $1$ and $n$ as consectuive. In our case we are looking for $f(7,3)$. Note that $$ f(n,k)=f(n-3,k-1)+f(n-1,k)\;\;\;\;\;\;\; n\geq 3 $$ by classifying such subsets which contain $1$ (and hence can't contain 2, and $n$) and such subsets which don't contain $1$. The initial conditions are $f(n,0)=1$. From here compute.

$\endgroup$ $\begingroup$

The general formula for the number of circular arrangements of $k$ elements over $n$ spots with no consecutive elements is $$\binom{n-k}{k}+\binom{n-k-1}{k-1}$$ See Selection in Circular Table for a proof.

$\endgroup$