Maths Olympiad Prep

Library / Japanese Mathematical Olympiad - The First Round /7 of 7

Japanese Mathematical Olympiad - The First Round

Number theory Difficulty 5.2 AIME, harder Prove it Japan

Tomohiro and Akinori read mathematical books as follows. Akinori reads 2 pages a day. Tomohiro reads 3 pages a day. However, each of the two stop reading of that day if he reaches the end of a chapter.

There is a mathematical book which consists of 10 chapters and 120 pages. Find the smallest value of the difference between the number of days in which Akinori reads the book and that of Tomohiro. A new chapter always begins with a new page.

Solution

It is clear that the smallest value exists. Let BB be a book with nin_i pages for the ii-th chapter which attains the smallest value.

We first prove that none of n1,n2,…,n10n_1, n_2, \dots, n_{10} are equivalent to 33 or 55 modulo 66. Assume that n1≡3,5(mod6)n_1 \equiv 3, 5 \pmod{6}. Checking the parity, we can assume without loss of generality that n2n_2 is odd. Consider book B′B' whose chapter one has 4 pages, chapter two has n1+n2−4n_1 + n_2 - 4 pages, and the remaining chapters have the same number of pages with corresponding chapters of BB. Then easy computation shows that Akinori can read B′B' faster than BB, and that Tomohiro can't read B′B' faster than BB. Then the difference of the days needed to read B′B' is smaller than that of BB, which contradicts minimality of BB.

Now let ni=6mi+kin_i = 6m_i + k_i (mim_i nonnegative, kik_i nonnegative <6< 6 and ki≠3,5k_i \ne 3, 5). Then it can be easily checked that Tomohiro reads ii-th chapter mim_i days faster than Akinori. Since
∑i=110mi=16(∑i=110ni−∑i=110ki)=16(120−∑i=110ki) \sum_{i=1}^{10} m_i = \frac{1}{6} \left( \sum_{i=1}^{10} n_i - \sum_{i=1}^{10} k_i \right) = \frac{1}{6} \left( 120 - \sum_{i=1}^{10} k_i \right)
and ki≤4k_i \le 4, it follows that ∑mi≥20−406\sum m_i \ge 20 - \frac{40}{6}, hence ∑mi≥14\sum m_i \ge 14. This value is in fact attained if, for example, n1=n2=⋯=n9=10n_1 = n_2 = \dots = n_9 = 10 and n10=30n_{10} = 30. Therefore, the smallest value is 14.

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.