## Task 2.

In a certain archipelago, there are 2017 islands named $1, 2, \ldots, 2017$. Two agencies, Red Dragon and Blue Eye, are negotiating the schedule of ferry routes between the islands. For each pair of islands, exactly one agency will organize a ferry route, and this route will only operate from the island with the smaller number to the island with the larger number.

A ferry route schedule is good if there do not exist two islands with labels $A < B$ such that it is possible to travel from island $A$ to island $B$ using only ferries from Red Dragon, and also using only ferries from Blue Eye.

Determine the total number of good ferry route schedules.
## First Solution.

The shipping lines organized by the agency Red Dragon will be called red lines, and those organized by Blue Eye will be called blue lines.

Let $a_{n}$ be the total number of good shipping line schedules for an archipelago with $n$ islands. Consider an archipelago with $n+1$ islands and observe island 1. Let $A$ be the set of all islands to which a red line from 1 goes, and $B$ be the set of all islands to which a blue line from 1 goes.

Notice that all lines (if they exist) from some island in $A$ to some island in $B$ must be blue. Assume the contrary, i.e., there exist islands $a \in A$ and $b \in B$ such that $a < b$ and the line $a \rightarrow b$ is red. The line $1 \rightarrow b$ is blue, and the lines $1 \rightarrow a$ and $a \rightarrow b$ are red, which means it is possible to travel from $a$ to $b$ using only red lines, but also using only blue lines, which is a contradiction. Similarly, we conclude that all (potential) lines from some island in $B$ to some island in $A$ must be red.

![](https://cdn.mathpix.com/cropped/2024_05_30_a077c8100ccb3eae0685g-13.jpg?height=408&width=694&top_left_y=887&top_left_x=681)

Suppose that the set $A$ contains $k \in \{0, 1, \ldots, n\}$ islands. Then the set $B$ contains $n-k$ islands. Notice that the islands in set $A$ must form an archipelago with a good shipping line schedule, and the same applies to the islands in set $B$. Furthermore, for each choice of archipelagos $A$ and $B$ with good shipping line schedules, we get exactly one archipelago with $n+1$ islands that has a good shipping line schedule.

We prove by mathematical induction on the number of islands that $a_{n} = n!$. Clearly, $a_{0} = a_{1} = 1$. Assume that $a_{k} = k!$ for all $k \leq n$. According to the above reasoning, we have

$$
a_{n+1} = \sum_{k=0}^{n} \binom{n}{k} a_{k} a_{n-k} = \sum_{k=0}^{n} n! = (n+1)!
$$

Thus, the claim is proven. Therefore, $a_{2017} = 2017!$.