Competition problem — Combinatorics

Library / /47 of 196

Combinatorics Difficulty 4.7 AIME Prove it Soviet Union

Problem:
Every city in a certain state is directly connected by air with at most three other cities in the state, but one can get from any city to any other city with at most one change of plane. What is the maximum possible number of cities?

Solution

Solution:
Answer: 10.
Take a particular city $X$ . At most $3$ cities are directly connected to $X$ . Each of those is directly connected to at most $2$ other cities (apart from $X$ ). So $X$ is connected with at most one change to at most $9$ other cities. Thus the maximum number is at most $10$ .

We can achieve $10$ as follows. Label the cities $1, \ldots, 10$ . Make direct connections as follows: $1$ : $2, 3, 4$ ; $2$ : $1, 5, 6$ ; $3$ : $1, 7, 8$ ; $4$ : $1, 9, 10$ ; $5$ : $2, 7, 9$ ; $6$ : $2, 8, 10$ ; $7$ : $3, 5, 10$ ; $8$ : $3, 6, 9$ ; $9$ : $4, 5, 8$ ; $10$ : $4, 6, 7$ .

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.