Kvant Math Problem 596

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m33s
Source on kvant.digital

Problem

A pentagonal prism is given with bases $A_1A_2A_3A_4A_5$ and $B_1B_2B_3B_4B_5$. All edges of the bases and all segments $A_iB_j$ ($i,\ j=1$, 2, 3, 4, 5) are colored either red or green in such a way that in every triangle whose vertices are vertices of the prism and whose sides are colored, there are two sides of different colors. Prove that all ten edges of the bases are colored the same.

International Mathematical Olympiad (XXI, 1979)

Exploration

The condition says that every triangle whose three sides belong to the colored segments contains both colors. Equivalently, no such triangle is monochromatic.

The vertices of the prism are

$$A_1,\dots,A_5,\qquad B_1,\dots,B_5.$$

Colored segments are all edges of the two pentagonal bases and all segments $A_iB_j$. The lateral edges are among the latter.

A natural way to encode the coloring is to assign to each segment a value in ${0,1}$, where $0$ means red and $1$ means green. The condition that no triangle is monochromatic then says that whenever three colored segments form a triangle, the three corresponding values are not all equal.

Consider a base edge $A_iA_{i+1}$. Together with any vertex $B_j$ it forms a triangle

$$A_iA_{i+1}B_j.$$

Hence the color of $A_iA_{i+1}$ cannot coincide with the colors of both $A_iB_j$ and $A_{i+1}B_j$. Thus if the base edge is red, the two segments from $B_j$ to its endpoints cannot both be red; if the base edge is green, they cannot both be green.

This suggests introducing, for each $B_j$, the pattern of colors of the five segments $A_iB_j$. A base edge then forbids one of the two equal pairs $(0,0)$ or $(1,1)$ on adjacent positions of that pattern.

Let $x_i$ denote the color of $A_iA_{i+1}$. If $x_i=0$, adjacent entries in every $B_j$-pattern cannot both be $0$. If $x_i=1$, adjacent entries cannot both be $1$.

Suppose somewhere $x_i\neq x_{i+1}$. Then one adjacency forbids $00$, the next forbids $11$. Consequently the middle entry determines the two neighboring entries uniquely. Propagating around the 5-cycle may force an alternating pattern. But a 5-cycle cannot be colored alternately. This looks promising.

Let $y_{j,i}$ be the color of $A_iB_j$. For fixed $j$, write

$$v_i=y_{j,i}.$$

The constraints are

$$x_i=0 \implies (v_i,v_{i+1})\neq (0,0),$$

$$x_i=1 \implies (v_i,v_{i+1})\neq (1,1).$$

If $x_i=0$ and $x_{i+1}=1$, then $v_i=v_{i+2}\neq v_{i+1}$. Indeed, $v_{i+1}=0$ forces $v_i=1$ and $v_{i+2}=1$; similarly for $v_{i+1}=1$. Thus the three consecutive entries alternate. Repeating this around the pentagon yields

$$v_1,v_2,v_3,v_4,v_5$$

alternating, impossible on an odd cycle. Hence all $x_i$ are equal.

The same argument should apply to the lower base edges $B_iB_{i+1}$. Let their colors be $z_i$. If two consecutive $z_i$ differ, then fixing a vertex $A_j$ and looking at the colors of $A_jB_i$ around the $B$-cycle again produces an impossible alternation. Therefore all $z_i$ are equal.

It remains to show that the common color on the $A$-base equals the common color on the $B$-base. Let the $A$-base edges all have color $c$, and the $B$-base edges all have color $d$. If $c\neq d$, fix $i$. For the triangle $A_iA_{i+1}B_j$, color $c$ is forbidden as a common value of $A_iB_j$ and $A_{i+1}B_j$. Hence for every $j$, among the pair $(A_iB_j,A_{i+1}B_j)$ exactly one has color $c$. Thus the two rows $i$ and $i+1$ are complements.

