Maths Olympiad Prep

Library / /24 of 27

Combinatorics Difficulty 6.4 National Olympiad Prove it Singapore

A group of tourists get on 10 buses in the outgoing trip. The same group of tourists get on 8 buses in the return trip. Assuming each bus carries at least 1 tourist, prove that there are at least 3 tourists such that each of them has taken a bus in the return trip that has more people than the bus he has taken in the outgoing trip.

Solution

We prove the general case where there are pp outgoing buses and qq returning buses with p>qp > q. The number of such tourists is pq+1p - q + 1. Let TT be the set of all tourists. For each tTt \in T, let ptp_t be the number of tourists in the bus that tt takes in the outgoing trip and let qtq_t be the number of tourists in the bus that tt takes in the return trip. Then
tT1pt=p,tT1qt=qtT(1pt1qt)=pq \sum_{t \in T} \frac{1}{p_t} = p, \quad \sum_{t \in T} \frac{1}{q_t} = q \quad \Rightarrow \quad \sum_{t \in T} \left( \frac{1}{p_t} - \frac{1}{q_t} \right) = p - q
Since 1pt1qt<1|\frac{1}{p_t} - \frac{1}{q_t}| < 1, at least pq+1p-q+1 terms in the above sum is positive. That is, there are at least pq+1p-q+1 tourists such that 1pt1qt>0\frac{1}{p_t} - \frac{1}{q_t} > 0, or equivalently pt<qtp_t < q_t.

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.