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.
(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 |
re: First speculation