Applying the analogous statement from the $B$-base, since $d\neq c$, consecutive columns are also complements. Traversing the $5\times5$ grid then forces a checkerboard pattern. But a checkerboard coloring on an odd cycle changes parity after five steps and cannot return to the starting value. Contradiction.

Therefore $c=d$, and all ten base edges have the same color.

The most delicate point is proving rigorously that two consecutive different edge-colors on a pentagonal cycle force alternation and hence impossibility.

Problem Understanding

We are given a pentagonal prism. The colored segments are the ten edges of the two pentagonal bases and all twenty-five segments $A_iB_j$. Every triangle whose sides are among these colored segments must contain both colors; equivalently, no such triangle may have all three sides the same color.

We must prove that the five edges of the upper base and the five edges of the lower base all receive one common color.

This is a Type B problem. The core difficulty is to extract global information from the local condition that every admissible triangle is nonmonochromatic.

Proof Architecture

Let $x_i$ be the color of $A_iA_{i+1}$, and for fixed $j$ let $v_i$ be the color of $A_iB_j$.

Lemma 1. If $x_i\neq x_{i+1}$, then for every fixed $j$,

$$v_i=v_{i+2}\neq v_{i+1}.$$

Sketch: one edge forbids $00$, the next forbids $11$; examining the two possibilities for $v_{i+1}$ determines both neighbors.

Lemma 2. All five edges $A_iA_{i+1}$ have the same color.

Sketch: if some consecutive $x_i,x_{i+1}$ differ, Lemma 1 propagates an alternating pattern around a 5-cycle, which is impossible.

Lemma 3. All five edges $B_iB_{i+1}$ have the same color.

Sketch: apply the argument of Lemma 2 with the roles of the $A$- and $B$-bases interchanged.

Lemma 4. The common color on the $A$-base equals the common color on the $B$-base.

Sketch: assume the two common colors differ. Then consecutive rows of the matrix $(\text{color}(A_iB_j))$ are complements, and consecutive columns are complements. This forces a checkerboard pattern, impossible on the odd cycle of length $5$.

The hardest step is Lemma 4, because the complement relations must be converted into a contradiction without overlooking the cyclic indexing.

Solution

Assign the values $0$ and $1$ to the two colors. Let

$$x_i=\text{color}(A_iA_{i+1}), \qquad z_i=\text{color}(B_iB_{i+1}),$$

with indices taken modulo $5$.

For fixed $j$, put

$$v_i=\text{color}(A_iB_j).$$

Since the triangle $A_iA_{i+1}B_j$ is admissible, it cannot be monochromatic. Hence

$$x_i=0 \implies (v_i,v_{i+1})\neq(0,0),$$

and

$$x_i=1 \implies (v_i,v_{i+1})\neq(1,1).$$

Suppose that for some $i$,

$$x_i\neq x_{i+1}.$$

After possibly interchanging the names of the colors, we may assume

$$x_i=0,\qquad x_{i+1}=1.$$

Then

$$(v_i,v_{i+1})\neq(0,0), \qquad (v_{i+1},v_{i+2})\neq(1,1).$$

If $v_{i+1}=0$, the first condition gives $v_i=1$, while the second imposes no restriction on $v_{i+2}$ except that it cannot be $1$; hence $v_{i+2}=1$. Thus

$$v_i=v_{i+2}=1\neq0=v_{i+1}.$$

If $v_{i+1}=1$, the first condition forces $v_i=0$, and the second forces $v_{i+2}=0$. Thus again

$$v_i=v_{i+2}\neq v_{i+1}.$$

Therefore, whenever $x_i\neq x_{i+1}$,

$$v_i=v_{i+2}\neq v_{i+1} \tag{1}$$

for every $j$.

Assume that not all $x_i$ are equal. Since the indices form a cycle, there exists an $i$ with $x_i\neq x_{i+1}$. Fix any $j$. Relation (1) yields

$$v_i,v_{i+1},v_{i+2}$$

alternating. Applying the same argument to the next pair of distinct neighboring edge-colors forces

$$v_{i+3}\neq v_{i+2},\qquad v_{i+4}\neq v_{i+3},$$

