Difference between revisions of "2016 IMO Problems/Problem 6"
(→Solution) |
|||
Line 9: | Line 9: | ||
==Solution== | ==Solution== | ||
{{solution}} | {{solution}} | ||
+ | |||
+ | Beautiful problem. Despite being placed a bit higher in both the Shortlist and the actual exam, kudos to the proposer for involving combi, geo and NT in one single problem. Anyway, here's my solution: Color each of the <math>2n</math> endpoints [color=#00f]blue[/color] and all the <math>\binom{n}{2}</math> intersection points [color=#f00]red[/color]. Join the blue points with a smooth curve <math>\cal{C}</math> such that none of the line segments intersect <math>\cal{C}</math> more than twice (i.e. all the red points lie inside <math>\cal{C}</math>). Call the [i]inverse[/i] of a blue point <math>\cal{B}</math>, the point which lies on both <math>\cal{C}</math> and the line segment through <math>\cal{B}</math>, and denote it by <math>\cal{B'}</math>. Also, we define the [i]neighbor[/i] of a blue point <math>\cal{B}</math> as the point which lies on the right of <math>\cal{B}</math> (if we stand facing the inverse of <math>\cal{B}</math>) and nearest to it. Finally, if Geoff (from now on we) can place a frog (in such a way that it satisfies his wish) at some blue point, then mark a circle around it; otherwise mark a cross at that point (similar to the game tic tac toe). We first make an important observation, which will provide the main crux of the problem (in all cases, we try to consider the optimal situation)- | ||
+ | |||
+ | [b]Observation[/b] If a blue point is circled, then we cannot circle its neighbor. | ||
+ | |||
+ | [u]PROOF[/u] Consider a blue point <math>\cal{B}</math> and its inverse <math>\cal{B'}</math>. Let <math>\cal{A}</math> be the neighbor of <math>\cal{B}</math>. Then it's easy to see that <math>\cal{A'}</math> is the neighbor of <math>\cal{B'}</math>. Let <math>P=\cal{BB'} \cap \cal{AA'}</math>, and assume to the contrary that both <math>\cal{B}</math> and <math>\cal{A}</math> can be circled. Suppose there are <math>x</math> red points on the segment <math>\cal{B} P</math>, and <math>y</math> red points on the segment <math>\cal{A} P</math> (excluding <math>P</math>). Then, we must have <math>x \neq y</math>. However, each line segment passing through the <math>x</math> red points on <math>\cal{B} P</math> must also pass through the <math>y</math> red points on <math>\cal{A} P</math> (since otherwise the condition that <math>\cal{B_n}</math> is the neighbor of <math>\cal{B}</math> gets violated). This gives <math>x=y</math>, a contradiction. Thus, our observation is true. | ||
+ | |||
+ | [b]Part (b)[/b] Circle any arbitrary blue point <math>\cal{B}</math>, and cross its inverse <math>\cal{B'}</math>. Then, by our Observation, there must be a cross at its neighbor, and a circle at the inverse of its neighbor. Repeat this process as long as possible. Note that there are exactly <math>n-1</math> blue points on both sides of <math>\cal{BB'}</math> (since otherwise all the red points do not lie inside <math>\cal{C}</math>). However, for the alternating sequence of circles and crosses staring from <math>\cal{B}</math> and ending at <math>\cal{B'}</math> (where we move in anticlockwise direction) to go on [i]peacefully[/i], there must be an even number of blue points on the arc <math>\widehat{\cal{BB'}}</math>, which gives that <math>n-1</math> is even, a contradiction. Thus, Geoff can never fulfill his wish if <math>n</math> is even. | ||
+ | |||
+ | [b]Part (a)[/b] As in Part (b), we get a sequence of alternating circles and crosses, and we have to show that this configuration will make Geoff happy. Suppose to the contrary that, for some odd <math>n</math>, two frogs meet at the same time (despite our exhaustive strategies :D). Consider the line segments on which these frogs were kept, and call them <math>\cal{AA'}</math> and <math>\cal{BB'}</math>, where <math>A</math> and <math>B</math> were circled. Let <math>P=\cal{AA'} \cap \cal{BB'}</math>. Suppose there are <math>k</math> blue points on the arc <math>\widehat{\cal{AB}}</math> not containing <math>A'</math> and <math>B'</math>. As both <math>A</math> and <math>B</math> are circled, so <math>k</math> must be odd. By our assumption, there exist an equal number of red points on the segments <math>\cal{A} P</math> and <math>\cal{B} P</math> (excluding <math>P</math>). Now, suppose there exists a line segment passing through a red point on segment <math>\cal{A} P</math> but not passing through any red point on segment <math>\cal{B} P</math>. As there are an equal number of red points on these two segments, so there must also exist a line segment passing through one of the red points on segment <math>\cal{B} P</math>, but not passing through any red point on segment <math>\cal{A} P</math>. Both of these line segments will then contribute to the number of blue points present on arc <math>\widehat{\cal{AB}}</math> (i.e. while counting <math>k</math>). Thus all the blue points on <math>\widehat{\cal{AB}}</math> come in pairs, which gives that <math>k</math> is even, a contradiction. Otherwise, no line segment intersects <math>\widehat{\cal{AB}}</math>, which gives <math>k=0</math>, again not possible. Thus, our assumption must be wrong, and so Geoff can always fulfill his wish if <math>n</math> is odd. | ||
==See Also== | ==See Also== | ||
{{IMO box|year=2016|num-b=5|after=Last Problem}} | {{IMO box|year=2016|num-b=5|after=Last Problem}} |
Latest revision as of 13:31, 4 December 2024
Problem
There are line segments in the plane such that every two segments cross and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it facing the other endpoint. Then he will clap his hands
times. Every time he claps,each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will ever occupy the same intersection point at the same time.
(a) Prove that Geoff can always fulfill his wish if is odd.
(b) Prove that Geoff can never fulfill his wish if is even.
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
Beautiful problem. Despite being placed a bit higher in both the Shortlist and the actual exam, kudos to the proposer for involving combi, geo and NT in one single problem. Anyway, here's my solution: Color each of the endpoints [color=#00f]blue[/color] and all the
intersection points [color=#f00]red[/color]. Join the blue points with a smooth curve
such that none of the line segments intersect
more than twice (i.e. all the red points lie inside
). Call the [i]inverse[/i] of a blue point
, the point which lies on both
and the line segment through
, and denote it by
. Also, we define the [i]neighbor[/i] of a blue point
as the point which lies on the right of
(if we stand facing the inverse of
) and nearest to it. Finally, if Geoff (from now on we) can place a frog (in such a way that it satisfies his wish) at some blue point, then mark a circle around it; otherwise mark a cross at that point (similar to the game tic tac toe). We first make an important observation, which will provide the main crux of the problem (in all cases, we try to consider the optimal situation)-
[b]Observation[/b] If a blue point is circled, then we cannot circle its neighbor.
[u]PROOF[/u] Consider a blue point and its inverse
. Let
be the neighbor of
. Then it's easy to see that
is the neighbor of
. Let
, and assume to the contrary that both
and
can be circled. Suppose there are
red points on the segment
, and
red points on the segment
(excluding
). Then, we must have
. However, each line segment passing through the
red points on
must also pass through the
red points on
(since otherwise the condition that
is the neighbor of
gets violated). This gives
, a contradiction. Thus, our observation is true.
[b]Part (b)[/b] Circle any arbitrary blue point , and cross its inverse
. Then, by our Observation, there must be a cross at its neighbor, and a circle at the inverse of its neighbor. Repeat this process as long as possible. Note that there are exactly
blue points on both sides of
(since otherwise all the red points do not lie inside
). However, for the alternating sequence of circles and crosses staring from
and ending at
(where we move in anticlockwise direction) to go on [i]peacefully[/i], there must be an even number of blue points on the arc
, which gives that
is even, a contradiction. Thus, Geoff can never fulfill his wish if
is even.
[b]Part (a)[/b] As in Part (b), we get a sequence of alternating circles and crosses, and we have to show that this configuration will make Geoff happy. Suppose to the contrary that, for some odd , two frogs meet at the same time (despite our exhaustive strategies :D). Consider the line segments on which these frogs were kept, and call them
and
, where
and
were circled. Let
. Suppose there are
blue points on the arc
not containing
and
. As both
and
are circled, so
must be odd. By our assumption, there exist an equal number of red points on the segments
and
(excluding
). Now, suppose there exists a line segment passing through a red point on segment
but not passing through any red point on segment
. As there are an equal number of red points on these two segments, so there must also exist a line segment passing through one of the red points on segment
, but not passing through any red point on segment
. Both of these line segments will then contribute to the number of blue points present on arc
(i.e. while counting
). Thus all the blue points on
come in pairs, which gives that
is even, a contradiction. Otherwise, no line segment intersects
, which gives
, again not possible. Thus, our assumption must be wrong, and so Geoff can always fulfill his wish if
is odd.
See Also
2016 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Problem |
All IMO Problems and Solutions |