Interior regions of a convex $n$ gon

For discussing Olympiad Level Combinatorics problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Interior regions of a convex $n$ gon

Unread post by tanmoy » Mon Jan 12, 2015 4:54 pm

For $n\geq 4$,let $r(n)$ denote the number of interior regions of a convex $n-$ gon divided by all its diagonals if no three diagonals are concurrent within the $n-$ gon.For example,suppose,$n=4$ and $ABCD$ is a quadrilateral.Diagonals $AC$ and $BD$ intersect at $O$.Then,the number of regions divided by the diagonals is $4$.($AOB,BOC,COD,DOA$).Prove that,$r(n)=\binom{n}{4}+\binom{n-1}{2}$.
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Interior regions of a convex $n$ gon

Unread post by rah4927 » Sat Feb 07, 2015 10:01 pm

Every time we draw a new diagonal,it creates one new region,and every time it intersects another previously drawn diagonal,it creates one more region.Hence,

Total number of regions if no 3 intersect at a point=number of intersections of two diagonals+number of diagonals+1
Last edited by rah4927 on Sun Feb 08, 2015 12:21 pm, edited 1 time in total.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Interior regions of a convex $n$ gon

Unread post by tanmoy » Sun Feb 08, 2015 12:27 pm

rah4927 wrote:Every time we draw a new diagonal,it creates one new region,and every time it intersects another previously drawn diagonal,it creates one more region.Hence,

Total number of regions if no 3 intersect at a point=number of intersections of two diagonals+number of diagonals
You have got a little mistake.We start with one part,the $n$ gon.One part is added for each diagonal,and one more part is added for each intersection point of two diagonals.$\therefore$ The total number of regions$=1+$number of intersections of two diagonals$+$number of diagonals$=1+\binom{n}{4}+\frac{n(n-3)}{2}=\binom{n}{4}+\binom{n-1}{2}$.
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Interior regions of a convex $n$ gon

Unread post by rah4927 » Sun Feb 08, 2015 12:34 pm

tanmoy wrote:
rah4927 wrote:Every time we draw a new diagonal,it creates one new region,and every time it intersects another previously drawn diagonal,it creates one more region.Hence,

Total number of regions if no 3 intersect at a point=number of intersections of two diagonals+number of diagonals
You have got a little mistake.We start with one part,the $n$ gon.One part is added for each diagonal,and one more part is added for each intersection point of two diagonals.$\therefore$ The total number of regions$=1+$number of intersections of two diagonals$+$number of diagonals$=1+\binom{n}{4}+\frac{n(n-3)}{2}=\binom{n}{4}+\binom{n-1}{2}$.
Yes,my original solution contained a mistake.I have rectified it.Thanks.

Post Reply