Number of Regions
 

Start with an N x N square with each side divided into N equal parts
by N-1 points (vertices).

Now connect every vertex on the boundary to every other vertex by
straight line segments.

(There are 4N such vertices, and by computation 6N^2-4N+4 such line
segments if the edges of the square are counted just once each.)

This divides the square into a number of separate (convex, non-
overlapping) regions.

The question is: for N=3 how many regions are formed by the 46 lines?

If you're adventurous, solve for N=4 and N=5.

Perhaps this problem was ambiguously or incorrectly specified,
or just not number-theoretically interesting enough?

The only subtlety appears to be when three (or more) of the
line segments intersect at a common point (and the fact that
the drawn diagram gets complicated for larger N).

For N=3, since the vertical and horizontal lines that divide the
square into 9 smaller squares provide some symmetry in counting
the regions, I count:

[spoiler]4 corner squares with 32 subregions each,
4 edge squares with 42 subregions each, and
1 central square with 36 subregions,
for a total of 4x32+4x42+36 = 332 regions.

I can't guarantee my diagram.

Is there an algorithm for solving the original problem?
Since the lines all intersect at rational points, perhaps
floating point arithmetic can be avoided?
[/spoiler]

Despite your persistence, the lack of interest in
this problem is deafening, and as far as I am concerned understandable:smile:

David

I had a go but found it too difficult. I'm unable to confirm or dispute davar55's solution for N=3 and I can't even manage to draw a reliable diagram.

I must add that my own chronic inablility to make headway with this problem says nothing about its intrinsic difficulty.

[QUOTE=davar55;129235]Start with an N x N square with each side divided into N equal parts
by N-1 points (vertices).

Now connect every vertex on the boundary to every other vertex by
straight line segments.

(There are 4N such vertices, and by computation 6N^2-4N+4 such line
segments if the edges of the square are counted just once each.)

This divides the square into a number of separate (convex, non-
overlapping) regions.

The question is: for N=3 how many regions are formed by the 46 lines?

If you're adventurous, solve for N=4 and N=5.[/QUOTE]

Did I draw this right?
If so there are 88 single regions.
But are you asking that we also count the larger regions made up of more than 1 single region?

Nice diagram, but I think Davar was including
the corners as vertices (he said there were 4N of them).

Yes to the question of including the corners as vertices.
No to the counting of larger regions (at least that's what I intended).

Here's another illustration.

4 corners (32 regions each)

4 mid-sides (44 regions each)

1 centre (36 regions)

so 340 sections. All praise the mighty flood-fill tool!

N=4
 

This illustration is not the most beautiful illustration in all the Earth, but, being generated by a perl script then exported with svg, is probably correct.

Symmetry gives three kinds of distinct square - corner, edge and middle4.

4*corner(54), 8*edge(76), 4*middle(74) = 1120

Data-structure thoughts
 

N=3 coloured as to the number of sides of each region.

I suppose you have to define a Region by a list of its corners taken in clockwise order; a line will cut any Region that it intersects into two Regions, and at worst each of those regions will have one more side than the original one.

Since Regions are convex, you can print their number at their centroid without looking too ugly.

Got it working
 

It needs exact rational arithmetic, the denominators are very varied, though they tend not to get very big.


N=4 is indeed 1120 regions, and to my surprise uses nothing bigger than pentagons

N=5 is 3264 regions, including eight heptagons and 76 hexagons

N=6 is a rather ugly symmetrical mess of 6264 regions: 56 hexagons and no heptagons, and lots of the area made of triangles.

N=7 has 13968 regions, many of them really quite small: it's too big to attach here, but the 7MB large image is available as [url]http://www.chiark.greenend.org.uk/~twomack/huge_N7.png[/url].

N=8 has 22904 regions.