0
$\begingroup$

I have this statement:

How many groups of $7$ elements can you get from the first $17$ natural numbers and at least $2$ of them must be consecutive ( Numbers can't repeat and order doesn't matter) ?

Basically, my development was:

I will get $17 \choose 7$ groups and I will subtract the combinations with two consecutive numbers or more.

To get all combinations with two consecutive numbers or more, I have different cases:

Case 1: All are consecutive numbers, This varies depending on the number when I start:

If I start from $1$, it will be: $1, 2, 3, 4 , 5 , 6 , 7$,

If I start from $2$, it will be: $2, 3, 4, 5 , 6 , 7 , 8$

Then, the maximum number from which I can begin is $11$ and will be: $11, 12, 13, 14, 15, 16, 17$.

Therefore, when all numbers are consecutive, I have $11$ possible cases.

I will do the same procedure for the other cases.

Case 2: Here I need only $6$ consecutive, so the maximum number that I can begin is $12$, so I have $12$ cases.

Therefore, for all consecutive, I have $11$ cases, for $6$ consecutive, I have $12$ cases, for $5$ I have $13$, for $4$ I have $14$, for $3$ I have $15$ and for $2$ consecutive numbers I have $16$ cases.

The total cases are: $11 + 12 + 13 + 14 + 15 + 16$ = $81$

Then I will subtract. Then, $\binom{17}{7} - 81 = 19448 - 81 = 19367$

But they told me, that my answer is bad. What have I done wrong and why?

How should it be done, following a logic similar to that of my development?

$\endgroup$
  • $\begingroup$ Sometimes it helps to consider the Principle of Inclusion/Exclusion when counting instances that require a side condition, as here with imposing (at least) two consecutive numbers in a set. $\endgroup$ – hardmath Aug 12 '18 at 15:26
  • 1
    $\begingroup$ Edited, the 17 first natural numbers, i.e $[1, 2 ... 17]$ $\endgroup$ – Eduardo S. Aug 12 '18 at 20:04
  • $\begingroup$ That principe help in these type of combinations with "at least" ? $\endgroup$ – Eduardo S. Aug 12 '18 at 20:05
  • $\begingroup$ There are more than $12$ cases for $6$ consecutive integers since you have to choose seven numbers. If you choose $1, 2, 3, 4, 5, 6$ or $12, 13, 14, 15, 16, 17$, the seventh number can be selected in $10$ ways (since it not be adjacent to those six numbers). For any other sequence of six consecutive numbers, the seventh number can be selected in $9$ ways (since it cannot be adjacent to either end of the sequence of six numbers). You are asking for trouble with your approach since you could have three consecutive, two consecutive, and two isolated integers such as $1, 2, 3, 6, 7, 11, 14$. $\endgroup$ – N. F. Taussig Aug 12 '18 at 20:40
  • $\begingroup$ Possible duplicate of Choosing $5$ elements from first $14$ natural numbers so that at least two of the five numbers are consecutive $\endgroup$ – user575478 Aug 14 '18 at 3:35
1
$\begingroup$

The problem is easier to handle if you subtract those selections in which no two numbers are consecutive from the total number of selections.

As you observed, there are $$\binom{17}{7}$$ ways to select $7$ of the first $17$ positive integers.

To count the number of selections in which no two of the selected are consecutive, we will arrange ten blue and seven green balls so that no two of the green balls are consecutive.

Place ten blue balls in a row, leaving enough space between successive balls and at the ends of the row in which to place a green ball.

arrangement_of_blue_balls

There are eleven such spaces, nine between successive blue balls and two at the ends of the row. To ensure no two green balls are consecutive, we choose seven of these eleven spaces in which to place a green ball. For instance, if we choose the first, second, third, fourth, sixth, eighth, and ninth spaces, we obtain

arrangement_of_blue_and_green_balls

If we now number the balls from left to right, the numbers on the green balls are the desired set of seven numbers, no two of which are consecutive. Hence, there are $$\binom{11}{7}$$ selections of $7$ of the first $17$ positive integers in which no two of the selected integers are consecutive.

Hence, the number of selections of $7$ of the first $17$ positive integers in which at least two numbers are consecutive is $$\binom{17}{7} - \binom{11}{7}$$

$\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.