Suppose $2016$ points of the circumference of a circle are colored red and the remaining points are colored blue . Given any natural number $n\ge 3$, prove that there is a regular $n$-sided polygon all of whose vertices are blue.
Problem
Source: INMO 2016 Problem 4
Tags: combinatorics, combinatorics proposed
17.01.2016 15:11
17.01.2016 15:44
Here is a quite simple solution:Let $\mathcal{P}$ be a regular polygon with $n$ vertices(all vertices are on the given circle).If $M(\mathcal{P})$ represents the set of all red vertices of $\mathcal{P}$,note that $|\cup_{\mathcal{P}}M(\mathcal{P})|=2016$,so at least one polygon has all vertices blue.(that's because $2016$ is a finite number,and two distinct regular polygons don't share any common vertex)
17.01.2016 15:49
Probably same as above, but I will post my idea anyway.... Take any polygon, and keep rotating it. Finitely many red points, infinitely many polygons, and so done.
17.01.2016 15:49
Let $O$ be center of the circle. Denote the 2016 poins by $A_1,A_2,...,A_{2016}$ Denote by $\angle XYZ$ directed angle. Fix $n$, and consider set $S$ of all directed angles $\angle A_1OA_i$ mod $\frac{2\pi}{n}$ where $1 \leq i \leq 2016$ That set is indeed finite, so take some $0 < \alpha < \frac{2\pi}{n}, \alpha \notin S$. Let $G$ be set of all points $X$ on circumcircle such that $\angle A_1OX =\alpha \pmod{\frac{2\pi}{n}}$. Points in $G$ are vertices of a regular n-gon, and because $\angle A_1OX \neq \angle A_1OA_i$, $\forall 1 \leq i \leq 2016$ and $\forall X \in G$ we conclude that all points in $G$ are blue.
17.01.2016 19:36
My idea is to use induction on the number of red points and then argue simply by rotating using extremal principle (vertex of polygon closest to red point)
17.01.2016 22:47
17.01.2016 23:51
Given any $n$-sided regular polygon, there are at most $2016$ different polygons with at least one red vertex. However, there are an infinite number of ways to choose the polygon, so just choose a polygon randomly and you have a non-zero chance of getting one with all blue points
18.01.2016 02:42
Well, choose a point and draw a regular polygon of $n$ sides, now choose the adjacent side of the regular polygon and choose $2017$ points in that arc, now starting with each of those $2017$ points construct regular polygons, now by PHP we can note there exists one polygon all blue..... Or another better way is consider a regular $n$ gon........rotate it by some small angle $2016$ times......again by PHP we get the result......... Rotation trivializes the problem to a large extent..........
20.01.2016 11:51
I do think writing it combinatorially is a bit hard and if not then a bit time consuming and unnecessarily long. Post #7 gives a nice way to write this up.
20.01.2016 12:29
An easy problem but it is difficult to write a concise and clear proof which is why I'll probably lose a few marks although my proof was essentially correct. @anantmudgal09's idea of using roots of unity is amazing! What is the motivation for using this as a method of proof?
20.01.2016 12:52
hi I too have done 4 AM
20.01.2016 12:54
fifth one is part done. I mean 4.5
20.01.2016 14:12
darthsid wrote: An easy problem but it is difficult to write a concise and clear proof which is why I'll probably lose a few marks although my proof was essentially correct. @anantmudgal09's idea of using roots of unity is amazing! What is the motivation for using this as a method of proof? Well, the motivation is quite like this: You see the problem and how ridiculous the statement looks, other than $2016$ marked ones, we have infinitely many!!! That's to say that it has to be easy to solve but hard to write. Now, if you start writing combinatorially, it gets messy and a bit case prone. So, instead, ask this: What exactly is a regular $n$ gon? And what exactly are points so special for? This makes us suspect that we should see is a bit analytically and consider the Cartesian plane. But then again, Cartesian plane basically sucks for a regular $n$ gon so something better,...l, the Complex Plane!!! Now, see the points as complex numbers as they are then easier to interpret and the solution is natural. Of course, if you are a bit familiar with probabilistic/ analytic/algebraic methods in combinatorics, it see very easy to motivate this line of attack. The other combinatorial approaches are nice. I had say induction with extremely principle is the finest and nicest way to write in case this solution doesn't come. Else, it's pretty hard to write. What I liked the most was that this has a funny probabilistic solution. I was planning to nail it in a similar fashion as USAMO 2012/2 or Tournament of Towns Fall A level 2012/7 By using some probabilistic arguments so to make it easier by that, I considered complex number and saw that oh... It's being dumb anyways... But, I liked how this was a bit troll-ish for a cute combinatorics.
22.01.2016 05:01
Actually, what i did was the following: i proved that a regular n-gon can be determined by the angle it subtends at the center. Using this, i created n "sweeper arms", at a distance 2π/n from each other. Then, keeping the sweeper arm at the 1st point and rotating it slowly, anticlockwise, keep striking out the red points that have appeared at the ends of a sweeper arm. We will do the rotation only until 2π/n, so no red point will be double counted thus the striking is valid. But, in that 2π/n angle, we have infinite points, hence we can rotate the arms slowly enough, and no of red points cannot keep decreasing. Since they are finite, we are done.
22.01.2016 06:52
anantmudgal09 wrote: I do think writing it combinatorially is a bit hard and if not then a bit time consuming and unnecessarily long. Post #7 gives a nice way to write this up. I don't think so.......(tell me what is incomplete in this....!) Consider a point in the circle say $V$, now construct a regular $n$-gon with $V$, as one of its vertex, rotate the regular $n$-gon with an angle sufficiently small $2016$ times ($< \frac{360}{n}$), so now we have $2017$ new positions of the polygon(of which no two polygonal positions share same points since if it shares one common point then all points will be same as they are $\frac{360}{n}$ angular distance apart from each other), and thus we have $2016$ red points so there exists a polygonal position with no red points by PHP.
22.01.2016 06:56
anantmudgal09 wrote:
This is a good way to escape a long (not that long....), solution......
22.01.2016 07:43
Can someone please analyse how much I can get. P1: Got completely correct. P2: I did part (II) correct. But in part (I) i got: if $a=b$ then $a=c$ or $c(c^2-a^2)+a^2(a-c)=0$ which i erroneously simplified to $c(c+a)+a^2=0$ and then stated the later was impossible. Therefore $a=b=c$ must hold. P3: My solution to 1st part: $T(T(T(n)))<T(n)$ unless $T(n)=1or2$ Therefore we must have $T^k(n)=1or2$ for some $k\in\mathbb{N}$ If $T^k(n)=2$ then $T^{k+1}(n)=1$ and we're done. Didn't get time for the 2nd part. P4: Very trivial problem. Got it correct. P5: Simplifying the initial conditions, i showed that we needed to prove $BD^2=[ABC]$ and then did a 2 page unsuccessful Trig Bash. (I didn't know Cono Sur's Theorem) P6: Showed that $a_1$ and $d$ (common difference of the A.P) are rational. But couldn't go much further ahead.
22.01.2016 08:45
Its completely fine to be excited and curious to know how you fared in INMO $2016$, this is not an appropriate place to ask this question...... Try posting it in the Post INMO group.....
24.01.2016 16:56
Guys, i divided the circle in n parts and then took the first points of each arc, then the second points of each arc and so on... till i get 2017 polygons. Then it is simple PHP. Basically, just another method of constructing 2017 polygons.
25.01.2016 15:47
Practically those 2016 points would not be visible at all
25.01.2016 15:49
It can be proved for any $n$ number of points.
26.01.2016 20:43
My solution is same as $viswanath$
03.02.2016 19:07
Well, this is true even when a countable number of points on the circumference of the circle is colored red.
11.02.2016 09:43
hi devesh marvellous poem ! That is the spirit
09.03.2016 08:07
standard
26.08.2016 09:01
I do it checking the existence of such configurations , or a backtrack fellowship.
Attachments:

