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 "2006 USAMO Problems/Problem 2"

m
m (→‎Solution)
 
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
== Solution ==
+
(''Dick Gibbs'') For a given positive integer <math>k </math> find, in terms of <math>k </math>, the minimum value of <math>N </math> for which there is a set of <math>2k+1 </math> distinct positive integers that has sum greater than <math>N </math> but every subset of size <math>k </math> has sum at most <math>N/2 </math>.
−
== See Also ==
+
 
−
*[[2006 USAMO Problems]]
+
== Solutions ==
 +
 
 +
=== Solution 1 ===
 +
Let one optimal set of integers be <math>\{a_1,\dots,a_{2k+1}\}</math> with <math>a_1 > a_2 > \cdots > a_{2k+1} > 0</math>.
 +
 
 +
The two conditions can now be rewritten as <math>a_1+\cdots + a_k \leq N/2</math> and <math>a_1+\cdots +a_{2k+1} > N</math>.
 +
Subtracting, we get that <math>a_{k+1}+\cdots + a_{2k+1} > N/2</math>, and hence <math>a_{k+1}+\cdots + a_{2k+1} > a_1+\cdots + a_k</math>.
 +
In words, the sum of the <math>k+1</math> smallest numbers must exceed the sum of the <math>k</math> largest ones.
 +
 
 +
Let <math>a_{k+1}=C</math>. As all the numbers are distinct integers, we must have <math>\forall i \in\{1,\dots,k\}:~ a_{k+1-i} \geq C+i</math>, and also <math>\forall i \in\{1,\dots,k\}:~ a_{k+1+i} \leq C-i</math>.
 +
 
 +
Thus we get that <math>a_1+\cdots + a_k \geq kC + \dfrac{k(k+1)}2</math>, and <math>a_{k+1}+\cdots + a_{2k+1} \leq (k+1)C - \dfrac{k(k+1)}2</math>.
 +
 
 +
As we want the second sum to be larger, clearly we must have <math>(k+1)C - \dfrac{k(k+1)}2 > kC + \dfrac{k(k+1)}2</math>.
 +
This simplifies to <math>C > k(k+1)</math>.
 +
 
 +
Hence we get that:
 +
 
 +
<cmath>
 +
\begin{align*}
 +
N & \geq 2(a_1+\cdots + a_k) \\
 +
  & \geq 2\left( kC + \dfrac{k(k+1)}2 \right) \\
 +
  & = 2kC + k(k+1) \\
 +
  & \geq 2k(k^2+k+1) + k(k+1) \\
 +
  & = 2k^3 + 3k^2 + 3k
 +
\end{align*}
 +
</cmath>
 +
 
 +
On the other hand, for the set <math>\{ k^2+k+1+i ~|~ i\in\{-k,\dots,k\} \, \}</math> the sum of the largest <math>k</math> elements is exactly <math>k^3 + k^2 + k + \dfrac{k(k+1)}2</math>, and the sum of the entire set is <math>(k^2+k+1)(2k+1) = 2k^3 + 3k^2 + 3k + 1</math>, which is more than twice the sum of the largest set.
 +
 
 +
Hence the smallest possible <math>N</math> is <math>\boxed{ N = 2k^3 + 3k^2 + 3k }</math>.
 +
 
 +
{{alternate solutions}}
 +
 
 +
== See also ==
 +
* <url>viewtopic.php?t=84550 Discussion on AoPS/MathLinks</url>
 +
 
 +
{{USAMO newbox|year=2006|num-b=1|num-a=3}}
 +
 
 +
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 08:48, 5 August 2014

Problem

(Dick Gibbs) For a given positive integer $k$ find, in terms of $k$, the minimum value of $N$ for which there is a set of $2k+1$ distinct positive integers that has sum greater than $N$ but every subset of size $k$ has sum at most $N/2$.

Solutions

Solution 1

Let one optimal set of integers be $\{a_1,\dots,a_{2k+1}\}$ with $a_1 > a_2 > \cdots > a_{2k+1} > 0$.

The two conditions can now be rewritten as $a_1+\cdots + a_k \leq N/2$ and $a_1+\cdots +a_{2k+1} > N$. Subtracting, we get that $a_{k+1}+\cdots + a_{2k+1} > N/2$, and hence $a_{k+1}+\cdots + a_{2k+1} > a_1+\cdots + a_k$. In words, the sum of the $k+1$ smallest numbers must exceed the sum of the $k$ largest ones.

Let $a_{k+1}=C$. As all the numbers are distinct integers, we must have $\forall i \in\{1,\dots,k\}:~ a_{k+1-i} \geq C+i$, and also $\forall i \in\{1,\dots,k\}:~ a_{k+1+i} \leq C-i$.

Thus we get that $a_1+\cdots + a_k \geq kC + \dfrac{k(k+1)}2$, and $a_{k+1}+\cdots + a_{2k+1} \leq (k+1)C - \dfrac{k(k+1)}2$.

As we want the second sum to be larger, clearly we must have $(k+1)C - \dfrac{k(k+1)}2 > kC + \dfrac{k(k+1)}2$. This simplifies to $C > k(k+1)$.

Hence we get that:

\begin{align*} N & \geq 2(a_1+\cdots + a_k) \\ & \geq 2\left( kC + \dfrac{k(k+1)}2 \right) \\ & = 2kC + k(k+1) \\ & \geq 2k(k^2+k+1) + k(k+1) \\ & = 2k^3 + 3k^2 + 3k \end{align*}

On the other hand, for the set $\{ k^2+k+1+i ~|~ i\in\{-k,\dots,k\} \, \}$ the sum of the largest $k$ elements is exactly $k^3 + k^2 + k + \dfrac{k(k+1)}2$, and the sum of the entire set is $(k^2+k+1)(2k+1) = 2k^3 + 3k^2 + 3k + 1$, which is more than twice the sum of the largest set.

Hence the smallest possible $N$ is $\boxed{ N = 2k^3 + 3k^2 + 3k }$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

  • <url>viewtopic.php?t=84550 Discussion on AoPS/MathLinks</url>
2006 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_USAMO_Problems/Problem_2&oldid=62736"