There are some real numbers on the board (at least two). In every step we choose two of them, for example $a$ and $b$, and then we replace them with $\frac{ab}{a+b}$. We continue until there is one number. Prove that the last number does not depend on which order we choose the numbers to erase.
Problem
Source: AZE JBMO TST
Tags: combinatorics
02.05.2015 22:50
it is obvious that if in some step $a_1,a_2,\cdots ,a_n$ are written on the board then the number $\frac{1}{\frac{1}{a_1}+\frac{1}{a_2}+\cdots +\frac{1}{a_n}}$ is invariant so if at the first step the numbers $b_1,b_2,\cdots ,b_m$ are on the board then the last number is $\frac{1}{\frac{1}{b_1}+\frac{1}{b_2}+\cdots +\frac{1}{b_m}}$ which is afixed number. DONE
12.04.2020 23:35
Can anybody check if this works? I claim that the last number does not depend on what order we choose the numbers to erase. I will prove that the last number does not change by using induction. Base Case: If there are two numbers, the sum is given to be $\frac{ab}{a+b}$. Inductive Hypothesis: If there are $n-1$ numbers, then the number that remains is $\frac{a_1a_2a_3...a_n}{all the products that have n-1 terms in it}$. Inductive Step: Lets say our nth number is $a_n$. We can use our given rule for this number and our sum for $n-1$ terms and we find that the number that remains is $\frac{a_1a_2...a_n}{all the products that have n terms in it}$. Thus, our induction is complete. With this result, that means that the resulting number depends on the sum and product of the starting values. Thus, our last number will always be the same regardless of what numbers we choose to erase.
09.10.2020 20:20
If I am not missing something, I think this is correct.
17.12.2020 20:49
This just comes from the Commutative Property of sum and multiplication.
17.12.2020 20:55
I think this is a well-known problem. Let $a_1,a_2,\ldots,a_n$ be the numbers written on the board. Key claim: $\sum_{k=1}^n \frac{1}{a_k}$ is invariant. We only have to look at $a$ and $b$, since everything else stays the same. Indeed, we have $\frac{1}{a}+\frac{1}{b}=\frac{a+b}{ab}=\frac{1}{\frac{ab}{a+b}}$. Thus the claim is proven. Therefore, let the value of $\sum_{k=1}^n \frac{1}{a_k}$ at the start be $S$. Let $x$ be the value of the last number that remains. Then from our invariant, we have $\frac{1}{x}=S \implies x=\frac{1}{S}$. Since $S$ doesn't depend on the order in which the numbers are combined, we are done. $\blacksquare$
17.12.2020 21:03
Alternatively, let the numbers be $x_1,\cdots, x_n$ and let $y_i:=1/x_i$. Replacing $x_i,x_j$ by ${{x_ix_j}\over {x_i+x_j}}$ corresponds to replacing $y_i,y_j$ by $y_i+y_j$. Then its clear that the final $y$ becomes $\sum_1^n y_i$.
29.10.2021 21:32
IstekOlympiadTeam wrote: There are some real numbers on the board (at least two). In every step we choose two of them, for example $a$ and $b$, and then we replace them with $\frac{ab}{a+b}$. We continue until there is one number. Prove that the last number does not depend on which order we choose the numbers to erase. Note that $\frac{ab}{a + b} = \frac{1}{\frac{1}{a}+\frac{1}{b}}$ let's do a first operation with the numbers $a$ and $b$ , then the number that we have left is $\frac{ab}{a + b}$, now let's do an operation with the number obtained and a number $c$, and the number that we have left is $ \frac{abc}{ab + bc + ca} = \frac{1}{\frac{1}{a} + \frac{1}{b} + \frac{1}{c}}$, by induction we obtain that the final number in a total of $n$ numbers is $\frac {1}{\frac{1}{a_1} + \frac{1}{a_2} + ... + \frac{1}{a_n}}$, so with this the final number already It is fixed, that is, the order of operations will not change the final result.
30.03.2022 17:55
If there is a $0$ on the board at any point, then clearly the last number will be $0$ independent of which replacements are made. Let $H(x_1,x_2,\ldots,x_n)$ be the harmonic mean of $x_1,x_2,\ldots,x_n$, note that $\frac{ab}{a+b}=H(a,b)$. Order the numbers on the board as $a_1,a_2,\ldots,a_n$ so that whenever $a,a_m,a_{m+1},\ldots,a_n$ are on the board, the next move is made with $a$ and $a_m$. By induction, we will show that, after the $i$th move, the numbers $H(a_1,a_2,\ldots,a_{i+1}),a_{i+2},\ldots,a_n$ are left on the board. The base case is trivial. If $H(a_1,a_2,\ldots,a_{i+1}),a_{i+2},\ldots,a_n$ are on the board at any point, then after the next move, we will have $\frac1{\frac1{a_1}+\frac1{a_2}+\ldots+\frac1{a_{i+1}}+\frac1{a_{i+2}}},\ldots,a_n$, completing the induction. Then we will end up with $H(a_1,a_2,\ldots,a_n)$ at the end. But since $H(x_1,x_2,\ldots,x_n)$ is symmetric, the order of $\{a_i\}$ doesn't matter.
12.12.2024 20:04
Denote the as $a_1,a_2,...,a_n$ Now we will prove $\frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3}+...+\frac{1}{a_n}$ is invariant. $Prove:$ Suppose we have the reals $a,b$ and the other reals. We replace $n$ with $a$ and $b$ where $n=\frac{ab}{a+b}$ Now lets suppose $r_1,r_2,...,r_n$ were the other reals and $x=\frac{1}{r_1}+\frac{1}{r_2}+...+\frac{1}{r_n}$ Now, $\frac{1}{n}+x=\frac{a+b}{ab}+x=\frac{1}{a}+\frac{1}{b}+x$ which proves the invariance. Now suppose initially the reals numbers were $b_1,b_2,...,b_n$ and final number as $c$ from invariance, $\frac{1}{c}=\frac{1}{b_1}+\frac{1}{b_2}+...+\frac{1}{b_n}$ $c=\frac{1}{\frac{1}{b_1}+\frac{1}{b_2}+...+\frac{1}{b_n}}$ which is independent of which order we choose $\square$