Problem:
A book contains 30 stories. Each story has a different number of pages under 31. The first story starts on page 1 and each story starts on a new page. What is the largest possible number of stories that can begin on odd page numbers?
All-Soviet-Union Mathematical Olympiad
Solution
Solution:
Answer: 23.
Call stories with an odd number of pages odd stories and stories with an even number of pages even stories. There are 15 odd stories and 15 even stories. The odd stories change the parity of the starting page (in the sense that the following story starts on a page of opposite parity), whereas the even stories do not. So the odd stories must start alternately on odd and even pages. Hence 8 of them must start on odd pages and 7 on even pages (irrespective of how the stories are arranged). We can, however, control the even stories. In particular, if we put each of them after an even number of odd stories, then they will all begin on odd pages. For example, we could put them all first (before any of the odd stories).
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.