# Why everytime the final number comes the same?

I have come across an interesting puzzle.

Write $20$ numbers. Erase any two number say $x$ and $y$ and and replace with

$\text{Number}_{new} = xy/(x + y)$

OR

$\text{Number}_{new}= x + y + xy$

Where some possible choices of are:

You are to repeat 19 times, until you get a single number.

The final result will be independent of the choices of pairs made. Why is the result the same every time ?

Example:

Suppose I take $4$ numbers $\{2 , 4 , 5 , 7\}$

1. Now if I take $2$ and $4$ and get new number. New set will be $\{\frac86, 5 , 7\}$ Now if I take 5 and 7. New set will be $\{\frac86 , \frac{35}{12}\}$ And the final value will be $\{\frac{140}{153}\}$

2. Now if I take $2$ and $5$ and get new number. New set will be $\{\frac{10}7, 4 , 7\}$. Now if I take $4$ and $7$. New set will be $\{\frac{10}7 , \frac{28}{11}\}$ And the final value will be $\{\frac{140}{153}\}$ again

How is this possible?

-
Where do a and b come from? Are they x and y? Maybe you lost some text between "choices of" and "are" and after "are"? –  Ross Millikan Mar 21 '12 at 17:54
Your new number is just $2y$. Which means if you keep choosing $y$ as the second number then you'll end up with $2^{19}y$, and you won't always get the same answer. –  Matthew Pressland Mar 21 '12 at 17:56
I guess vikiii meant xy/(x+y). –  quartz Mar 21 '12 at 17:59
Ah, yes, that seems likely. I probably should have realised that, must be too used to LaTeX! –  Matthew Pressland Mar 21 '12 at 18:00
Qiaochu Yuan's answer applies to the new expression as x+y+xy=(x+1)(y+1)-1. Please do not add to the question this way after answers have been received as it makes the answers look nonresponsive. –  Ross Millikan Mar 23 '12 at 19:35

The keywords here are associativity and commutativity. The operation $x \circ y = \frac{xy}{x + y}$ clearly has the property $x \circ y = y \circ x$. Less obviously, it also has the property $$(x \circ y) \circ z = x \circ (y \circ z).$$

You can verify this by computing both sides to be $\frac{xyz}{xy + yz + zx}$. Once you know this, it follows that $x \circ y$ defines a commutative semigroup (on, say, the positive reals, to ensure that the division is always well-defined), and in a commutative semigroup the expression $$x_1 \circ x_2 \circ ... \circ x_n$$

is well-defined without the need to insert parentheses (by associativity) and moreover independent of the order of the $x_i$ (by commutativity).

One slick way to see that $\circ$ is indeed associative and commutative is to write it as $$x \circ y = \frac{1}{ \frac{1}{x} + \frac{1}{y} } = f^{-1}(f(x) + f(y))$$

where $f$ (say, as a function from the positive reals to the positive reals) denotes inversion. Then the associativity and commutativity of $\circ$ follows from the associativity and commutativity of $+$, since $$x \circ y = f^{-1}(f(x) + f(y)) = f^{-1}(f(y) + f(x)) = y \circ x$$

and \begin{align*} (x \circ y) \circ z &=& f^{-1}(f(f^{-1}(f(x) + f(y))) + f(z)) \\\ &=& f^{-1}(f(x) + f(y) + f(z)) \\\ &=& f^{-1}(f(x) + f(f^{-1}(f(y) + f(z)))) \\\ &=& x \circ (y \circ z). \end{align*}

It follows by induction that $$x_1 \circ ... \circ x_n = f^{-1}(f(x_1) + ... + f(x_n)) = \frac{1}{ \frac{1}{x_1} + ... + \frac{1}{x_n} }.$$

You can think of this as saying that $\circ$ is just another name for the addition operation, but it's being encoded in a funny way by $f$ and you need to decode it by $f^{-1}$ for everything to make sense. More formally, $f$ defines an isomorphism from the positive reals under $\circ$ to the positive reals under addition.

By writing down other choices for $f$ you can write down more complicated examples of functions with the same property using transport of structure. For example, if $f(x) = \log x$, then $f^{-1}(x) = e^x$, and $$f^{-1}(f(x) + f(y)) = e^{\log x + \log y} = e^{\log x} e^{\log y} = xy$$

so $f$ defines an isomorphism from, say, positive reals under multiplication to the reals under addition (both of which define groups).

As another example, if $f(x) = x^2$, then $f^{-1}(x) = \sqrt{x}$, and $$f^{-1}(f(x) + f(y)) = \sqrt{x^2 + y^2}$$

so $f$ defines an isomorphism from, say, the non-negative reals under the operation $x \circ y = \sqrt{x^2 + y^2}$ to the non-negative reals under addition.

As a final example, let $f(x)$ be the inverse hyperbolic arctangent, so that $f^{-1}(x) = \tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$. Then it turns out that $$f^{-1}(f(x) + f(y)) = \frac{x + y}{1 + xy}$$

which is (in appropriate units) the velocity-addition formula in special relativity, and $f$ defines an isomorphism from the interval $(-1, 1)$ under the above operation to the reals under addition.

-
+1 for relating this to relativity, made me chuckle –  BlueRaja - Danny Pflughoeft Mar 21 '12 at 20:28
+1, man, for such a wonderful generalization! –  Vadim Mar 21 '12 at 20:50
A more obvious physics analogy is resistors wired in parallel. –  Dan Mar 21 '12 at 23:12
Is there a (continuous) example that is not related by such a change of coordinates? –  A. Rex Mar 23 '12 at 19:09
@A. Rex: I don't know. That's probably worth asking as a separate question. (I have a vague guess that one can write down a counterexample by giving a continuous parameterization of part of an elliptic curve and using the group law, which will have elements of finite order in general.) –  Qiaochu Yuan Mar 23 '12 at 21:48

Hint: Assuming you meant $xy\over{x+y}$, Final answer will always be of the form

$$1\over{\sum _{i=1}^{i=20}{1\over{x_i}}}$$

-

Let us find some characteristic of the set of numbers that does not change when you group two of them the way you describe.

The formula $\frac{xy}{x+y}$ suggests the following characteristic: $$\chi(a,b,c,\ldots)=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\ldots$$ Indeed, if we take two numbers $m$ and $n$ and group them, then $$\chi(a,b,\ldots,m,\ldots,n,\ldots)=\frac{1}{a}+\ldots+\frac{1}{m}+\ldots+\frac{1}{n}+\ldots=\frac{1}{a}+\ldots+\frac{m+n}{mn}+\ldots=\chi(a,b,\ldots,\frac{mn}{m+n},\ldots)$$

Therefore, when you group any two numbers in the set, its characteristic does not change, and what you are going to get at the end (regardless of the sequence of pairs you choose) is one number $x$ such that $$\chi(a,b,c,\ldots)=\frac{1}{a}+\frac{1}{b}+\ldots=\chi(x)=\frac{1}{x}$$

-