Maths Olympiad Prep

Library / /6 of 12

Combinatorics Difficulty 6.0 AIME, harder Prove it Bulgaria

Every two of nn towns in a country are connected by one way or two way road. It is known that for every kk towns there exists round trip passing through each of these kk towns exactly once. Find the maximal possible number of one way roads.

Solution

Suppose there exists a town AA with k1k-1 one way roads all of which are pointing in one and the same direction from AA. Town AA with all k1k-1 end points of one way roads form a group of kk towns that violates the condition of the problem. We conclude that for any town there exist at most k2k-2 one way roads in the town and at most k2k-2 roads out of the town. Therefore the one way roads are at most n(k2)n(k-2).

We show now that when n2k3n \le 2k-3, it is possible to have all roads to be one way roads and when n>2k3n > 2k-3 then the maximal number of one way roads equals n(k2)n(k-2).

Let n=2k3n = 2k-3 and consider the towns to be vertexes of a regular nn-gon. For every town AA let k2k-2 one way roads out of AA point to the next k2k-2 towns clockwise. Since n=2k3n = 2k-3 such allocation is possible and every two towns are connected with one way road. Consider a group of kk towns and order them clockwise. Between any two neighbors AA and BB there exists one way road from AA to BB. Therefore the desired round trip exists.

When n<2k3n < 2k-3, it suffices to choose arbitrary nn towns from the above construction.

When n>2k3n > 2k-3 we proceed by similar manner. Connect every town AA with one way road from AA with the next k2k-2 towns. Let all remaining roads be two way roads.

Take arbitrary kk towns. Consider a group of kk towns and order them clockwise. Between any two neighbors AA and BB there exists one way road from AA to BB. Therefore the desired round trip exists.

Answer. When n2k3n \le 2k-3 all roads could be one way and when n>2k3n > 2k-3 there exist at most n(k2)n(k-2) one way roads.

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 and solution reproduced as published; topic and difficulty added by this site.