Library / All-Soviet-Union Mathematical Olympiad /79 of 185

All-Soviet-Union Mathematical Olympiad

Combinatorics Difficulty 5.0 AIME Prove it Soviet Union

Problem:
Can we label each vertex of a 45-gon with one of the digits $0, 1, \ldots, 9$ so that for each pair of distinct digits $i, j$ one of the 45 sides has vertices labeled $i, j$ ?

Solution

Solution:
$10 \times 5 > 45$ , so some digit $i_0$ must appear less than $5$ times. But each occurrence can give at most $2$ edges $i_0, j$ , so there are at most $8$ edges $i_0, j$ , which is one too few.

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

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