Don't Try Counting one by one

Suppose we have a regular 28 28 -gon, and we want to make a decagon ( 10 10 -gon) inside this polygon by joining vertices of this 28 28 -gon such that no side of decagon and 28 28 -gon should be common.

Find the number of such decagons possible.


This can be solved by many ways.Try to find out the shorter and elegant solution.


The answer is 68068.

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.

2 solutions

Vishnu Bhagyanath
Mar 23, 2016

Consider the general case for an n-gon \text{n-gon} creating an r-gon \text{r-gon} . Essentially, we need to choose r r points from the n n vertices such that no two vertices are adjacent. First assume the 1 st 1^{\text{st}} vertex isn't a part of this r-gon \text{r-gon} . Then, the n th n^{\text{th}} vertex can be a part of this r-gon \text{r-gon} . Imagine removing exactly r r points from the n-gon \text{n-gon} and choosing r r points from the resulting figure. Notice that there may or may not be adjacent vertices in the produced figure. But if we reinsert these r r blocks into the spaces where adjacent blocks are chosen, we get the n-gon \text{n-gon} again but such that none of the two points are ever adjacent. So there will be ( n r r ) \binom{n-r}{r} to choose such shapes.

Similarly consider the case when the 1 s t 1^{st} vertex is a part of the r-gon \text{r-gon} ,then the n th n^{\text{th}} vertex cannot be a part of this r-gon \text{r-gon} . So there will be ( n r 1 r 1 ) \binom{n-r-1}{r-1} ways of choosing the points.

If S ( n , r ) S_{(n,r)} denotes the number of ways to get an r-gon \text{r-gon} from an n-gon \text{n-gon} such that no two vertices are adjacent from the original n-gon \text{n-gon} , then S ( n , r ) = ( n r r ) + ( n r 1 r 1 ) S_{(n,r)}=\binom{n-r}{r}+\binom{n-r-1}{r-1}

Substituting n = 28 , r = 10 n=28,r=10 , we get S ( 28 , 10 ) = 68068 S_{(28,10)} = 68068 .

Gautam Sharma
Mar 24, 2016

Let's do this question using gap method. For understanding see my solution in this

So Let us fix 18 18 points(vertices of 28-gon) in a straight line(see above link for reference) .Now there are total 19 spaces which we can choose as vertices(including first and last). If any 10 of these 19 places are chosen then, no one will be adjacent. This can be done in 19 C 10 ^{19}C_{10} ways.

But if we choose the first and last position and then join the line back to form the polygon then these two points will adjacent.This case is possible by 17 C 8 ^{17}C_{8} ways (17 places left and 8 more vertices to be chosen because two have been chosen before i.e first and last).

Hence 19 C 10 ^{19}C_{10} - 17 C 8 = 68068 ^{17}C_{8}= \boxed{68068} .

Moderator note:

Well written and clearly explained!

Can u tell me why you have subtracted in the last step ? I'm extremely weak at combinatorics.

Aditya Kumar - 5 years, 2 months ago

Log in to reply

Look when we have chosen first and last place and then join them back to form polygon then they will be adjacent and we do not want this case.So i have subtracted total no. of different combination of this case from total.

Gautam Sharma - 5 years, 2 months ago

Log in to reply

Ooh I didn't think of that. Thanks.

Aditya Kumar - 5 years, 2 months ago

Sir why do you fix 18 points of an 28 Gon polynomial.

Rishabh Deep Singh - 5 years, 2 months ago

Log in to reply

Lol i m not 'Sir' i m younger than you!! See we have to select 10 vertices to create a decagon.So we fixed 28-10=18 points and remaining 10 vertices we will select by gap method. Pls reply if u still have a doubt.

Gautam Sharma - 5 years, 2 months ago

Log in to reply

I got it Thanks you should mention this in your solution also.

Anyways Thanks a lot.

Rishabh Deep Singh - 5 years, 2 months ago

Log in to reply

@Rishabh Deep Singh He's also giving JEE 2016(might come AIR 1).

Aditya Kumar - 5 years, 2 months ago

Log in to reply

@Aditya Kumar Who is also giving JEE also.

Rishabh Deep Singh - 5 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...