Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

I got 16.

share|improve this question
    
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
2  
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
2  
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

1 Answer 1

Well, you can get more than 16, And apparently, 22 (image below) is the maximum number. I'd love to see Calvin Lin's proof..

enter image description here

Of course, if the lines don't have to be straight, you can go much higher..

share|improve this answer
1  
You can get 22. Don't have any parallel lines. –  Calvin Lin Oct 1 '13 at 23:44
    
Thanks, especially for the formula. –  David Oct 1 '13 at 23:47
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.