The first \(9\) natural numbers are given in a list. You are supposed to select two numbers randomly from the list, call them \(x\) and \(y\), remove them from the list and insert \(x + y + xy\) into the list. You keep repeating this until you are left with only one number in the list. Which number is most likely to be the last number left in the list?

Thursday, February 17, 2011

Please email your solutions to puzzles@cotpi.com.

### 1 comment

### Credit

This puzzle is taken from folklore.

### Further reading

The following is a list of resources on related topics:

- Wheeler, David A. "When Adding and Multiplying are the Same." 10 Sep. 2002. 9 Sep. 2011 <http://www.dwheeler.com/essays/add-multiply.html>.

## Ryan Batterman solved this puzzle:

Let \(f(x, y) = x + y + xy\). It can be rewritten as \(f(x, y) = (x + 1)(y + 1) - 1\). Now, consider an arbitrary set of integers \(A = \{a_1, a_2, \dots, a_n\}\). Applying the algorithm mentioned in the problem statement to two integers \(a_i\) and \(a_j\) chosen randomly from the set such that \(i \ne j\), we obtain, \(f(a_i, a_j) = (a_i + 1)(b_i + 1) - 1\). When this expression is used in subsequent calls to \(f(x, y)\), the \(-1\) drops, the new number is included in the product and the \(-1\) gets added again. For instance, using this result and a different number \(a_k\) chosen randomly from the set, we obtain \(f\bigl((a_i + 1)(a_j + 1) - 1, a_k\bigr) = (a_i + 1)(a_j + 1)(a_k + 1) - 1\). Inductively, this pattern holds, and the algorithm returns a product of all integers in the set minus \(1\).

Therefore, the result of the algorithm, when applied to the set \(A\) is \(\prod_{i=1}^n (a_i + 1) - 1\). If \(A = \{1, 2, \dots, 9\}\), on applying the algorithm, we obtain \((1 + 1)(2 + 1)\dots(9 + 1) - 1 = 10! - 1 = 3628799\).