Problema 2 Nivel 2 Mayo 2019

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 312
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 4
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Problema 2 Nivel 2 Mayo 2019

Mensaje sin leer por Turko Arias » Vie 26 Jul, 2019 4:07 am

Se tiene un tablero con $2020$ casillas en la fila inferior y $2019$ en la superior, ubicadas como se muestra en la figura.

En la fila inferior se colocan los números enteros del $1$ al $2020$ en algún orden. Luego en cada casilla de la fila superior se anota la multiplicación de los dos números que tiene debajo. ¿Cómo se pueden colocar los números en la fila inferior para que la suma de los números de la fila superior sea lo menor posible?

Imagen

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 208
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Re: Problema 2 Nivel 2 Mayo 2019

Mensaje sin leer por BrunZo » Vie 26 Jul, 2019 12:21 pm

Solución:
Spoiler: mostrar
Básicamente, sea $a_1, a_2, a_3,\dots, a_{2020}$ una permutación de $\{1,2,3,\dots, 2020\}$. Queremos maximizar $a_1a_2+a_2a_3+\dots+a_{2019}a_{2020}$.
Para eso, escribimos:
$$a_1a_2+a_2a_3+\dots+a_{2019}a_{2020}=(a_1a_2+a_3a_4+a_5a_6+\dots a_{2019}a_{2020})+(a_2a_3+a_4a_5+a_6a_7+\dots a_{2018}a_{2019})$$
Por rearrangment inequality, se cumple que
$$a_1a_2+a_3a_4+a_5a_6+\dots a_{2019}a_{2020}\geq 1\cdot 2020+2\cdot 2019+3\cdot 2018+\dots+1010\cdot 1011$$
con igualdad si y sólo si $a_i+a_{i+1}=2021$ para todo $i\leq 2019$ impar. Además,
$$a_2a_3+a_4a_5+a_6a_7+\dots a_{2018}a_{2019}\geq 1\cdot 2018+2\cdot 2017+3\cdot 2016+\dots+1009\cdot 1010$$
con igualdad si y sólo si $a_i+a_{i+1}=2019$ para todo $i\leq 2018$ par y además $a_1$ y $a_{2020}$ son $2019$ y $2020$, en algún orden. En particular
$$a_1a_2+a_2a_3+\dots+a_{2019}a_{2020}\geq (1\cdot 2020+2\cdot 2019+3\cdot 2018+\dots+1010\cdot 1011)+(1\cdot 2018+2\cdot 2017+3\cdot 2016+\dots+1009\cdot 1010)=1371695140$$
con igualdad si y sólo si se cumplen ambas condiciones anteriores. Veamos que la sucesión
$$2020,1,2018,3,2016,5,2014,7,2012,9,\cdots 6,2015,4,2017,2,2019$$
cumple ambas condiciones, luego minimiza la suma.

Responder