Competition problem — Combinatorics

Library / /628 of 740

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

Consider an infinite grid of equilateral triangles. Each edge (that is, each side of a small triangle) is colored one of $N$ colors. The coloring is done in such a way that any path between any two nonadjacent vertices consists of edges with at least two different colors. What is the smallest possible value of $N$ ?

Solution

Solution:

Answer: 6

Note that the condition is equivalent to having no edges of the same color sharing a vertex by just considering paths of length two. Consider a hexagon made out of six triangles. Six edges meet at the center, so $N \geq 6$ . To prove $N=6$ , simply use two colors for each of the three possible directions of an edge, and color edges of the same orientation alternatingly with different colors.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.