There is convex $2009$-gon on the plane. a) Find the greatest number of vertices of $2009$-gon such that no two forms the side of the polygon. b) Find the greatest number of vertices of $2009$-gon such that among any three of them there is one that is not connected with other two by side.
Problem
Source:
Tags:
munygrubber
21.01.2011 05:24
(I am not counting rotations.) A. as long as no two are next to each other, it is allowed. So, we can use every other one. 2009/2 = 1004.5 BEcause we can't have half a point (and it would cause two to be next to each other), the answer is 1004. B. It's confusing. I think it's 1339 because of similar logic to part A.
math_explorer
22.01.2011 09:50
Rigorously: There are 2009 triplets of consecutive vertices. Each time we select one additional vertex, we increase the number of selected vertices of 3 triplets by 1 each. In each triplet, we can select at most 2 vertices, so the total number of increases is at most 4018. Therefore we cannot select 1340 or more vertices. 1339 is of course possible.