13.01.2017 12:09
Hey guys where can I find these type of problems
13.01.2017 12:48
Wasn't this one (very) trivial?
13.01.2017 13:42
TheOneYouWant wrote: Actually, what i did was the following: i proved that a regular n-gon can be determined by the angle it subtends at the center. Using this, i created n "sweeper arms", at a distance 2π/n from each other. Then, keeping the sweeper arm at the 1st point and rotating it slowly, anticlockwise, keep striking out the red points that have appeared at the ends of a sweeper arm. We will do the rotation only until 2π/n, so no red point will be double counted thus the striking is valid. Pretty much my solution ! But, in that 2π/n angle, we have infinite points, hence we can rotate the arms slowly enough, and no of red points cannot keep decreasing. Since they are finite, we are done.
25.01.2017 18:53
Place the polygon such that one of the vertex lies on one of the red points. Then keep rotating the polygon. Coincidence of points may take place a maximum of $2016n$ times. But there are infinitely many blue points. This proves the result.
31.12.2017 11:43
A simple proof: Consider any regular $n$-gon on any circle, and join its vertices to the center. You will thus obtain $n$ lines if $n$ is odd, otherwise $\frac{n}{2}$ lines. Call this system of $n$ $\left( or \frac{n}{2} \right)$ lines the $n-skeleton$ of the $n$-gon. For instance, the $4-skeleton$ would be 2 perpendicular lines passing through the center of the circle. The red lines in the figure represent a $4-skeleton$. [Note that 2 $n-skeletons$ on a circle are distinct if they have at least one different vertex. Since there exist infinitely many points on the circumference of a circle, hence there exist infinitely many distinct $n-skeletons$ on a given circle. ] [asy][asy] pair A=origin, B=(20,0), C=(0,20), D=(-20,0), E=(0,-20) ; dot(B); dot(C); dot(D); dot(E); draw(B--D, red); draw(C--E, red); draw(Circle((0,0),20)); dot(A); [/asy][/asy] Now, back to our given circle, we want to construct a regular $n$-gon all of whose vertices are blue. Construct $2017$ distinct $n-skeletons$. Since we have 2016 red points, at least one of these $skeletons$ would contain no red points, which is the one we desire.
23.01.2019 14:07