2
$\begingroup$

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.

  • 0
    @BrianMScott How can you say the probability tag is misleading? It is clearly a probability problem regardless of whether or not it can be solved by other means.2012-07-04

2 Answers 2

13

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.

  • 0
    But the problem has a probabilistic aspect because at the earlier stages there is a nontrivial distribution of the total at that stage.2012-07-04
1

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