23
$\begingroup$

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?

Thanks in advance.

$\endgroup$
11
  • $\begingroup$ 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"? $\endgroup$ Commented Mar 21, 2012 at 17:54
  • 2
    $\begingroup$ 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. $\endgroup$
    – mdp
    Commented Mar 21, 2012 at 17:56
  • $\begingroup$ I guess vikiii meant xy/(x+y). $\endgroup$
    – quartz
    Commented Mar 21, 2012 at 17:59
  • $\begingroup$ Ah, yes, that seems likely. I probably should have realised that, must be too used to LaTeX! $\endgroup$
    – mdp
    Commented Mar 21, 2012 at 18:00
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Mar 23, 2012 at 19:35

3 Answers 3

34
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ A more obvious physics analogy is resistors wired in parallel. $\endgroup$
    – Dan
    Commented Mar 21, 2012 at 23:12
  • 1
    $\begingroup$ Is there a (continuous) example that is not related by such a change of coordinates? $\endgroup$
    – A. Rex
    Commented Mar 23, 2012 at 19:09
  • $\begingroup$ @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.) $\endgroup$ Commented Mar 23, 2012 at 21:48
  • $\begingroup$ @Qiaochu thanks. you are awesum..!! $\endgroup$
    – vikiiii
    Commented Mar 24, 2012 at 3:28
  • $\begingroup$ @vikiiii See also this answer. $\endgroup$ Commented Sep 12, 2012 at 21:49
5
$\begingroup$

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}}}$$

$\endgroup$
0
3
$\begingroup$

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}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .