We consider a prism which has the upper and inferior basis the pentagons: $A_{1}A_{2}A_{3}A_{4}A_{5}$ and $B_{1}B_{2}B_{3}B_{4}B_{5}$. Each of the sides of the two pentagons and the segments $A_{i}B_{j}$ with $i,j=1,\ldots$,5 is colored in red or blue. In every triangle which has all sides colored there exists one red side and one blue side. Prove that all the 10 sides of the two basis are colored in the same color.
Problem
Source: IMO ShortList, Bulgaria 2, IMO 1979, Day 1, Problem 2
Tags: 3D geometry, prism, combinatorics, graph theory, Coloring, IMO, IMO 1979
Learner94
26.09.2011 12:46
Sorry to revive this. The idea of the solution is from the book A Collection of Problems Suggested for IMO. Solution: Let us prove first that the edges $A_1A_2,A_2A_3,\cdots ,A_5A_1$ are of the same color. Assume the contrary, and let w.l.o.g. $A_1A_2$ be red and $A_2A_3$ be green. Three of the segments $A_2B_l, (l = 1, 2, 3, 4, 5)$, say $A_2B_i,A_2B_j,A_2B_k$,have to be of the same color, let it w.l.o.g. be red. Then $A_1B_i,A_1B_j,A_1B_k$ must be green. At least one of the sides of triangle $B_iB_jB_k$, say $B_iB_j$ ,must be an edge of the prism. Then looking at the triangles $A_1B_iB_j$ and $A_2B_iB_j$ we deduce that $B_iB_j$ can be neither green nor red, which is acontradiction. Hence all five edges of the pentagon $A_1A_2A_3A_4A_5$ have thesame color. Similarly, all five edges of $B_1B_2B_3B_4B_5$ have the same color.We now show that the two colors are the same. Assume otherwise, i.e.,that w.l.o.g. the $A$ edges are painted red and the $B$ edges green. Let us call segments of the form $A_iB_j$ diagonal ($i$ and $j$ may be equal). We now count the diagonal segments by grouping the red segments based on their $A$ point, and the green segments based on their $B$ point. As above, the assumption that three of $A_iB_j$ for fixed $i$ are red leads to a contradiction. Hence at most two diagonal segments out of each $A_i$ may be red, which counts up to at most $10$ red segments. Similarly, at most $10$ diagonal segments can be green. But then we can paint at most $20$ diagonal segments out of $25$, which is a contradiction. Hence all edges in the pentagons $A_1A_2A_3A_4A_5$ and $B_1B_2B_3B_4B_5$ have the same color.
eduD_looC
09.08.2021 22:41
Another way to end the solution (starting from the assumption that $A_1A_2A_3A_4A_5$ is completely red and $B_1B_2B_3B_4B_5$ is completely blue) is to consider $A_1B_j$ for fixed $i$ and $j=1,2,3,4,5$. There must be at least three of the same colour by Pigeonhole. However, if they're red, you get a contradiction (using work from proving $A_1A_2A_3A_4A_5$ is only made up of one colour), and if they're blue, you also get a contradiction (use $\triangle A_1B_xB_y$, where $B_x$ and $B_y$ are two adjacent vertices with $A_1B_x$ and $A_1B_y$ being part of the "at least three of the same colour" group).