All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes
Cutting planes with polygons (Posted on 2006-09-06) Difficulty: 3 of 5
Into how many regions can you partition the plane with m n-sided regular polygons?

For example, with two squares you can achieve up to 10 regions by choosing the right size and position of your squares.

See The Solution Submitted by JLo    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: First speculation | Comment 2 of 17 |
(In reply to First speculation by vswitchs)

The formula given below is wrong [note added later]:

If indeed the maximum can be achieved by equal-sized (congruent) polygons with the same center, then I would think that the number of regions for m+1 polygons can be determined from the number for m regions.

Each generation (m polygons, m+1 polygons, etc.) has a completely inner region, a completely outer region, and some border regions.  When going from one generation to the next, n regions are added by being cut from the former outer region and n from the former inner region, and each of the border regions is divided into 2. And of course there are the inner and outer regions remaining.

This leads to the recursion r(m+1,n) = 2n + 2(r(m,n)-2) + 2
 = 2(r(m,n) + n - 1)

With one polygon, of course, there are 2 regions.

The recursion formula gives

 m \ n 4      5      6      7      8
 1     2      2      2      2      2
 2     10     12     14     16     18
 3     26     32     38     44     50
 4     58     72     86     100    114
 5     122    152    182    212    242
 6     250    312    374    436    498
 7     506    632    758    884    1010
 8     1018   1272   1526   1780   2034
 9     2042   2552   3062   3572   4082
 10    4090   5112   6134   7156   8178

so with 3 squares of the same size with the same center you'd get 26 regions.

Later note:

The recursion is wrong.  Some border regions escape being split by a newly added polygon.

 

Edited on September 6, 2006, 2:34 pm

Edited on September 6, 2006, 2:35 pm

Edited on September 6, 2006, 4:13 pm
  Posted by Charlie on 2006-09-06 14:20:26

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information