Question 46
*South African Magical Flights* (SAMF) operates flights between South African airports. If there is a flight from airport $A$ to airport $B$, there will also be a flight from $B$ to $A$.
The SAMF headquarters are located in Kimberley. Every airport that is served by SAMF can be reached from Kimberley in precisely one way. This way of reaching Kimberley may involve stopping at other airports on the way. (For example, it may happen that you can get to Kimberley from Durban by flying from Durban to Bloemfontein and then from Bloemfontein to Kimberley. In that case there is no other way to get from Durban to Kimberley. For example, there would be no direct flight from Durban to Kimberley.)
An airport (other than Kimberley) is called *terminal* if there are flights to (and from) precisely one other airport. Suppose that there are $t$ terminal airports.
Due to budget cuts, SAMF decides to close down $k$ of the airports. It should still be possible to reach each of the remaining airports from Kimberley.
Let $C$ be the number of choices for the $k$ destinations that are discontinued. Prove that
$$
\frac{t!}{k!(t-k)!} \le C \le \frac{(t+k-1)!}{k!(t-1)!},
$$
where $n! = 1 \times 2 \times \dots \times n$ for any positive integer $n$, and $0! = 1$.
The SAMF headquarters are located in Kimberley. Every airport that is served by SAMF can be reached from Kimberley in precisely one way. This way of reaching Kimberley may involve stopping at other airports on the way. (For example, it may happen that you can get to Kimberley from Durban by flying from Durban to Bloemfontein and then from Bloemfontein to Kimberley. In that case there is no other way to get from Durban to Kimberley. For example, there would be no direct flight from Durban to Kimberley.)
An airport (other than Kimberley) is called *terminal* if there are flights to (and from) precisely one other airport. Suppose that there are $t$ terminal airports.
Due to budget cuts, SAMF decides to close down $k$ of the airports. It should still be possible to reach each of the remaining airports from Kimberley.
Let $C$ be the number of choices for the $k$ destinations that are discontinued. Prove that
$$
\frac{t!}{k!(t-k)!} \le C \le \frac{(t+k-1)!}{k!(t-1)!},
$$
where $n! = 1 \times 2 \times \dots \times n$ for any positive integer $n$, and $0! = 1$.