50th Mathematical Olympiad in Ukraine, Third Round (January 23, 2010)

Question

Vitalii, Michael and Olexandr were given n dollars by their mother each one. Vitalii had to spend all his money for buying books, Michael for buying notebooks, Olexandr for pens. Vitalii had bought 1 book, Michael 2 notebooks and Olexandr 5 pens. After that, they together had n dollars. Prove that one of the boys can buy one more item.

Accepted Answer

Assuming the contrary. Denote by q_1, q_2 and q_3 the costs of one book, notebook and pen, respectively, and by r_1, r_2, r_3 the change our boys were given. Obviously r_1 < q_1, r_2 < q_2, r_3 < q_3. From the statement we have n = q_1 + r_1, n = 2q_2 + r_2, n = 5q_3 + r_3 and we can write the next inequalities: n = q_1 + r_1 > 2r_1, n = 2q_2 + r_2 > 3r_2, n = 5q_3 + r_3 > 6r_3 r_1 < 12n, r_2 < 13n, r_3 < 16n. Adding them we will have n = r_1 + r_2 + r_3 < n2 + n3 + n6 = n which is impossible. This contradiction completes the proof.