South African Mathematics Olympiad

We show that the answer is generally $\left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right)=\frac{(a+b-2)!}{(a-1)!(b-1)!}$ if there are $a$ towns on one side and $b$ on the other. In our particular instance, there are thus $\left(\genfrac{}{}{0ex}{}{33}{14}\right)=818809200$ 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=1$ or $b=1$. In this case, $\left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right)=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 $A_1,A_2,\dots ,A_{\alpha }$, and the villages on the other side $B_1,B_2,\dots ,B_{\beta }$ (in this order). Note first that $A_1$ and $B_1$ cannot both be connected by a bridge to villages other than each other: if there is a bridge between $A_1$ and $B_k$ and a bridge between $B_1$ and $A_l$, where $k,l>1$, then these bridges cross, which is impossible. This leaves us with two possibilities:

$A_1$ is directly connected to $B_1$ only, while $B_1$ is connected to the rest. In this case, we can ignore $A_1$ and only count the possibilities to build bridges between $A_2,A_3,\dots ,A_{\alpha }$ and $B_1,B_2,\dots ,B_{\beta }$. By the induction hypothesis, this can be done in $\left(\genfrac{}{}{0ex}{}{a+b-3}{a-2}\right)$ ways. $B_1$ is directly connected to $A_1$ only, while $A_1$ is connected to the rest. In this case, we can ignore $B_1$, and the induction hypothesis shows that there are $\left(\genfrac{}{}{0ex}{}{a+b-3}{a-1}\right)$ possibilities.

Altogether, this gives us $$\left(\genfrac{}{}{0ex}{}{a+b-3}{a-2}\right)+\left(\genfrac{}{}{0ex}{}{a+b-3}{a-1}\right)=\left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right)$$ possibilities to build the bridges, which completes our induction.