Cono Sur 2006 P3

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata FOFO 8 años - Medalla Especial
Mensajes: 160
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 5
Nivel: 2

Cono Sur 2006 P3

Mensaje sin leer por Matías » Mié 25 Jul, 2018 6:38 pm

Sea $n$ un número natural. La sucesión finita $a$ de enteros positivos tiene, entre sus términos, exactamente $n$ números distintos ($a$ puede tener números repetidos). Además, si a uno cualquiera de sus términos se le resta $1$, se obtiene una sucesión que tiene, entre sus términos, al menos $n$ números positivos distintos. ¿Cuál es el valor mínimo que puede tener la suma de todos los términos de la sucesión $a$?

juandodyk
Mensajes: 14
Registrado: Mar 26 Jun, 2018 1:59 am
Nivel: Exolímpico

Re: Cono Sur 2006 P3

Mensaje sin leer por juandodyk » Vie 27 Jul, 2018 6:41 pm

Spoiler: mostrar
Sea $b_k$ la cantidad de veces que aparece el número $k$ en la secuencia. Si $b_k\geqq 2$ y restamos $1$ a un término $k$, sigue habiendo otro término $k$, y quizás ahora aparece otro término positivo $k-1$, por lo que sigue habiendo al menos $n$ números positivos distintos. Si $b_k=1$ y restamos $1$ al único término $k$, hay un número positivo menos; para compensar, $k-1$ debe ser positivo y distinto al resto, es decir, $k$ debe ser al menos $2$ y $b_{k-1}=0$.

La suma de los términos de la sucesión $a$ es $\sum_k kb_k$, ya que el número $k$ se suma exactamente $b_k$ veces. Buscamos, pues, una sucesión de enteros no negativos $(b_k)$ tal que $(1)$ entre ellos hay exactamente $n$ números positivos, $(2)$ si $b_k=1$ entonces $k\geqq2$ y $b_{k-1}=0$, y $(3)$ minimiza $\sum_k kb_k$.

Si $b_k\geqq 3$ lo cambio por $b_k=2$, sigo cumpliendo $(1)$ y $(2)$ y tengo $\sum_k kb_k$ menor, así que no puede suceder.

No puede haber dos $0$ consecutivos y un número positivo después. En efecto, si $b_k = b_{k+1} = 0$, formamos otra secuencia $b'$ con $b'_i = b_i$ para $i\leqq k$ y $b'_i=b_{i+1}$ para $i\geqq k+1$. Claramente cumple $(1)$ y $(2)$, y $\sum_i ib'_i = \sum_{i\leqq k} ib_i + \sum_{i\geqq k+2} (i-1)b_i < \sum_i ib_i$. Por el mismo argumento no puede haber un $0$ y un $2$ después. Entonces luego de un $0$ hay un $1$ o no hay más números positivos.

No puede darse $(b_k, b_{k+1}, b_{k+2}) = (0,1,2)$. En efecto, sea $b'$ igual a $b$ excepto que $(b'_k, b'_{k+1}, b'_{k+2}) = (2,0,1)$. Claramente cumple $(1)$ y $(2)$, pero $\sum_i ib_i - \sum_i ib'_i = (k+1)+2(k+2) - 2k-(k+2) = 3 > 0$.

Entonces si miro $b_1,\ldots,b_K$, donde $b_K$ es el último positivo, sólo contiene números $0,1,2$, y las apariciones de $0$ o $1$ se dan en bloques $(0,1)$, que no tienen $2$ a la derecha. En resumen, la sucesión es de la forma $\underbrace{2, \ldots, 2}_r, \underbrace{0,1, \ldots, 0,1}_s$, donde $s$ es la cantidad de unos, y tenemos $r+s=n$. Entonces hay que minimizar $2(1+\cdots +r) + (r+2) + \cdots + (r+2s) = r(r+1)+rs+s(s+1) = r^2+s^2+rs+r+s = (r+s)^2-rs+(r+s)=n^2-rs+n$. Para ello hay que maximizar $rs$ bajo $r+s=n$. Tenemos $rs \leqq (\frac{r+s}2)^2 = (\frac n2)^2$, luego $rs \leqq \lfloor \frac{n^2}4 \rfloor$. Si $n$ es par ponemos $r=s=\frac n2$ y lo alcanzamos, así que es el máximo. Si $n$ es impar, digamos $n=2t+1$, tenemos $\lfloor \frac{n^2}4 \rfloor = \lfloor \frac{(2t+1)^2}4 \rfloor = \lfloor\frac{4t^2+4t+1}4\rfloor = t^2+t = t(t+1)$, así que ponemos $r=t$ y $s=t+1$ y de nuevo lo alcanzamos. Así que el máximo de $rs$ es $\lfloor \frac{n^2}4 \rfloor$ y el mínimo buscado es $n^2-\lfloor \frac{n^2}4 \rfloor+n$.

Responder