Maths Olympiad Prep

Library / /35 of 56

Combinatorics Difficulty 5.8 AIME, harder Prove it Singapore

The numbers 12,13,,12010\frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{2010} are written on a blackboard. A student chooses any two of the numbers, say x,yx, y, erases them and then writes down x+y+xyx + y + xy. He continues to do this until only one number is left on the blackboard. What is this number?

Solution

We shall prove by induction that if the original numbers are a1,,ana_1, \dots, a_n, n2n \ge 2, then the last number is (1+a1)(1+an)1(1+a_1) \cdots (1+a_n) - 1.
The assertion is certainly true for n=2n=2, the base case. Now suppose it is true for n=k2n=k \ge 2. Consider k+1k+1 numbers a1,,ak+1a_1, \dots, a_{k+1} written on the board. After one operation, we are left with kk numbers. Without loss of generality, we can assume that the student erases aka_k and writes bk=ak+ak+1+akak+1=(1+ak)(1+ak+1)1b_k = a_k+a_{k+1}+a_k a_{k+1} = (1+a_k)(1+a_{k+1})-1. After a further kk operations, we are left with the number
(1+a1)(1+ak1)(1+bk)1=(1+a1)(1+ak1)(1+ak)(1+ak+1)1. (1+a_1) \cdots (1+a_{k-1})(1+b_k) - 1 = (1+a_1) \cdots (1+a_{k-1})(1+a_k)(1+a_{k+1}) - 1.
This completes the proof of the inductive step. Thus the last number is
(1+12)(1+13)(1+12010)1=2010 (1 + \frac{1}{2})(1 + \frac{1}{3}) \cdots (1 + \frac{1}{2010}) - 1 = 2010

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 reproduced verbatim; metadata (topic, difficulty) added by this project.