Problema 2 Nivel 2 Mayo 2019

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

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 412
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 9
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
Fundamentalista del Aire Acondicionado

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 261
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
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