TIFR CSE 2020 | Part A | Question: 6

Question

What is the maximum number of regions that the plane $\mathbb{R}^{2}$ can be partitioned into using $10$ lines?

• A. $25$
• B. $50$
• C. $55$
• D. $56$
• E. $1024$

Hint: Let $A(n)$ be the maximum number of partitions that can be made by $n$ lines. Observe that $A(0) = 1, A(2) = 2, A(2) = 4$ etc. Come up with a recurrence equation for $A(n)$.

Answer 1

The recurrence is given by $A(n)=A(n-1)+n$. Each new $n^{th}$ line drawn is creating $n$ new partitions. While creating partitions,draw the new line in such a way that it cuts the all the previously drawn $n-1$ lines, then the $n^{th}$ line will create $n$ new partitions and previous $A(n-1)$ partitions will remain the same.

Then $A(3)=A(2)+3=4+3=7$

$A(4)=A(3)+4=7+4=11$

$\vdots$                         $\vdots$                        $\vdots$

$A(10)=A(9)+10=46+10=\textbf{56}$

P.S. Try dividing $\mathbb{R}^{2}$ by $n=3 ,n=4,n=5$ lines using the method above, you'll get the idea.