Difference between revisions of "2006 SMT/General Problems/Problem 8"

m (Problem 8)
m (Solution)
Line 13: Line 13:
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
We now see that we need to find all unordered 4-tuples of positive integers such that the product of all the elements is less that five. Those tuples are:
+
We now see that we need to find all unordered 4-tuples of positive integers such that the product of all the elements is less that or equal to five. Those tuples are:
 
<cmath>(a_1,a_2,a_3,a_4) \in \{(1,1,1,1), (2,1,1,1), (3,1,1,1), (4,1,1,1), (2,2,1,1), (5,1,1,1)\}</cmath>
 
<cmath>(a_1,a_2,a_3,a_4) \in \{(1,1,1,1), (2,1,1,1), (3,1,1,1), (4,1,1,1), (2,2,1,1), (5,1,1,1)\}</cmath>
  

Revision as of 17:36, 14 January 2020

Problem

Given two $2$'s, "plus" can be changed to "times" without changing the result: $2+2=2\cdot2$. The solution with three numbers is easy too: $1+2+3=1\cdot2\cdot3$. There are three answers for the five-number case. Which five numbers with this property has the largest sum?

Solution

Assuming all the numbers are positive, lets denote the five numbers as $a_0,a_1,a_2,a_3,a_4$. Assume WLOG that $a_0 \ge a_1 \ge a_2 \ge a_3 \ge a_4$. The condition we are looking for is $a_0+a_1+a_2+a_3+a_4 = a_0 \cdot a_1 \cdot a_2\cdot a_3 \cdot a_4$.

Manipulating the LHS, we see that: \begin{align*} a_0+a_1+a_2+a_3+a_4 &= a_0 \cdot a_1 \cdot a_2\cdot a_3 \cdot a_4\\ 5a_0 &\ge a_0 \cdot a_1 \cdot a_2\cdot a_3 \cdot a_4\\ 5 &\ge a_1 \cdot a_2\cdot a_3 \cdot a_4 \end{align*}

We now see that we need to find all unordered 4-tuples of positive integers such that the product of all the elements is less that or equal to five. Those tuples are: \[(a_1,a_2,a_3,a_4) \in \{(1,1,1,1), (2,1,1,1), (3,1,1,1), (4,1,1,1), (2,2,1,1), (5,1,1,1)\}\]

We can test each tuple separately, and solve for $a_0$ by plugging them into the original constraint. This yields the solutions $(a_0,a_1,a_2,a_3,a_4) \in \{(3,3,1,1,1),(2,2,2,1,1), (5,2,1,1,1)\}$

We have three solutions, as said in the problem, therefore the tuple with the greatest sum is clearly $(a_0,a_1,a_2,a_3,a_4) = (5,2,1,1,1)$. Our solution is $\boxed{(5,2,1,1,1)}$