2011 UNCO Math Contest II Problems/Problem 10


The integers $1, 2, 3,\cdots , 50$ are written on the blackboard. Select any two, call them $m$ and $n$ and replace these two with the one number $m+n+mn$. Continue doing this until only one number remains and explain, with proof, what happens. Also explain with proof what happens in general as you replace $50$ with $N$. As an example, if you select $3$ and $17$ you replace them with $3 + 17 + 51 = 71$. If you select $5$ and $7$, replace them with $47$. You now have two $47$’s in this case but that’s OK.

Solution 1

First try $\{1, 2, 3, \ldots , n\}$ for $n= 2, 3, 4, 5$. The crossing off process yields $\{5,23,119,719\}$ each one being one less than a factorial. So for general $n$ you should end up with$(n+1)!-1$. Now look at $n=3$ again and replace $1, 2, 3$ with $a,b,c$ (order does not matter). Crossing off gives you \[(a+b+ab) + c + (a+b+ab)c  =a+b+c+ab+ac+bc+abc\] reminding one of the coefficients in \[(x-a)(x-b)(x-c)= x^3-(a+b+c)x^2+(ab+ac+bc)x-abc\] Now let $x=-1$, and watch what happens remember that $\{a,b,c\} = \{1,2,3\}$. There are other approaches.

Solution 2

By using Simon's Favorite Factoring Trick, we can see that $m+n+mn=(m+1)(n+1)-1.$ Something interesting happens when we set $a-1=m$ and $b-1=n:$ \begin{align*} (m+1)(n+1)-1&=\\ (a-1+1)(b-1+1)-1&=\\ ab-1 \end{align*} If we represent each element of the set as $a-1,$ the action repeatedly performed becomes much simpler. For a set $S={a_1-1, a_2-1, ..., a_n-1},$ performing the action stated in the problem until one value is left yields the value $(a_1)(a_2)(a_3)...(a_n)-1.$ Setting $S$ to the first 50 integers and perform the action until one value is left, we get a value equal to $\boxed{51!-1}.$ Setting $S$ to the first $N$ integers yeilds a value equal to $\boxed{(N+1)!-1}$

See Also

2011 UNCO Math Contest II (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10
All UNCO Math Contest Problems and Solutions