All-Russian Olympiad Problem 2
A regular
2
0
1
2
-gon is inscribed in a circle. Find the maximal
k
such that we can choose
k
vertices from given
2
0
1
2
and construct a convex
k
-gon without parallel sides.This problem is part of
this set
.
The answer is 1509.
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.
2 solutions
Divide the regular 2012-gon into two equivalent semi circles, each part has: 2 2 0 1 2 = 1 0 0 6 edges, choose a semi circle being a part of the result convex k-gon without parallel sides. In the remaining semi circle, connecting individually two edges to get one edge of the result k-gon. Finally it makes k-gon with: 1 0 0 6 + 2 1 0 0 6 = 1 5 0 9 edges.
I went for the same thing but I realised that it would be difficult to prove that no better solution exists. A proof would be helpful.
Log in to reply
There's actually a very simple way to prove that no better solution exists, using the ideas already presented in this problem. When you've found the construction to such a problem, try and see what restrictions / underlying principles are helping you determine the setup. In this case, we care about the slope of the lines, and also the number of points between the vertices.
As such, this leads us to define the following: For every pair of points, we let ( θ , n ) denote the angle of the line between them, and the number of pairs of points between them (such that for consecutive pairs, we have n = 2 ). Then, from all of these ( 2 2 0 1 2 ) pairs, we want to pick distinct θ 's such that ∑ ( n − 1 ) = 2 0 1 2 .
From here, it's almost obvious how to proceed (esp when you think about how you constructed the examples). We can show that we can pick at most 1 0 0 6 pairs where n = 2 , and then at most 2 1 0 0 6 pairs where n = 3 . Hence, this gives us the maximum possible. It remains to show that this construction can be achieved.
First note that only odd regular n-gons will not have parallel sides. So it will be a regular 503-gon (2012=4*503).
But the problem does not require it to be regular.
Maximum sides=number of vertices=2012.
If we want to have maximum sides, we can miss one vertex in every four vertices.
This will give us one side less in every four sides.
So 2012/4=503. So we miss 503 vertices so 503 sides. Thus we are left with 2012 - 503=1509 sides.
Thus it is 1 5 0 9 − g o n .