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:
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.
Why do we need the Pigeonhole Principle for this problem?
ReplyDeleteFor 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?
You need to prove that there is a REGULAR n-sided polygon all of whose vertices are blue.
DeleteAhh okay. Here is an alternate proof then (won't call it easier or harder, just different).
ReplyDeleteConsider 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.
The restriction n <> m is not required.
ReplyDelete• กำจัดขน
ReplyDelete• กระตุ้นการผลิตคอลลาเจนชูกระชับผิวหน้า (Tightening) ลบเลือนหายไปริ้วรอยช่วยทำให้ผิวเรียบเนียน
• รอยหลุมสิวตื้นขึ้นและก็รูขุมขนกระชับขึ้นผิวหน้าละเอียดและก็เรียบเนียน
• รักษาสิวอักเสบรอยแดงจากสิวหรือเส้นเลือดฝอยที่ไม่ดีเหมือนปกติ
• ลดความหมองคล้ำผิวกระจ่างขาวสวยใสดูอ่อนกว่าวัย
• กำจัดเส้นโลหิตขอดแล้วก็เส้นเลือดฝอย
• รักษาเส้นโลหิตขอดเล็กๆได้โดยไม่ต้องเสียเวล่ำเวลาผ่าตัด ไม่ต้องนอนพัก แม้กระนั้นบางทีอาจจำต้องทำต่อเนื่องกันหลายหนก็เลยจะได้ผลลัพธ์ที่ดี
เลเซอร์ขนขา
เลเซอร์รักแร้
เลเซอร์บิกินี
เลเซอร์ กำจัดขนหน้า
เลเซอร์ กำจัดขน รักแร้