If we consider a box containing $n$ balls numbered from $1$ to $n$. If $455$ is the number of ways to get three balls from the box such that no two balls are consecutively numbered, then we have to find the value of $n$.
Someone please help me out in this. I am not getting anything, how to start it?
On
As I tend to make mistakes with this kind of problems, I asked my friend Ruby to do some test runs. She is pretty fast at counting and makes no silly mistakes if I explained it well.
We got different numbers, much larger numbers until I realized that order should not matter for a draw, so drawing $1,3,5$ is considered the same as drawing $5,3,1$. Then Ruby found $455$ non-consecutive draws for $n=17$ balls, confirming Arthur's formula.
Here is what I told her: balls.rb
This is what she found: balls.log
On
By the multiplicative rule we get nC1 *n-3C1*n-6C1 (every time we choose a ball its successor and predecessor is eliminated). This is n(n-3)(n-6).
On
We can choose the three numbers by lining up a string of $3$ "$1$"s and $n-3$ "$0$"s with a list of the numbers from $1$ to $n$.
We can break down the situations in which no two consecutive numbers appear into two cases
Strings that don't end in "$\boldsymbol{1}$":
$3$ substrings of "$10$" and $n-6$ substrings of "$0$". We can count these as $$ \binom{n-3}{3} $$ Strings that do end in "$\boldsymbol{1}$":
$2$ substrings of "$10$" and $n-5$ substings of "$0$" and a final substring of "$1$". We can count these as $$ \binom{n-3}{2} $$ The total number of strings in which no two consecutive numbers appear $$ \binom{n-2}{3}=\frac{(n-3)^3-(n-3)}6 $$ which is approximately $\frac{(n-3)^3}6$. Inverting $\frac{(n-3)^3}6$ at $455$, we get $$ (6\cdot455)^{1/3}+3=16.9761 $$ Trying $$ \binom{17-2}{3}=455 $$ we see that $n=17$ is the answer.
Another Way To Count
If we tack on an extra placeholder past the numbers from $1$ to $n$ and include an extra "$0$", we can then cover all the situations where no consecutive numbers are chosen with $3$ "$10$"s and $n-5$ "$0$"s. This directly gives us $$ \binom{n-2}{3} $$ arrangements.
Here is the situation selecting $1$, $5$, and $n$. Note the extra space to the right of $n$ for the "$0$" of "$10$" or just a "$0$" to go.
On
The general problem at hand is this: How many ways are there to choose $k$ out of $n$ numbered balls such that no two chosen balls have consecutive numbers?
To approach this, think about lining up the $n-k$ balls that are not chosen. Then insert the chosen balls between the unchosen balls, where they belong in the line. If no two chosen balls are consecutive, each chosen ball gets stuck between a different pair of unchosen balls. Conversely, any way of sticking $k$ chosen balls between $n-k$ unchosen balls, such that no two chosen balls are between the same pair of unchosen balls, gives a choice of $k$ non-consecutive balls from the total $n$ balls.
So we see that the number of ways to choose $k$ non-consecutive balls out of $n$ total balls is precisely the number of ways to put $k$ chosen balls between $n-k$ unchosen balls, with at most one chosen ball between any two unchosen ones. Note that we can also put a chosen ball on the far left or far right of the line of unchosen balls, so the total number of places to put the chosen balls is $n-k+1$ (explicitly, the chosen balls can be to the left of the first unchosen ball, to the left of the second, to the left of the third, ..., to the left of the last unchosen ball, or to the RIGHT of the last unchosen ball).
Thus the number of interest is the number of ways to put $k$ chosen balls in $n-k+1$ locations, i.e. $\binom{n-k+1}{k}$.
For the problem of interest, $k=3$, and we want to know for which $n$ is $455=\binom{n-3+1}{3} = (n-2)(n-3)(n-4)/6$. This is a polynomial you can solve (or, more likely, just check a few cases), and it has solution $n=17$.
There are $\binom{n}{3}$ ways to pick three balls. Now to exclude the ones with two or more consecutive balls.
We do this by counting in how many ways we can pick two consecutive balls, and then a single ball from what's left. There are $n-1$ ways to pick two consecutive balls, and then there are $n-2$ balls left. So there are $(n-1)(n-2)$ ways to pick two consecutive balls and then one ball. However, this counts every case of three consecutive balls twice. We therefore need to subtract them once. There are $n-2$ ways to do that, so we get $(n-1)(n-2) - (n-2) = (n-2)^2$.
Therefore the total number of ways to pick three balls so that none are consecutive is $\binom n3 - (n-2)^2 = \frac{n^3 - 9n^2 +26n - 24}{6}$. You want to find the $n$ that makes this fraction equal to $455$.