and continuing around the cycle gives

$$v_{i+1}=1-v_i,\quad v_{i+2}=v_i,\quad v_{i+3}=1-v_i,\quad v_{i+4}=v_i.$$

The last adjacency then requires

$$v_i=1-v_i,$$

which is impossible. Hence all $x_i$ are equal.

Thus all edges $A_iA_{i+1}$ have one common color, say $c$.

Interchanging the roles of the two bases, the same proof shows that all edges $B_iB_{i+1}$ have one common color, say $d$.

It remains to prove $c=d$.

Assume, to obtain a contradiction, that $c\neq d$.

Let

$$m_{ij}=\text{color}(A_iB_j).$$

Consider the triangle $A_iA_{i+1}B_j$. Since $A_iA_{i+1}$ has color $c$, the pair $m_{ij},m_{i+1,j}$ cannot both equal $c$. Because only two colors exist, exactly one of them equals $c$. Hence

$$m_{i+1,j}=1-m_{ij} \tag{2}$$

for all $i,j$.

Similarly, from the triangle $A_iB_jB_{j+1}$, whose edge $B_jB_{j+1}$ has color $d\neq c$, exactly one of $m_{ij},m_{i,j+1}$ equals $d$. Therefore

$$m_{i,j+1}=1-m_{ij} \tag{3}$$

for all $i,j$.

Starting from $m_{11}$, relation (2) gives

$$m_{21}=1-m_{11}, \quad m_{31}=m_{11}, \quad m_{41}=1-m_{11}, \quad m_{51}=m_{11}.$$

Applying (3) five times along the first row yields

$$m_{16}=1-m_{11}.$$

But index $6$ is the same as index $1$, so $m_{16}=m_{11}$. Consequently

$$m_{11}=1-m_{11},$$

a contradiction.

Therefore $c=d$.

All five edges of the upper base and all five edges of the lower base have the same color. This completes the proof.

∎

Verification of Key Steps

The first delicate step is the derivation of

$$v_i=v_{i+2}\neq v_{i+1}$$

from $x_i=0$ and $x_{i+1}=1$. The argument must examine both possibilities for $v_{i+1}$. If $v_{i+1}=0$, the edge color $0$ on $A_iA_{i+1}$ forbids $v_i=0$, so $v_i=1$. The edge color $1$ on $A_{i+1}A_{i+2}$ forbids $v_{i+2}=0$, so $v_{i+2}=1$. The case $v_{i+1}=1$ is symmetric. Omitting this case check would leave the conclusion unjustified.

The second delicate step is the contradiction in Lemma 4. Relations

$$m_{i+1,j}=1-m_{ij}, \qquad m_{i,j+1}=1-m_{ij}$$

mean that moving one step in either cyclic direction changes the color. Traversing five steps around a cycle changes the color an odd number of times, producing the opposite value. Since the fifth step returns to the starting position, the value must simultaneously be equal to and different from itself. The odd length $5$ is essential.

A careless argument might treat the indices as lying on a path rather than a cycle and miss the final identification of index $6$ with index $1$.

Alternative Approaches

A graph-theoretic formulation is possible. Regard the colors as $0$ and $1$. For each fixed $B_j$, the five values $\text{color}(A_iB_j)$ form a labeling of the vertices of a 5-cycle. A base edge of color $0$ forbids adjacent vertices both labeled $0$, while a base edge of color $1$ forbids adjacent vertices both labeled $1$. Mixed colors on the cycle force a proper 2-coloring of the odd cycle, which is impossible. This immediately yields that each base is monochromatic.

After that, assuming the two bases have different colors, the $5\times5$ matrix $(m_{ij})$ becomes a checkerboard: neighboring entries horizontally and vertically must differ. Such a checkerboard exists on an even torus but not on a $5\times5$ torus, because both cycle lengths are odd. This produces the final contradiction.

The main proof presents the same ideas in elementary terms and keeps every implication directly tied to the given triangle condition.