Intersecting 17-sided polygons

Suppose A = A 1 A 2 . . . A 17 A=A_1A_2...A_{17} and B = B 1 B 2 . . . B 17 B=B_1B_2...B_{17} are two polygons, possibly self-intersecting. Suppose no three out of 34 34 vertices of A A and B B lie on the same straight line. Find the largest possible number of intersections of A A and B B .

Details and assumptions

You should not count any self intersections of the polygons.


The answer is 272.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Calvin Lin Staff
May 13, 2014

First, note that each side of A A can intersect with no more that 16 16 sides of B B . Indeed, consider the line that contains it. It divides the plane into two parts. If B i B i + 1 B_iB_{i+1} intersects it for all i i from 1 1 to 16 16 , then B 1 B_1 and B 17 B_{17} are in the same half-plane so B 17 B 1 B_{17}B_1 cannot intersect it. Therefore, the total number of intersections can be at most 16 × 17 = 272. 16 \times 17 = 272.

To construct an example with 272 272 intersections, consider 34 34 points uniformly distributed on the unit circle, with angles to the x x -axis being 2 π k 34 , \frac{2\pi k}{34,} for k = 0 , 1 , . . . , 33 k=0,1,...,33 . We will call these points P k . P_k.

The heptadecagons A A and B B will be "stars", with A A using even k k and B B using odd. Specifically, the edge from A i A_i to A i + 1 A_{i+1} or from A 17 A_{17} to A 1 A_1 is the segment from P k P_k to P k + 16 ( m o d 34 ) P_{k + 16 \pmod{34}} for some k k . Then B B is obtained from A A by rotating at an angle of 2 π 34 \frac{2 \pi}{34} about the origin. The picture below illustrates this construction with pentagons instead of heptadecagons.

Note that all edges of A A and B B are chords that are "close" to a diameter. One can see that for a given edge of A A exactly one edge of B B does not intersect it: the one that is obtained from it by the symmetry around the origin. For example, for the chord A 1 A 2 A_1A_2 that connects points P 0 P_0 and P 16 , P_{16}, at most one of the endpoints of an edge of B B can be among P 1 , P 3 , . . . , P 15 . P_1,P_3,...,P_{15}. If neither are there, then the only way to have a chord this close to the diameter using the points P 17 , . . . , P 33 P_{17},...,P_{33} is to use P 17 P_{17} and P 33 . P_{33}.

So, the final answer is 272 272 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...