We draw $n$ convex quadrilaterals in the plane. They divide the plane into regions (one of the regions is infinite). Determine the maximal possible number of these regions.
Problem
Source: Baltic Way 2002
Tags: combinatorics proposed, combinatorics
dyta
13.11.2010 16:49
WakeUp wrote: We draw $n$ convex quadrilaterals in the plane. They divide the plane into regions (one of the regions is infinite). Determine the maximal possible number of these regions.
I think I can be solved by induction. The result is $2^n$.
chaotic_iak
14.11.2010 02:46
No, obviously it isn't. With 2 quadrilaterals, there can be up to 10 regions (make 8-pointed star from the two quadrilaterals).
JacobGuo
14.11.2010 03:50
He has the right idea though
it is not hard to prove that it is 2 more than the maximum number of intersection points, which can be proven inductively to be $2^n$, so it is $2^n+2$
chaotic_iak
14.11.2010 04:38
I found these: 0 quadrilaterals = 1 region 1 quadrilateral = 2 regions 2 quadrilaterals = 10 regions 3 quadrilaterals = 26 regions...?
geomath
24.03.2017 08:46
This numbers is equivalient to the sequence \[a_n=2^{n+2}-6 \qquad for \;\; all\;\; n\ge 1\]
Tintarn
12.09.2018 10:51
geomath wrote: This numbers is equivalient to the sequence \[a_n=2^{n+2}-6 \qquad for \;\; all\;\; n\ge 1\] Maybe that's true for the first few numbers but certainly not beyond. The true answer is $a_n=4n^4-4n+2=(2n-1)^2+1$. It clearly suffices to prove that $a_{n+1}-a_n \le 8n$. But this is clear since each of the four new edges can intersect at most $2n$ of the previously drawn edges and hence "create" at most $2n$ new regions. Finally, it is easy to see that drawing squares slightly rotated around their center achieves this number.