Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 IMO Problems/Problem 2"

(Created page with "2. Let <math>n\ge3</math> and consider a set <math>E</math> of <math>2n-1</math> distinct points on a circle. Suppose that exactly <math>k</math> of these points are to be col...")
 
 
Line 1: Line 1:
−
2. Let <math>n\ge3</math> and consider a set <math>E</math> of <math>2n-1</math> distinct points on a circle. Suppose that exactly <math>k</math> of these points are to be colored black. Such a coloring is “good” if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly <math>n</math> points from <math>E</math>. Find the smallest value of <math>k</math> so that every such coloring of <math>k</math> points of <math>E</math> is good.
+
==Problem==
 +
Let <math>n\ge3</math> and consider a set <math>E</math> of <math>2n-1</math> distinct points on a circle. Suppose that exactly <math>k</math> of these points are to be colored black. Such a coloring is “good” if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly <math>n</math> points from <math>E</math>. Find the smallest value of <math>k</math> so that every such coloring of <math>k</math> points of <math>E</math> is good.
 +
 
 +
==Solution==
 +
We form a graph on the <math>2n-1</math> points by connecting two of these points iff one of the arcs they determine has exactly <math>n</math> points in its interior. If <math>3\not|2n-1</math>, then this graph is a cycle, and the question becomes: what's the minimal <math>k</math> s.t. whenever we color <math>k</math> vertices of a cycle of length <math>2n-1</math>, there are two adjacent colored vertices? Obviously, the answer is <math>k=n</math>. On the other hand, when <math>3|2n-1</math>, the graph is a disjoint union of three cycles of length <math>\frac{2n+1}3</math>, and the answer will be, in this case, <math>3\cdot\left\lfloor\frac{2n-1}6\right\rfloor+1</math>.
 +
 
 +
This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [https://aops.com/community/p366558]
 +
 
 +
== See Also == {{IMO box|year=1990|num-b=1|num-a=3}}

Latest revision as of 13:37, 30 January 2021

Problem

Let $n\ge3$ and consider a set $E$ of $2n-1$ distinct points on a circle. Suppose that exactly $k$ of these points are to be colored black. Such a coloring is “good” if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $n$ points from $E$. Find the smallest value of $k$ so that every such coloring of $k$ points of $E$ is good.

Solution

We form a graph on the $2n-1$ points by connecting two of these points iff one of the arcs they determine has exactly $n$ points in its interior. If $3\not|2n-1$, then this graph is a cycle, and the question becomes: what's the minimal $k$ s.t. whenever we color $k$ vertices of a cycle of length $2n-1$, there are two adjacent colored vertices? Obviously, the answer is $k=n$. On the other hand, when $3|2n-1$, the graph is a disjoint union of three cycles of length $\frac{2n+1}3$, and the answer will be, in this case, $3\cdot\left\lfloor\frac{2n-1}6\right\rfloor+1$.

This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

See Also

1990 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_IMO_Problems/Problem_2&oldid=144072"