Find the maximum possible value of the product of distinct positive integers whose sum is $2004$.
Problem
Source: Bulgarian IMO TST 2004, Day 2, Problem 1
Tags: algebra proposed, algebra
08.07.2013 15:41
Mladenov wrote: Find the maximum possible value of the product of distinct positive integers whose sum is $2004$.
08.07.2013 16:09
Consider a maximizing set $S$ of such distinct positive integers with sum $2004$. Let $a$ be the minimum of $S$, and $b$ be the maximum of $S$. Assume that $T=[a,b]-S$ contains at least two elements, and let $x$ and $y$ be the minimum and maximum of $T$, respectively; note that $x<y$. Then $x-1,y+1\in S$ and $x,y\notin S$, and replacing $x-1$ and $y+1$ by $x$ and $y$ would increase the product as $(x-1)(y+1)<xy$. Therefore the maximizing $S$ either forms an interval or an interval with a single missing number. Next assume that $a\ge5$. Then replacing $a$ by $2$ and $a-2$ increases the product, as $a<2(a-2)$. Therefore $a\le4$. Next assume that $a=1$. Then removing $a$ and replacing $b$ by $b+1$ increases the product, as $1\cdot b<b+1$. Therefore $a\ge2$. If $a=2$, then $b=63$ and $S=[2,63]-\{11\}$. If $a=3$, then $b=63$ and $S=[3,63]-\{9\}$. If $a=4$, then $b=63$ and $S=[4,63]-\{6\}$. The highest product out of these three possibilities is $S=[2,63]-\{11\}$.