Maths Olympiad Prep

Library / /21 of 115

Combinatorics Difficulty 6.8 National olympiad Find the answer

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, A,B,CA, B, C are such that the links between AB,ACAB, AC and BCBC are all air, all bus or all train.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Assume ABAB , ACAC , and ADAD are all rail.
None of BCBC , CDCD , or CDCD can be rail, as those cities would form a rail triangle with AA .
If BCBC is bus, then BDBD is bus as well, as otherwise BB has all three types.
However, CDCD cannot be rail (as ACD\triangle ACD would be a rail triangle), bus (as BCDBCD would be a bus triangle), or ferry (as CC and DD would have all three types).
Therefore, no city can have three connections of the same type.
Assume there are 5 towns - AA , BB , CC , DD , and EE .
Two connections from AA must be of one type, and two of another; otherwise there would be at least three connections of the same type from AA , which has been shown to be impossible.
Let ABAB and ACAC be rail connections, and ADAD and AEAE be bus.
Assume CDCD is air.
BCBC cannot be rail ( ABC\triangle ABC would be a rail triangle) or bus ( CC would have all three types), so BCBC must be air.
DEDE cannot be bus ( ADE\triangle ADE would be a bus triangle) or rail ( DD would have all three types), so DEDE must be air.
BEBE cannot be rail ( EE would have all three types) or bus ( BB would have all three types), so BEBE must be air.
However, BDBD cannot be rail ( DD would have all three types), bus ( BB would have all three types), or air ( DD would have three air connections).
Therefore, the assumption that CDCD is air is false.
CDCD can equally be rail or bus; assume it is bus.
BCBC cannot be rail ( ABC\triangle ABC would be a rail triangle) or air ( CC would have all three types), so BCBC must be bus.
BDBD cannot be air ( BB would have all three types) or bus ( DD would have three bus connections), so BDBD must be rail.
DEDE cannot be air ( DD would have all three types) or bus ( DD would have three bus connections), so DEDE must be rail.
CECE cannot be air ( CC would have all three types) or bus ( EE would have three bus connections), so CECE must be rail.
The only connection remaining is BEBE , which cannot be orange as both BB and DD 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:
ABAB , BCBC , CDCD , and DADA are connected by bus.
ACAC is connected by rail.
BDBD is connected by air.
Therefore, the maximum number of towns is 44 .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.