Is there an alternative? Part 2

Once again the chocolates are back . This time 30 different chocolates are placed on table in a circle . Now , my friend Guillermo Templado has to pick up 6 chocolates such that between each of the chosen chocolates there are at least 2 chocolates. In how many ways can he pick up his chocolates ?

P.S: What if the chocolates were placed on a straight line?


The answer is 30940.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Laurent Shorts
Feb 13, 2017

First, let's find the answer to the second question, as it will help us.

If there are 30 identical chocolates in a line, instead of picking them up, we can put them in some order: put the 6 chocolates you want to eat (written X ) and then put the 2 mandatory chocolates (written o ) in between each X .

_Xoo_Xoo_Xoo_Xoo_Xoo_X_

You are left with 30 16 = 14 30-16=14 chocolates, that you have to put in 7 spaces (written _ ): between the X 's, at the far left, or at the far right. As you can put several times some chocolate in any of these spaces, that's a multicombination and there's ( ( 7 14 ) ) = ( 7 + 14 1 14 ) = ( 20 14 ) = 3 8 760 \Big(\!\!\Big(\begin{matrix}7\\14\end{matrix}\Big)\!\!\Big)={7+14-1 \choose 14}={20 \choose 14}=38'760 ways, by stars and bars , to do that.

With similar steps, we have this generic formula for taking p p chocolates from a line of n n while keeping at least two chocolates in-between is: ( ( p + 1 n p 2 ( p 1 ) ) ) = ( n 2 p + 2 p ) \boxed{\Big(\!\!\Big(\begin{matrix}p+1\\n-p-2(p-1)\end{matrix}\Big)\!\!\Big)={n-2p+2 \choose p}}


Now, when the chocolates are in circles:

First, pick up on chocolate (30 ways to do that). You can pick up the remaining 5 chocolates from 30 1 2 2 = 25 30-1-2-2=25 possible places, as you cannot take the first chocolate again, nor the 2 × 2 2\times2 chocolates on each of its sides.

From the first part here, we now that there is ( 25 2 5 + 2 5 ) = ( 17 5 ) = 6 188 {25-2·5+2 \choose 5}={17 \choose 5}=6'188 ways to pick 5 chocolates from 25 with at least 2 between them. We have then 30 6 188 30·6'188 ways to pick 6 chocolates while deciding which one should be considered as the first one . But for all of the 6 choosen chocolates, each can be picked as first one , and therefore we have counted every possibility to pick up the chocolates 6 times. We should then divide our result by 6.

Answer is 30 6 188 6 = 3 0 940 \dfrac{30·6'188}{6}=\boxed{30'940} .


Generic formula for p p chocolates picked from n n displayed in circle, while leaving at least k k chocolates in-between is n p ( n 1 k p p 1 ) \frac{n}{p}{n-1-k·p \choose p-1}

wow that's great.....really awesome.....

Ujjwal Mani Tripathi - 4 years, 3 months ago
Ashish Gupta
Feb 12, 2017

great use of gap method..

Ujjwal Mani Tripathi - 4 years, 3 months ago
Ankit Kumar Jain
Feb 27, 2017

We generalize this for n n chocolates and atleast p p chocolates gap and choosing r r chocolates.

We firstly choose a chocolate ,

Now , call the number of chocolates between 1 s t , 2 n d 1^{st} , 2^{nd} chosen chocolates as a 1 a_1 , similarly between 2 n d , 3 r d 2^{nd} , 3^{rd} as a 2 a_2 , similarly define a i a_i , where i ( 1 , 2 , 3 r 1 ) i \in (1 , 2 , 3 \cdot \cdot \cdot r - 1) , a r a_r is the number of chocolates between r t h , 1 s t r^{th} , 1^{st} chosen chocolates.

Now , we want that a 1 + a 2 + a 3 + + a r = n r a_1 + a_2 + a_3 + \cdot \cdot \cdot + a_r = n - r because there are n r n - r chocolates remaining . With the condition that a i a_i , where i ( 1 , 2 , 3 r ) p i \in (1 , 2 , 3 \cdot \cdot \cdot r) \geq p because we desire p p chocolates between any two chosen chocolates.

By Stars And Bars Theorem , we have the number of solutions to be ( n r r p + r 1 r 1 ) = ( n r p 1 r 1 ) {{n - r - rp + r - 1}\choose{r - 1}} = {{n - rp - 1}\choose{r - 1}} .

Now , for choosing the first chocolate , we have n n ways. But for any set of r r chocolates , call b 1 , b 2 , b 3 , b r b_1 , b_2 , b_3 , \cdot \cdot \cdot b_r , we are counting it r r times , as we can suppose any of the r r chocolates to be the first one.

Therefore , our final answer is ( n r p 1 r 1 ) × n r \boxed{{{n - rp - 1}\choose{r - 1}}\times{\frac{n}{r}}}

Plugging in the values n = 30 , r = 6 , p = 2 n = 30 , r = 6 , p = 2 , we get 30940 \boxed{30940} as our answer.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...