Friday, 4 March 2016

An interesting application of the pigeonhole principle

Question:
Suppose 2016 points of the circumference of a circle are coloured red and the remaining points are coloured blue. Given any natural number $n \geq 3$, prove that there is a regular n-sided polygon all of whose vertices are blue. (Source: INMO 2016)

Solution:
Consider a regular $(2017 \times n)$-gon on the circle, say with vertices $A_1, A_2, A_3,\dots, A_{2017 \times n}$. For each $j$, such that $1 \leq j \leq 2017$, consider the set of points $\{A_k : k \equiv j \mod 2017\}$. Note that these are the vertices of a regular $n$-gon, say $S_j$. Thus, we get 2017 regular $n$-gons: $S_1, S_2,\dots, S_{2017}$. Since there are only 2016 red points on the circumference, by pigeonhole principle there must be at least one $n$-gon among these 2017 which does not contain any red vertex. But then, all the vertices of this regular $n$-gon must be blue. Hence proved.

4 comments:

  1. Why do we need the Pigeonhole Principle for this problem?

    For any positive integer "m", even if all m points on the circumference are colored red, it still leaves an infinite set of points that are not red.

    Thus, for any n <> m, one can form an n-gon all of whose vertices are non-red.

    What am I missing?

    ReplyDelete
    Replies
    1. You need to prove that there is a REGULAR n-sided polygon all of whose vertices are blue.

      Delete
  2. Ahh okay. Here is an alternate proof then (won't call it easier or harder, just different).

    Consider a unit circle on which n points are colored red at angular positions given by θ_i, 1 <= i <= n. For any m <> n, consider the following question:

    Mark all the m roots of unity on another unit circle superimposed on the first one. Can one always find an angle φ such that when this circle is rotated counterclockwise by φ, none of the roots coincide with any of the n red points on the circle underneath?

    Proof: The angular positions of the m roots of unity are given by 2π/k, where 1 <= k <= m. Rotating the frame by φ counterclockwise brings these roots to angular positions 2π/k + φ.

    We need to show that we can always find a φ such that
    φ <> θ_i - 2π/k

    But that is trivial: for any choice of θ_i and n, the set represented by the angles θ_i - 2π/k is strictly finite, while there are infinitely many angles round the unit circle. QED.

    ReplyDelete
  3. The restriction n <> m is not required.

    ReplyDelete