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?
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.
wow that's great.....really awesome.....
great use of gap method..
We generalize this for n chocolates and atleast p chocolates gap and choosing r chocolates.
We firstly choose a chocolate ,
Now , call the number of chocolates between 1 s t , 2 n d chosen chocolates as a 1 , similarly between 2 n d , 3 r d as a 2 , similarly define a i , where i ∈ ( 1 , 2 , 3 ⋅ ⋅ ⋅ r − 1 ) , a r is the number of chocolates between r t h , 1 s t chosen chocolates.
Now , we want that a 1 + a 2 + a 3 + ⋅ ⋅ ⋅ + a r = n − r because there are n − r chocolates remaining . With the condition that a i , where i ∈ ( 1 , 2 , 3 ⋅ ⋅ ⋅ r ) ≥ p because we desire p chocolates between any two chosen chocolates.
By Stars And Bars Theorem , we have the number of solutions to be ( r − 1 n − r − r p + r − 1 ) = ( r − 1 n − r p − 1 ) .
Now , for choosing the first chocolate , we have n ways. But for any set of r chocolates , call b 1 , b 2 , b 3 , ⋅ ⋅ ⋅ b r , we are counting it r times , as we can suppose any of the r chocolates to be the first one.
Therefore , our final answer is ( r − 1 n − r p − 1 ) × r n
Plugging in the values n = 3 0 , r = 6 , p = 2 , we get 3 0 9 4 0 as our answer.
@Laurent Shorts @starwar clone @Ashish Gupta Please comment.
Problem Loading...
Note Loading...
Set Loading...
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 3 0 − 1 6 = 1 4 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 1 4 ) ) = ( 1 4 7 + 1 4 − 1 ) = ( 1 4 2 0 ) = 3 8 ′ 7 6 0 ways, by stars and bars , to do that.
With similar steps, we have this generic formula for taking p chocolates from a line of n while keeping at least two chocolates in-between is: ( ( p + 1 n − p − 2 ( p − 1 ) ) ) = ( p n − 2 p + 2 )
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 3 0 − 1 − 2 − 2 = 2 5 possible places, as you cannot take the first chocolate again, nor the 2 × 2 chocolates on each of its sides.
From the first part here, we now that there is ( 5 2 5 − 2 ⋅ 5 + 2 ) = ( 5 1 7 ) = 6 ′ 1 8 8 ways to pick 5 chocolates from 25 with at least 2 between them. We have then 3 0 ⋅ 6 ′ 1 8 8 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 6 3 0 ⋅ 6 ′ 1 8 8 = 3 0 ′ 9 4 0 .
Generic formula for p chocolates picked from n displayed in circle, while leaving at least k chocolates in-between is p n ( p − 1 n − 1 − k ⋅ p )