1981 USAMO Problems/Problem 2
Problem
What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a train link. No three towns, are such that the links between and are all air, all bus or all train.
Solution
Assume , , and are all rail.
None of , , or can be rail, as those cities would form a rail triangle with .
If is bus, then is bus as well, as otherwise has all three types.
However, cannot be rail (as would be a rail triangle), bus (as would be a bus triangle), or ferry (as and would have all three types).
Therefore, no city can have three connections of the same type.
Assume there are 5 towns - , , , , and .
Two connections from must be of one type, and two of another; otherwise there would be at least three connections of the same type from , which has been shown to be impossible.
Let and be rail connections, and and be bus.
Assume is air.
cannot be rail ( would be a rail triangle) or bus ( would have all three types), so must be air.
cannot be bus ( would be a bus triangle) or rail ( would have all three types), so must be air.
cannot be rail ( would have all three types) or bus ( would have all three types), so must be air.
However, cannot be rail ( would have all three types), bus ( would have all three types), or air ( would have three air connections).
Therefore, the assumption that is air is false.
can equally be rail or bus; assume it is bus.
cannot be rail ( would be a rail triangle) or air ( would have all three types), so must be bus.
cannot be air ( would have all three types) or bus ( would have three bus connections), so must be rail.
cannot be air ( would have all three types) or bus ( would have three bus connections), so must be rail.
cannot be air ( would have all three types) or bus ( would have three bus connections), so must be rail.
The only connection remaining is , which cannot be orange as both and would have all three types, but this means there are no air connections.
Therefore, it is impossible with five (or more) towns.
A four-town mapping is possible:
, , , and are connected by bus.
is connected by rail.
is connected by air.
Therefore, the maximum number of towns is .
See Also
1981 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.