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 outgoing buses and returning buses with . The number of such tourists is . Let be the set of all tourists. For each , let be the number of tourists in the bus that takes in the outgoing trip and let be the number of tourists in the bus that takes in the return trip. Then
Since , at least terms in the above sum is positive. That is, there are at least tourists such that , or equivalently .
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.