Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Why everytime the final number comes the same?

Suppose we write the integers 1 thru $n$, choose 2 random ones, erase them, and replace them with the single integer that is their sum plus their product instead. We now have $n-1$ integers written. We repeat this process until we only have 1 number written. Prove that there is only one result possible.

share|improve this question

marked as duplicate by Qiaochu Yuan Jul 4 '12 at 18:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

What does this have to do with probability? –  Chris Eagle Jul 4 '12 at 18:35
@ChrisEagle You choose random integers? ;) Seriously though, this should be retagged, but I'm not sure what to. –  tomasz Jul 4 '12 at 18:37
This is a cool problem, but the original poster doesn't give any context or their own take on it. –  Ben Millwood Jul 4 '12 at 18:43
@Michael: The problem as stated has no probabilistic aspect: that is in fact the point of it. The fact that there is a related probabilistic problem isn’t relevant, and the (probability) tag would be misleading. –  Brian M. Scott Jul 4 '12 at 18:49
@Michael: I flatly disagree. The probability tag is misleading for anyone using tags to see whether his question has already been answered or to look for answers to similar questions. –  Brian M. Scott Jul 4 '12 at 19:30

2 Answers 2

For any numbers $a$ and $b$, $a+b+ab=(a+1)(b+1)-1$; call this $a\otimes b$. For any $a,b,c$,

$$\begin{align*} (a\otimes b)\otimes c&=\Big((a+1)(b+1)-1\Big)\otimes c\\ &=(a+1)(b+1)(c+1)-1\\ &=a\otimes\Big((b+1)(c+1)-1\Big)\\ &=a\otimes(b\otimes c)\, \end{align*}$$

and clearly $a\otimes b=b\otimes a$, so $\otimes$ is a commutative, associative binary operation. It follows that the final result is simply $$\bigotimes_{k=1}^nk=\prod_{k=1}^n(k+1)-1=(n+1)!-1$$ irrespective of the order in which the calculations are performed.

share|improve this answer
But the problem has a probabilistic aspect because at the earlier stages there is a nontrivial distribution of the total at that stage. –  Michael Chernick Jul 4 '12 at 18:47

$$L = \left(\displaystyle \prod_{k=1}^{n} (1+x_k) \right)- 1 = \left(\displaystyle \prod_{k=1}^{n-2} (1+x_k) \right) \left(1+x_{n-1} \right) \left(1+x_n \right)- 1\\ = \left(\displaystyle \prod_{k=1}^{n-2} (1+x_k) \right) \left(1+\left(x_{n-1} + x_n + x_{n-1}x_n \right) \right)- 1 = \left(\displaystyle \prod_{k=1}^{n-2} (1+x_k) \right) \left(1+\tilde{x}_{n-1} \right)- 1$$ Hence, $L$ remains same, if we replace $(x_{n-1},x_n) \to (x_{n-1} + x_n + x_{n-1} x_n)$

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.