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 "1992 IMO Problems/Problem 3"

(created the problem and solution for the 1992 IMO Problem 3 because it wasn't created yet)
 
m (→‎Problem)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
3. Consider nine points in space, no four of which are coplanar. Each pair
+
==Problem==
−
of points is joined by an edge (that is, a line segment) and each edge is
 
−
either colored blue or red or left uncolored. Find the smallest value of
 
−
<math>n</math> such that whenever exactly n edges are colored, the set of colored
 
−
edges necessarily contains a triangle all of whose edges have the same
 
−
color.
 
  
 +
Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of <math>n</math> such that whenever exactly n edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.
  
−
Solution:
+
==Solution==
 
We show that for <math>n = 32</math> we can find a coloring without a monochrome triangle.
 
We show that for <math>n = 32</math> we can find a coloring without a monochrome triangle.
 
Take two squares <math>R_1R_2R_3R_4</math> and <math>B_1B_2B_3B_4</math>. Leave the diagonals of each square uncolored, color the remaining edges of <math>R</math> red and the remaining edges of <math>B</math>
 
Take two squares <math>R_1R_2R_3R_4</math> and <math>B_1B_2B_3B_4</math>. Leave the diagonals of each square uncolored, color the remaining edges of <math>R</math> red and the remaining edges of <math>B</math>
Line 14: Line 10:
 
Clearly <math>X</math> is not the vertex of a monochrome square, because if <math>XY</math> and <math>XZ</math> are
 
Clearly <math>X</math> is not the vertex of a monochrome square, because if <math>XY</math> and <math>XZ</math> are
 
the same color then, <math>YZ</math> is either uncolored or the opposite color. There is no triangle within the red square or the blue square, and hence no monochrome triangle. It remains to consider triangles of the form <math>R_iR_jB_k</math> and <math>B_iB_jR_k.</math> But if <math>i</math> and <math>j</math> have the same parity, then <math>R_iR_j</math> is uncolored (and similarly <math>B_iB_j</math>), whereas if
 
the same color then, <math>YZ</math> is either uncolored or the opposite color. There is no triangle within the red square or the blue square, and hence no monochrome triangle. It remains to consider triangles of the form <math>R_iR_jB_k</math> and <math>B_iB_jR_k.</math> But if <math>i</math> and <math>j</math> have the same parity, then <math>R_iR_j</math> is uncolored (and similarly <math>B_iB_j</math>), whereas if
−
they have opposite parity, then <math>R_iB_k</math> and <math>R_jB_k</math> have opposite colors (and similarly <math>B_iR_k and </math>B_jR_k<math>).
+
they have opposite parity, then <math>R_iB_k</math> and <math>R_jB_k</math> have opposite colors (and similarly <math>B_iR_k</math> and <math>B_jR_k</math>).
−
It remains to show that for </math>n = 33<math> we can always find a monochrome triangle.
+
It remains to show that for <math>n = 33</math> we can always find a monochrome triangle.
 
There are three uncolored edges. Take a point on each of the uncolored edges.
 
There are three uncolored edges. Take a point on each of the uncolored edges.
−
The edges between the remaining </math>6<math> points must all be colored. Take one of
+
The edges between the remaining <math>6</math> points must all be colored. Take one of
−
these, </math>X.<math> At least </math>3<math> of the </math>5<math> edges to </math>X<math>, say </math>XA<math>, </math>XB<math>, </math>XC<math> must be the same color
+
these, <math>X.</math> At least <math>3</math> of the <math>5</math> edges to <math>X</math>, say <math>XA</math>, <math>XB</math>, <math>XC</math> must be the same color
−
(say red). If </math>AB<math> is also red, then </math>XAB<math> is monochrome. Similarly, for </math>BC<math> and </math>CA.<math>
+
(say red). If <math>AB</math> is also red, then <math>XAB</math> is monochrome. Similarly, for <math>BC</math> and <math>CA.</math>
−
But if </math>AB<math>, </math>BC<math> and </math>CA<math> are all blue, then </math>ABC$ is monochrome.
+
But if <math>AB</math>, <math>BC</math> and <math>CA</math> are all blue, then <math>ABC</math> is monochrome.
 +
 
 +
==See Also==
 +
 
 +
{{IMO box|year=1992|num-b=2|num-a=4}}
 +
[[Category:Olympiad Geometry Problems]]
 +
[[Category:3D Geometry Problems]]

Latest revision as of 01:17, 18 January 2024

Problem

Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $n$ such that whenever exactly n edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

Solution

We show that for $n = 32$ we can find a coloring without a monochrome triangle. Take two squares $R_1R_2R_3R_4$ and $B_1B_2B_3B_4$. Leave the diagonals of each square uncolored, color the remaining edges of $R$ red and the remaining edges of $B$ blue. Color blue all the edges from the ninth point $X$ to the red square, and red all the edges from $X$ to the blue square. Color $R_iB_j$ red if $i$ and $j$ have the same parity and blue otherwise. Clearly $X$ is not the vertex of a monochrome square, because if $XY$ and $XZ$ are the same color then, $YZ$ is either uncolored or the opposite color. There is no triangle within the red square or the blue square, and hence no monochrome triangle. It remains to consider triangles of the form $R_iR_jB_k$ and $B_iB_jR_k.$ But if $i$ and $j$ have the same parity, then $R_iR_j$ is uncolored (and similarly $B_iB_j$), whereas if they have opposite parity, then $R_iB_k$ and $R_jB_k$ have opposite colors (and similarly $B_iR_k$ and $B_jR_k$). It remains to show that for $n = 33$ we can always find a monochrome triangle. There are three uncolored edges. Take a point on each of the uncolored edges. The edges between the remaining $6$ points must all be colored. Take one of these, $X.$ At least $3$ of the $5$ edges to $X$, say $XA$, $XB$, $XC$ must be the same color (say red). If $AB$ is also red, then $XAB$ is monochrome. Similarly, for $BC$ and $CA.$ But if $AB$, $BC$ and $CA$ are all blue, then $ABC$ is monochrome.

See Also

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