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 trian link. No three towns, 
are such that the links between 
and 
are all air, all bus or all train.
Solution
Assume AB, AC, and AD are all rail.
None of BC, CD, or CD can be rail, as those cities would form a rail triangle with A.
If BC is bus, then BD is bus as well, as otherwise B has all three types.
However, CD cannot be rail (as ACD would be a rail triangle), bus (as BCD would be a bus triangle), or ferry (as C and D would have all three types).
Therefore, no city can have three connections of the same type.
Assume there are 5 towns - A, B, C, D, and E.
Two connections from A must be of one type, and two of another; otherwise there would be at least three connections of the same type from A, which has been shown to be impossible.
Let AB and AC be rail connections, and AD and AE be bus.
Assume CD is air.
BC cannot be rail (ABC would be a rail triangle) or bus (C would have all three types), so BC must be air.
DE cannot be bus (ADE would be a bus triangle) or rail (D would have all three types), so DE must be air.
BE cannot be rail (E would have all three types) or bus (B would have all three types), so BE must be air.
However, BD cannot be rail (D would have all three types), bus (B would have all three types), or air (D would have three air connections).
Therefore, the assumption that CD is air is false.
CD can equally be rail or bus; assume it is bus.
BC cannot be rail (ABC would be a rail triangle) or air (C would have all three types), so BC must be bus.
BD cannot be air (B would have all three types) or bus (D would have three bus connections), so BD must be rail.
DE cannot be air (D would have all three types) or bus (D would have three bus connections), so DE must be rail.
CE cannot be air (C would have all three types) or bus (E would have three bus connections), so CE must be rail.
The only connection remaining is BE, which cannot be orange as both B and D 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:
AB, BC, CD, and DA are connected by bus
AC is connected by rail
BD is connected by air
Therefore, the maximum number of towns is 4.
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. 
