# Difference between revisions of "2006 USAMO Problems/Problem 2"

Line 1: | Line 1: | ||

== Problem == | == Problem == | ||

− | For a given positive integer <math> | + | 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>. |

== Solution == | == Solution == | ||

− | {{ | + | 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>. | ||

== See Also == | == See Also == |

## Revision as of 15:05, 2 February 2009

## Problem

For a given positive integer find, in terms of , the minimum value of for which there is a set of distinct positive integers that has sum greater than but every subset of size has sum at most .

## Solution

Let one optimal set of integers be with .

The two conditions can now be rewritten as and . Subtracting, we get that , and hence . In words, the sum of the smallest numbers must exceed the sum of the largest ones.

Let . As all the numbers are distinct integers, we must have , and also .

Thus we get that , and .

As we want the second sum to be larger, clearly we must have . This simplifies to .

Hence we get that:

On the other hand, for the set the sum of the largest elements is exactly , and the sum of the entire set is , which is more than twice the sum of the largest set.

Hence the smallest possible is .