Maths Olympiad Prep

Library / Singapur /20 of 23

Singapur

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 p−q+1p - q + 1. Let TT be the set of all tourists. For each t∈Tt \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
∑t∈T1pt=p,∑t∈T1qt=q⇒∑t∈T(1pt−1qt)=p−q \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 ∣1pt−1qt∣<1|\frac{1}{p_t} - \frac{1}{q_t}| < 1, at least p−q+1p-q+1 terms in the above sum is positive. That is, there are at least p−q+1p-q+1 tourists such that 1pt−1qt>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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.