Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 UNCO Math Contest II Problems/Problem 10"

(→‎Solution)
(→‎Solution)
 
Line 8: Line 8:
  
  
−
== Solution ==
+
== Solution 1 ==
 
First try <math>\{1, 2, 3, \ldots , n\}</math> for <math>n= 2, 3, 4, 5</math>. The crossing off process yields <math>\{5,23,119,719\}</math> each one being one less than a factorial. So for general <math>n</math> you should end up with<math>(n+1)!-1</math>. Now look at <math>n=3</math> again and replace <math>1, 2, 3</math> with <math>a,b,c</math> (order does not matter). Crossing off gives you <cmath>(a+b+ab) + c + (a+b+ab)c  =a+b+c+ab+ac+bc+abc</cmath> reminding one of the coefficients in <cmath>(x-a)(x-b)(x-c)= x^3-(a+b+c)x^2+(ab+ac+bc)x-abc</cmath> Now let <math>x=-1</math>, and watch what happens remember that <math>\{a,b,c\} = \{1,2,3\}</math>. There are other approaches.
 
First try <math>\{1, 2, 3, \ldots , n\}</math> for <math>n= 2, 3, 4, 5</math>. The crossing off process yields <math>\{5,23,119,719\}</math> each one being one less than a factorial. So for general <math>n</math> you should end up with<math>(n+1)!-1</math>. Now look at <math>n=3</math> again and replace <math>1, 2, 3</math> with <math>a,b,c</math> (order does not matter). Crossing off gives you <cmath>(a+b+ab) + c + (a+b+ab)c  =a+b+c+ab+ac+bc+abc</cmath> reminding one of the coefficients in <cmath>(x-a)(x-b)(x-c)= x^3-(a+b+c)x^2+(ab+ac+bc)x-abc</cmath> Now let <math>x=-1</math>, and watch what happens remember that <math>\{a,b,c\} = \{1,2,3\}</math>. There are other approaches.
 +
== Solution 2 ==
 +
By using Simon's Favorite Factoring Trick, we can see that <math>m+n+mn=(m+1)(n+1)-1.</math>
 +
Something interesting happens when we set <math>a-1=m</math> and <math>b-1=n:</math>
 +
\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 <math>a-1,</math> the action repeatedly performed becomes much simpler.
 +
For a set <math>S={a_1-1, a_2-1, ..., a_n-1},</math> performing the action stated in the problem until one value is left yields the value <math>(a_1)(a_2)(a_3)...(a_n)-1.</math>
 +
Setting <math>S</math> to the first 50 integers and perform the action until one value is left, we get a value equal to <math>\boxed{51!-1}.</math>
 +
Setting <math>S</math> to the first <math>N</math> integers yeilds a value equal to <math>\boxed{(N+1)!-1}</math>
  
 
== See Also ==
 
== See Also ==

Latest revision as of 14:55, 31 January 2023

Problem

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 (Problems • Answer Key • Resources)
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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_UNCO_Math_Contest_II_Problems/Problem_10&oldid=188436"