Maths Olympiad Prep

Library / /38 of 39

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Croatia

In some archipelago, there are 20172017 islands labelled 1,2,,20171, 2, \ldots, 2017. Two agencies, Red dragon and Blue eye, are planning to establish ship lines between certain islands. Exactly one agency will operate between each two islands, with a ship line from the island labelled with a smaller number to the island labelled with a larger number.

An arrangement of ship lines is good if there are no two islands, labelled AA and BB, where A<BA < B, such that it is possible to go from AA to BB in two ways: one, using only the ships owned by Red dragon, and the other, using only ships owned by Blue eye.

Determine the number of good arrangements of ship lines. (Russia 2005)

Solution

Ship lines maintained by Red dragon we will call red lines, and those maintained by Blue eye blue lines.

Let ana_n denote the number of good arrangements for an archipelago with nn islands. Consider an archipelago with n+1n + 1 islands and notice island 11. Let AA be the set of all islands which are connected to island 11 with a red line, and let BB be the set of all islands which are connected to island 11 with a blue line.

Note that all lines (if there are any) from some island in AA to some island in BB must be blue. Suppose that's not the case, i.e. that there are islands aAa \in A and bBb \in B such that a<ba < b and the line aba \to b is red. We know that line 1b1 \to b is blue, and lines 1a1 \to a and aba \to b are red, hence we can go from aa to bb using only red lines, and also using only blue lines, which is a contradiction. By the same reasoning we conclude that all lines (if there are any) from some island in BB to some island in AA must be red.

Figure 1

Let set AA contain k{0,1,,n}k \in \{0, 1, \dots, n\} islands. That means that set BB contains nkn-k islands. Note that islands in the set AA must form an archipelago with a good arrangement of ship lines, and the same holds for the set BB. On the other hand, for each selection of archipelagos AA and BB with good arrangements we get exactly one archipelago with n+1n+1 islands and good ship lines arrangement between them.

Now, using mathematical induction, we will prove that an=n!a_n = n!. It is obvious that a0=a1=1a_0 = a_1 = 1. Suppose that ak=k!a_k = k!, for all knk \le n, for some positive integer nn. By previous reasoning we conclude that
an+1=k=0n(nk)akank=k=0nn!=(n+1)! a_{n+1} = \sum_{k=0}^{n} \binom{n}{k} a_k a_{n-k} = \sum_{k=0}^{n} n! = (n+1)!
Thus, an=n!a_n = n! and finally a2017=2017!a_{2017} = 2017!.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.