retagged by
808 views
2 votes
2 votes

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

  1. $25$
  2. $50$
  3. $55$
  4. $56$
  5. $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)$.

retagged by

1 Answer

5 votes
5 votes
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.
Answer:

Related questions

3 votes
3 votes
2 answers
1
admin asked Feb 10, 2020
774 views
The sequence $s_{0},s_{1},\dots , s_{9}$ is defined as follows:$s_{0} = s_{1} + 1$$2s_{i} = s_{i-1} + s_{i+1} + 2 \text{ for } 1 \leq i \leq 8$$2s_{9} = s_{8} + 2$What is...
1 votes
1 votes
1 answer
4
admin asked Feb 10, 2020
649 views
What is the area of the largest rectangle that can be inscribed in a circle of radius $R$?$R^{2}/2$$\pi \times R^{2}/2$$R^{2}$$2R^{2}$None of the above