Numbers on blackboard

Question

All numbers $1$ to $155$ are written on a blackboard, one time each. We randomly choose two numbers and delete them, by replacing one of them with their product plus their sum. We repeat the process until there is only one number left. What is the average value of this number?

I don't know how to approach it: For two numbers, $1$ and $2$, the only number is $1\cdot 2+1+2=5$ For three numbers, $1, 2$ and $3$, we can opt to replace $1$ and $2$ with $5$ and then $3$ and $5$ with $23$, or $1$ and $3$ with $7$ and then $2$, $7$ with $23$ or $2$, $3$ with $11$ and $1$, $11$ with $23$ so we see that no matter which two numbers we choose, the average number remains the same. Does this lead us anywhere?

Answer 1

Claim: if $a_1,...,a_n$ are the $n$ numbers on the board then after n steps we shall be left with $(1+a_1)...(1+a_n)-1$.

Proof: induct on $n$. Case $n=1$ is true, so assume the proposition holds for a fixed $n$ and any $a_1$,...$a_n$. Consider now $n+1$ numbers $a_1$,...,$a_{n+1}$. Suppose that at the first step we choose $a_1$ and $a_2$. We will be left with $ n$ numbers $b_1=a_1+a_2+a_1a_2$, $b_2=a_3$,...,$b_n=a_{n+1}$, so by the induction hypothesis at the end we will be left with $(b_1+1)...(b_n+1)-1=(a_1+1)...(a_{n+1}+1)-1$ as needed, because $b_1+1=a_1+a_2+a_1a_2+1=(a_1+1)(a_2+1)$

Where did I get the idea of the proof from? I guess from the n=2 case: for $a_1,a_2$ you are left with $a_1+a_2+a_1a_2=(1+a_1)(1+a_2)-1$ and I also noted this formula generalises for $n=3$

So in your case we will be left with $156!-1=1\times 2\times...\times 156 -1$

Answer 2

Another way to think of Sorin's observation, without appealing to induction explicitly:

Suppose your original numbers (both the original 155 numbers and later results) are written in white chalk. Now above each white number write that number plus one, in red chalk. Write new red companions to each new white number, and erase the red numbers when their white partners go away.

When we erase $x$ and $y$ and write $x+y+xy$, the new red number is $x+y+xy+1=(x+1)(y+1)$, exactly the product of the two red companions we're erasing.

So we can reformulate the entire game as:

Write in red the numbers from $2$ to $156$. Keep erasing two numbers and writing their product instead. At the end when you have one red number left, subtract one and write the result in white.

Since the order of factors is immaterial, the result must be $2\cdot 3\cdots 156-1$.