From James Bach comes a doozy on doodles:

James likes to draw doodles in the shapes of different polygons. He especially likes to doodle *self-intersecting* polygons, where the sides cross over each other. (These are distinct from the simple polygons you might have learned about in school, whose sides do not intersect each other.)

The other day, James was able to draw a self-intersecting polygon, each of whose sides intersected with exactly two other sides. Not only that, he drew a polygon with the fewest possible sides that met these criteria.

What was it, you ask? It was a pentagram, which has just five sides.

Lovely. But this got James really thinking — can you draw a polygon where each side intersects exactly *three* other sides? And if so, what is the minimum number of sides this polygon can have?

The figures above provide two ideas which led me to the solution.

On the left, notice that a hexagon has the minimum number of sides where each side intersects exactly *one* other side.

On the right, notice that three segments can intersect three other segments with two pairs of endpoints. That is, each **purple** segment intersects exactly three **cyan** segments, and each **cyan** segment intersects exactly three **purple** segments.

Combining these ideas together yields a polygon of 18 sides, where each side intersects exactly *three* other sides.

The minimum number of sides a polygon can have such that each side intersects exactly $n$ other sides is $n+3$ for even $n$.

This can be easily determined by the following.

- A side is determined by two vertices.
- Since each vertex is defined by two sides, place $\frac{n}{2}$ vertices on one region bounded by the side. This yields $n$ total sides intersecting the specified side.
- Place $\frac{n}{2} +1$ vertices on the opposite region bounded by the side. Note that if there are only $\frac{n}{2}$ vertices on the opposite region bounded by the side, there will be an even number of vertices and sides, which will not result in the desired polygon.

$2 + \frac{n}{2} +\frac{n}{2} +1 = n+3$

For odd $n$ I could not see a pattern. But I did determine that for $n = 5$, the solution is a decagon, much less than that of $n = 3$.

Notice that each pair of sides of the same color intersect each other and exactly two other pairs.

Number of Intersections for each side | Minimum number of sides |
---|---|

$1$ | $6$ |

$2$ | $5$ |

$3$ | $18$ |

$4$ | $7$ |

$5$ | $10$ |

$6$ | $9$ |

$7$ | $??$ |

$8$ | $11$ |

$...$ | $...$ |

Code can be found here.