5
$\begingroup$

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

Hints only please!

This is a confusing worded-problem.

We could break it into, $7$ cases but that would take very long?

Case 1: 3 chairs adjacent.

Ways to do this: $$\binom{10}{3} \cdot \binom{7}{7} = 120$$

But I see that, for the next, $\binom{10}{4}$.

So it will be:

$$1 + \binom{10}{3} + \binom{10}{4} + \binom{10}{5} + \binom{10}{6} + \cdots + \binom{10}{9}$$

$$= 1 + 120 + 210 + 252+\cdots$$

But this isnt a legit method it looks like.

I am not sure how to use PIE/anything else here?

$\endgroup$

4 Answers 4

2
$\begingroup$

We may count how many "circular strings" over the alphabet $\Sigma=\{0,1\}$ do not have three consecutive $1$s. Let $A_n$ be the number of regular strings in $\Sigma^n$ without three consecutive ones, and $C_n=|A_n|$. Since $a\in A_n$ may start only with $0,10,110$, we have: $$ C_1=2,C_2=4,C_3=7,\qquad C_n=C_{n-1}+C_{n-2}+C_{n-3} $$ so $C_n$ is a tribonacci number. Let we fix a conventional starting point in our circular strings avoiding $111$, by denoting it with a dot. We have the following possibilities:

$$ 0.0\quad 01.0\quad 011.0\quad 0.10\quad 01.10\quad 0.110\quad $$ so the number of circular strings with length $10$ avoiding $111$ is given by: $$ C_8+C_7+C_6+C_7+C_6+C_6 = C_8+2C_7+3C_6 = 149+2\cdot 81+3\cdot 44 = \color{blue}{443} $$ and the wanted number of subsets is given by: $$ 2^{10} - \color{blue}{443} = \color{red}{581}.$$

$\endgroup$
1
  • $\begingroup$ Nice solution, but I really don't understand it. I tried creating a recurrence relation but have failed a lot, since it is a very difficult task. Here is the issue, we start with: $0$ then two options $1$ or another $0$, but if you choose $1$ then what? How does the recurrence form after that? $\endgroup$
    – Amad27
    Jul 19, 2015 at 18:13
2
$\begingroup$

Another approach is to count the good configurations directly. There is one subset of size $10$, ${10 \choose 9}=10$ of size $9$, ${10 \choose 8}=45$ of size $8$ and ${10 \choose 7}=120$ of size $7$. All $176$ of these have three chairs in a row.

There are $10$ subsets of size $3$ that have three in a row. For subsets of size $4$ there are $10$ ways to choose the first of the three and six places for the other one where we exclude the one just before the three to avoid double counting four in a row. That gives $60$. For subsets of size $5$ there are $10$ ways to choose the three in a row and ${6 \choose 2}=15$ ways to choose the two others, again disallowing the one just before the set of three. That gives $150$. This paragraph totals $220$.

Finally we have subsets of size $6$. We follow the same approach as with $5$, choosing a block of three in $10$ ways, then choosing the three others in ${6 \choose 3}=20$ ways. There are fifteen configurations with two isolated sets of three, which we have counted twice. That gives $185$ subsets.

The grand total is $176+220+185=581$

$\endgroup$
0
$\begingroup$

The number of sets of exactly three adjacent chairs is $10$. Either they're chairs $1$, $2$, and $3$, or $2,3,4$, or $3,4,5$, etc. After $8,9,10$ comes $9,10,1$ and then $10,1,2$.

The number of subsets of the remaining set of seven chairs is $2^7=128$.

However, if one just picks $10\times128=1280$, then one is counting some combinations more than once. For example, if one has $1,2,3,4,6,7,8$, then one counts each of these: \begin{align} & \underbrace{1,2,3,}\ 4, 6, 7, 8 \\[10pt] & 1,\ \underbrace{2,3,4,}\ 6,7,8 \\[10pt] & 1,2,3,4,\ \underbrace{6,7,8} \end{align} But they're really all three the same combination and should be counted only once. One should therefore expect a smaller number than $1280$.

So I would search for combinations in which no chairs are adjacent or in which exactly two chairs are adjacent, and subtract that from the total number of subsets.

$\endgroup$
2
  • $\begingroup$ ... a smaller number than $1280$, also because $\{1,2,\ldots,9,10\}$ has only $2^{10}=1024$ subsets. $\endgroup$ Jul 10, 2015 at 21:50
  • $\begingroup$ @JackD'Aurizio : That too! ${}\qquad{}$ $\endgroup$ Jul 10, 2015 at 21:53
0
$\begingroup$

This probably isn't the elegant answer they were looking for, but if you consider the chairs to be ordered linearly (not circularly) then the number of ways of NOT getting 3 chairs in a row, as a function $F(n,k)$ of the number of such subsets of $n$ chairs that can be chosen linearly such that there is no contiguous subset of $3$ chairs chosen, and ends with $k$ contiguous chairs chosen, then you get:

$$F(n,0) = F(n-1,0) + F(n-1,1) + F(n-1,2)$$

$$F(n,1) = F(n-1,0)$$

$$F(n,2) = F(n-1,1)$$

Of course, then you need to take care of the circularity of the chairs and so you'll need to break into cases as to whether the initial binary indicator sequence of 2 chairs that may be taken is $00$, $01$, $10$, or $11$. Since $11$ and $10$ are the only possibilities for initial sequence that can cause you trouble when you choose the last 2 chairs, where you may get 3 contiguous chairs that cross the starting point of the circle, you can probably just keep track of each of those subcases separate and lump $00$ and $01$ starting sequences together.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.