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

2
3
7
8
More than 8
6
4
5

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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.)