The numbers $\frac{1}{1}, \frac{1}{2}, \cdots , \frac{1}{2012}$ are written on the blackboard. Aïcha chooses any two numbers from the blackboard, say $x$ and $y$, erases them and she writes instead the number $x + y + xy$. She continues to do this until only one number is left on the board. What are the possible values of the final number?
Problem
Source: Pan African MO 2012 Day 2 Q1
Tags: induction, SFFT, geometry, 3D geometry, invariant, special factorizations, combinatorics proposed
professordad
14.10.2012 17:41
Suppose that Aicha chooses the numbers $a_1$ and $a_2$ first; after she has written the new number, she then chooses $a_3$ and performs the operation again; and so on until $a_{2012}$.
Performing the operation on $a_1$ and $a_2$ gives $(1+a_1)(1+a_2) - 1$; performing the operation on this and $a_3$ gives $\left([(1+a_1)(1+a_2) - 1] + 1\right)\left(1 + a_3\right) - 1$, or $(1 + a_1)(1 + a_2)(1 + a_3) - 1$; and so on. By a simple induction argument, the last number is
\[\left[\prod_{k=1}^{2012} (1 + a_k)\right] - 1\] Plugging in 1/1, 1/2, etc, 1/2012, we see that the product is 2013 (it telescopes), so the final number is 2012.
JBL
21.10.2012 02:13
Your solution presumes that she must make the choices in a particular order, but in fact this is not the case. E.g., she could first combine two numbers, then combine two completely unrelated numbers. Luckily, this operation is associative so it doesn't matter. (This problem is not original to the PAMO; anyone want to go find some past examples on the forum? Maybe the word "SFFT" would help, but maybe not.)
jowramos
23.10.2012 00:45
In relation to this problem, it has appeared, as I remember, at Mathematica Circles (a book from Dmitri Fomin) and at the Cone Sul Mathematical Olympiad. My solution was: consider the number $ E = (a_1 +1)(a_2 +1)\cdots (a_n+1) $, where $a_1,a_2,\dots, a_n$ are the numbers firstly writen on the board. Then, after performing one of these operations, let's say with numbers $a$ and$b$, the number $E$ keeps its value, i.e., it does not vary! In other words, when there's only one number left on the board, say $N$, we mus have $N+1 = E = 2\cdot \dfrac{3}{2} \cdot \dfrac{4}{3} \cdots \dfrac{2013}{2012} =2013 \iff N = 2012$, which solves the problem. I, personally, consider this a classic problem, and a little too mainstream and known for it to be on an international exam, but if they've put it in this year's exam...
mavropnevma
23.10.2012 00:58
Absolutely correct remark. This is the textbook example for the use of invariants, and indeed should not have been used in a competition. At least some variation, making the invariant less obvious ... JBL's hint SSFT is the acronym for Simon's Favorite Factoring Trick, which here pushes towards writing $xy + x + y = (x+1)(y+1) - 1$
OscarGoldenDoodle
12.01.2013 17:35
I could not find the solution myself and looked at the solution posted on this forum. This is a very nice problem with an absolutely beautiful and elegant solution.
math_13
04.05.2013 18:16
At the end of number $(a_1+1)(a_2+1)...(a_2013+1)-1=\frac{1}{2}.\frac{2}{3}...\frac{2013}{2012}-1=2012$ Answer:2012
AshAuktober
13.06.2024 16:00
Post 200, nice! This is a standard one. Observe that if the numbers on the board at any point are $a_1, \cdots, a_n$, then $\prod_{i = 1}^n (a_i+1)$ is invariant. Also, originally it has the value $\left(1+\frac{1}{1} \right)\cdots\left(1+\frac{1}{2012} \right) = \frac{2\cdot 3\cdots 2013}{1 \cdot 2 \cdots 2012} = 2013$ So when there's a single number left, say $a$, $a+1 = 2013 \implies a = 2012$. $\square$