Maths Olympiad Prep

Library / /59 of 60

Combinatorics Difficulty 6.9 National olympiad Prove it South Africa

Several small villages are situated on the banks of a straight river. On one side, there are 2020 villages in a row, and on the other there are 1515 villages in a row. We would like to build bridges, each of which connects a village on the one side with a village on the other side. The bridges must be straight, must not cross, and it should be possible to get from any village to any other village using only those bridges (and not any roads that might exist between villages on the same side of the river). How many different ways are there to build the bridges?

Solution

We show that the answer is generally (a+b2a1)=(a+b2)!(a1)!(b1)!\binom{a+b-2}{a-1} = \frac{(a+b-2)!}{(a-1)!(b-1)!} if there are aa towns on one side and bb on the other. In our particular instance, there are thus (3314)=818809200\binom{33}{14} = 818\,809\,200 ways to build the bridges. We prove our general formula by induction on the total number of villages. Note that the formula always holds if either a=1a=1 or b=1b=1. In this case, (a+b2a1)=1\binom{a+b-2}{a-1} = 1, and indeed there is only one possibility: to build bridges from the single village on the one side of the river to all other villages. This forms the base of our induction.

We call the villages one the one side A1,A2,,AαA_1, A_2, \dots, A_\alpha, and the villages on the other side B1,B2,,BβB_1, B_2, \dots, B_\beta (in this order). Note first that A1A_1 and B1B_1 cannot both be connected by a bridge to villages other than each other: if there is a bridge between A1A_1 and BkB_k and a bridge between B1B_1 and AlA_l, where k,l>1k, l > 1, then these bridges cross, which is impossible.
This leaves us with two possibilities:

* A1A_1 is directly connected to B1B_1 only, while B1B_1 is connected to the rest. In this case, we can ignore A1A_1 and only count the possibilities to build bridges between A2,A3,,AαA_2, A_3, \dots, A_\alpha and B1,B2,,BβB_1, B_2, \dots, B_\beta. By the induction hypothesis, this can be done in (a+b3a2)\binom{a+b-3}{a-2} ways.
* B1B_1 is directly connected to A1A_1 only, while A1A_1 is connected to the rest. In this case, we can ignore B1B_1, and the induction hypothesis shows that there are (a+b3a1)\binom{a+b-3}{a-1} possibilities.

Altogether, this gives us
(a+b3a2)+(a+b3a1)=(a+b2a1) \binom{a+b-3}{a-2} + \binom{a+b-3}{a-1} = \binom{a+b-2}{a-1}
possibilities to build the bridges, which completes our induction.

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 and solution reproduced as published; topic and difficulty added by this site.