MathDB

A certain island has some ports along the coast and some towns inland. All roads on this island are one-way, and they do not meet except at a port or a town. Moreover, once you leave a certain port or town by road, there is no way you can return there by road. For any two ports

i

and

j

, let

f_{ij}

denote the number of different routes along the roads between

i

and

j

.
(a) Suppose there are four ports on the island:

1, 2, 3

and

4

, in clockwise order. Show that

f_{14}f_{23} \ge f_{13}f_{24}

(b) Suppose there were six ports on the island:

1, 2, 3, 4, 5

and

6

, in clockwise order. Show that

f_{16}f_{25}f_{34} + f_{15}f_{24}f_{36} + f_{14}f_{26}f_{35}\ge f_{16}f_{24}f_{35}+ f_{15}f_{26}f_{34} + f_{14}f_{25}f_{36}

(S Fomin}

Problem Statement