Maths Olympiad Prep

Library / /7 of 7

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 n13,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 BB' whose chapter one has 4 pages, chapter two has n1+n24n_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 BB' faster than BB, and that Tomohiro can't read BB' faster than BB. Then the difference of the days needed to read BB' 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 ki3,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=110nii=110ki)=16(120i=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 ki4k_i \le 4, it follows that mi20406\sum m_i \ge 20 - \frac{40}{6}, hence mi14\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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.