2021 AMC Fall 10B Problem 23

There are $10$ segments, each red or blue, so $2^{10} = 1024$ colorings, all equally likely. "At least one one-color triangle" is very common, so count the rare opposite: colorings with no one-color triangle.

1. No corner can have three segments of the same color. Each corner has $4$ segments. Suppose corner $V$ had three red segments, going to $A$, $B$, $C$.
- If $AB$ were red, triangle $VAB$ would be all red. So $AB$ is blue.
- The same way, $BC$ and $CA$ are blue.
- But then triangle $ABC$ is all blue.

Either way there is a one-color triangle. The same happens with three blue. So in a good coloring every corner has exactly $2$ red and $2$ blue segments.
2. What do the red segments look like? Every corner touches exactly $2$ red segments. Start at a corner and follow red segments: you enter each corner on one red segment and leave on the other, so you trace a closed loop. A loop needs at least $3$ corners, and $5$ corners cannot be split into two loops of $3$ or more. So the red segments form one loop through all $5$ corners.
3. Does every such loop work? The blue segments are then the other $5$ segments, which also form a loop through all $5$ corners. A five-corner loop contains no triangle. So every red loop gives a good coloring.
4. How many five-corner loops are there? Line up the $5$ corners in a loop order: start at corner $1$ and arrange the other $4$ after it, $4 \times 3 \times 2 \times 1 = 24$ ways. Each loop was counted twice (once going each direction), so there are $\frac{24}{2} = 12$ loops.
5. Probability.
$$1 - \frac{12}{1024} = 1 - \frac{3}{256} = \frac{253}{256}.$$

The answer is $\boxed{\textbf{(D)}\ \frac{253}{256}}$.

A small rule at each corner (no three segments of one color) turned out to fix the whole picture: two interlocking five-sided loops, one red and one blue. When "at least one" is almost certain, it is usually much easier to count the rare cases where it fails and subtract from $1$.

There are $2^{10} = 1024$ colorings of the ten segments. Count the colorings with no single-color triangle.

Fix a vertex $V$; four segments leave it. If three of them, say to $A, B, C$, were red, then to avoid red triangles $VAB$, $VBC$, $VCA$ the segments $AB, BC, CA$ would all be blue, forming a blue triangle. So no vertex has three edges of one color: every vertex has exactly $2$ red and $2$ blue edges.

The red edges then form a graph on $5$ vertices in which every vertex has degree $2$. Such a graph is a union of cycles covering all $5$ vertices; since a cycle needs at least $3$ vertices, $5$ cannot be split, so the red graph is a single $5$-cycle. Its complement (the blue edges) is then also a $5$-cycle, and a $5$-cycle contains no triangle, so every such coloring works.

The number of $5$-cycles on $5$ labeled vertices is $\frac{4!}{2} = 12$ (arrange the vertices around a cycle, up to rotation and reflection).

Therefore the probability of at least one monochromatic triangle is
$$1 - \frac{12}{1024} = 1 - \frac{3}{256} = \frac{253}{256}.$$

The answer is $\boxed{\textbf{(D)}\ \frac{253}{256}}$.