Question

Del conjunto de enteros $\{1, 2, 3, \ldots, 2009\},$ elige $k$ pares $\{a_i, b_i\}$ con $a_i \lt b_i$ de modo que no haya dos pares con un elemento común. Supón que todas las sumas $a_i + b_i$ son distintas y menores o iguales que $2009.$ Halla el máximo valor posible de $k.$

From the set of integers $\{1, 2, 3, \ldots, 2009\},$ choose $k$ pairs $\{a_i, b_i\}$ with $a_i \lt b_i$ so that no two pairs have a common element. Suppose that all the sums $a_i + b_i$ are distinct and less than or equal to $2009.$ Find the maximum possible value of $k.$

Respuesta

Solución:

Sea $S = \sum_{i=1}^{k} (a_i + b_i).$ Los $2k$ elementos elegidos son enteros positivos distintos, así que $S \ge 1 + 2 + \cdots + 2k$ $= k(2k + 1).$ Las $k$ sumas son enteros distintos a lo sumo $2009,$ así que $S \le 2009 + 2008 + \cdots$ ${}+ (2010 - k)$ $= \frac{k(4019 - k)}{2}.$ Combinando, $\begin{aligned} &k(2k + 1) \le \frac{k(4019 - k)}{2} \\ &\implies 4k + 2 \le 4019 - k \\ &\implies k \le \frac{4017}{5} = 803.4, \end{aligned}$ así que $k \le 803.$

Para alcanzar $k = 803,$ toma los pares $(i,\, 1206 + i)$ para $1 \le i \le 401,$ cuyas sumas son los números pares $1208, 1210, \ldots, 2008,$ junto con los pares $(a,\, a + 403)$ para $402 \le a \le 803,$ cuyas sumas son los números impares $1207, 1209, \ldots, 2009.$ Los elementos usados son del $1$ al $803,$ y del $805$ al $1607$ , sin repeticiones, y las $803$ sumas son todas distintas y a lo sumo $2009.$

El máximo es $k = 803.$

Let $S = \sum_{i=1}^{k} (a_i + b_i).$ The $2k$ chosen elements are distinct positive integers, so $S \ge 1 + 2 + \cdots + 2k$ $= k(2k + 1).$ The $k$ sums are distinct integers at most $2009,$ so $S \le 2009 + 2008 + \cdots$ ${}+ (2010 - k)$ $= \frac{k(4019 - k)}{2}.$ Combining, $\begin{aligned} &k(2k + 1) \le \frac{k(4019 - k)}{2} \\ &\implies 4k + 2 \le 4019 - k \\ &\implies k \le \frac{4017}{5} = 803.4, \end{aligned}$ so $k \le 803.$

To achieve $k = 803,$ take the pairs $(i,\, 1206 + i)$ for $1 \le i \le 401,$ whose sums are the even numbers $1208, 1210, \ldots, 2008,$ together with the pairs $(a,\, a + 403)$ for $402 \le a \le 803,$ whose sums are the odd numbers $1207, 1209, \ldots, 2009.$ The elements used are $1$ – $803,$ $805$ – $1607$ with no repeats, and all $803$ sums are distinct and at most $2009.$

The maximum is $k = 803.$

2009 AIME II Problema 12

Solución:

El Problema 12 en otros años