1981 USAMO / Problem 2

Let's try to solve this question using an analogy.

Let there be $\displaystyle N$ points. These are to be connected using three different colours of lines Red, Yellow and Blue. We have to find the maximum value of $N$ under these conditions:

$Condition1$ : Each pair of points is to be connected by only one colour.

$Condition2$ : There has to be atleast one line of each colour. Thus, $\displaystyle {N\choose 2}_{min} = 1+1+1=3$ $\displaystyle \Rightarrow N_{min} = 3$ .

$Condition3$ : There is no point such that lines of all 3 colours pass through it. (Intersections of the lines with themselves other than the given $N$ points are not to be considered for this condition. Consider only the $N$ points that we began with.)

$Condition4$ : There is no triangle such that all it's sides are of the same colour.

Total number of lines possible is $\displaystyle (T) = {N\choose 2} = \frac{N(N-1)}{2}$ .

Consider the $N$ points to be $A_1, A_2, \ldots A_N$ .

$\text{ }$

We start with the case where there are $(N)$ Red lines:

Let the $\displaystyle (N)$ Red lines form the perimeter of an $\displaystyle N$ -sided polygon $A_1A_2\ldots A_N$ . In this polygon total number of lines connecting the $A_i's$ has to be equal to $(T)$ so that $Condition1$ is satisfied.

We select a point, say $A_5$ , and draw $(N-3)$ Yellow lines to the remaining points. Now, every point except $A_4,A_5,A_6$ is connected to a Yellow and Red line so no Blue line is possible there. We connect $A_4$ and $A_6$ with the only Blue line possible. Now, no Yellow line is possible too, because if we connect any two points, say $A_3$ and $A_7$ with a Yellow line, it will result in a Yellow triangle $\bigtriangleup A_3A_5A_7$ . Thus, no more lines can be drawn.

Hence for $Condition1$ to be satisfied:

$\displaystyle T= \text{(number of Red lines)} + \text{(number of Yellow lines) } + \text{(number of Blue lines)}$

$\displaystyle T=(N) + (N-3) + 1$

$\displaystyle \Rightarrow {N\choose 2} = 2N - 2$

$\displaystyle \Rightarrow N^2 - 5N + 4 = 0$

$\displaystyle \Rightarrow N=\{1,4\}$

$N=1$ is discarded. Thus, for $(N)$ Red lines, $N=4$ is the only solution.

$\text{ }$

Now, we move on to the case where there are $(N-1)$ Red lines:

$Case 1$ : Select a point, say $A_1$ , draw $N-1$ Red lines to the remaining points. Now select another point, say $A_6$ , draw $(N-2)$ Yellow lines to all points other than $A_1$ (Since the line $A_1A_6$ is already drawn in Red.)

Now, we have $(N-2)$ points which are already connected by Red and Yellow lines. So, no Blue lines can be drawn. Also, drawing any more Yellow lines will result in the formation of Yellow triangles. Thus, no more lines cab be drawn. In this case, $Condition3$ is not satisfied here.

So, we replace one Yellow line for a Blue line.

Now, for $Condition1$ to be satisfied:

$\displaystyle T = (N-1) + (N-3)) +(1)$

$\displaystyle \Rightarrow T = 2N-3$

$\displaystyle \Rightarrow N^2 - 5N + 6 = 0$

$\displaystyle N = \{2,3\}$

$N=2$ is discarded and $N=3$ is the solution.

$Case 2$ : Instead of replacing a Yellow line for a Blue line, if we draw only $(N-4)$ Yellow lines leaving 2 points to be connected by a Blue line, $Condition1$ now gives:

$\displaystyle T=(N-1) + (N-4) + 1$

$\displaystyle \Rightarrow {N\choose 2} = 2N - 4$

$\displaystyle \Rightarrow N^2 - 5N + 8= 0$

$\displaystyle \Rightarrow Discriminant < 0$

Hence, no solution is possible in this case.

$Case 3$ : Draw $(N-1)$ Red lines such that they form the perimeter of an $\displaystyle N$ - sided polygon such that $A_1,A_N$ are not connected.

Draw Yellow lines from $A_3$ to all other points except $A_1,A_2,A_4, A_N$ . Thus, $(N-5)$ Yellow lines are drawn.

Draw the Blue lines $A_4A_1$ , $A_4A_2$ and $A_NA_1$ and $A_NA_2$ , thus forming a Blue hourglass-like structure. Hence, 4 Blue lines are drawn. $Condition2, 3,4$ are satisfied.

For $Condition1$ to be satisfied:

$\displaystyle T = (N-1) + (N-5) + 4$

$\displaystyle \Rightarrow T = 2N - 2$

$\displaystyle \Rightarrow N^2 - 5N + 4 = 0$

$\displaystyle \Rightarrow N=\{1,4\}$

$N = 1$ is discarded and we get $N = 4$ as the solution.

$\text{ }$

$\text{ }$

Interestingly, as we go on decreasing the number of Red lines to $(N-2), (N-3), (N-4), \ldots$ so on, depending on the number, order, method of selection of Red, Yellow and Blue lines we get $N=3$ or $N=4$ or no solution for N at all. Thus, we conclude that $\boxed{N=4}$ and $\boxed{N=3}$ are the only solutions satisfying all the conditions.

Now we consider the case when there are $(N+1)$ Red lines:

Let $(N)$ Red lines form the perimeter of an $N$ - sided polygon and draw one Red line such that $A_1,A_4$ are connected. For $A_1$ , $A_3, A_{N-1}$ cannot be chosen as that would result in a Red triangle $\bigtriangleup A_1A_2A_3$ or $\bigtriangleup A_1A_NA_{N-1}$ .

Draw Yellow lines from $A_1$ to all points except $A_2,A_N, A_4$ . (These points are already connected to $A_1$ in Red.) Thus, $(N-4)$ Yellow lines are drawn.

Now, draw the Blue lines $A_4A_2$ and $A_4A_N$ . Thus, there are 2 Blue lines. Now, all the points to connected to lines of any 2 of the colours. $Condition2, 3, 4$ are satisfied.

For $Condition1$ to be satisfied:

$\displaystyle T = (N+1) + (N-4) + (2)$

$\displaystyle {N\choose 2} = 2N-1$

$\displaystyle N^2 - 5N + 2 = 0$

As is seen, there are no positive integral solutions possible for $N$ in this case.

As we go on increasing the number of Red lines to $(N+2), (N+3), \ldots$ so on, we notice that no positive integral solutions for $N$ are possible.

Thus, we conclude $\boxed{N=3}$ and $\boxed{N=4}$ are the only possible solutions satisfying the given conditions.

Hence, the largest number of towns meeting all the criteria is $\displaystyle \boxed{4}$ .

(I know it's a really long solution and might require additional clarification or there could have been errors at places. Please feel free to point them out or ask any doubts.)

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 (triangle 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

(Solution credits: AOPS)