# Dividing a rectangle into maximum number of regions using lines

At most how many regions can you divide a rectangle in using 6 lines?

I got 16.

-
How did you get 16? – Don Larynx Oct 1 '13 at 23:33
I didn't use a real method or algorithm. I just tried to use logic, so I was also wondering whether there's an easier way to do it. – David Oct 1 '13 at 23:36
1st line: Horizontal, parallel to side 2nd: Vertical 3rd: A diagonal 4th: Other diagonal 5th: Vertical through first half of rectangle 6th: Vertical through second half of rectangle Counting gets you 16. – David Oct 1 '13 at 23:40
Judging from your comment, the lines do not need to be parallel. In which case, the answer is ${ n \choose 2} + n + 1$. This is a common problem, though typically set in a circle. – Calvin Lin Oct 1 '13 at 23:43
This is OEIS A000124, where the formula is ${n+1 \choose 2}+1=22$. There is a sketch of how to derive it. – Ross Millikan Oct 2 '13 at 0:03

An easy induction argument, is to show that adding the $k+1$ line, will result in that line being cut into at most $k+1$ line segments (within the rectangle). THis is where we use the fact that they are not parallel. Each of these line segments will split 1 region apart, thereby creating at most $k+1$ more regions. You can then show that ${ n \choose 2 } + n + 1$ satisfies the initial conditions and the recurrence relation. – Calvin Lin Oct 2 '13 at 0:39