Selectivo EGMO, Perú 2020. Problema 1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Nando

OFO - Mención-OFO 2019
Mensajes: 191
Registrado: Mar 31 Jul, 2018 7:39 pm
Medallas: 1

Selectivo EGMO, Perú 2020. Problema 1

Mensaje sin leer por Nando »

Para un par de conjuntos finitos $A$ y $B$ de números enteros no negativos, definimos $A + B$ como el conjunto de valores obtenidos al sumar un elemento cualquiera de $A$ con un elemento cualquiera de $B$.
Por ejemplo, si $A = \{2, 3\}$ y $B = \{0, 1, 2, 5\}$ entonces $A + B = \{2, 3, 4, 5, 7, 8\}$.
Determine el menor valor de $k$ para el cual existe un par de conjuntos $A$ y $B$ de números enteros no negativos con $k$ y $2k$ elementos, respectivamente, tales que
$$A + B = \{0, 1, 2, 3, . . . , 2019, 2020\}.$$
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Selectivo EGMO, Perú 2020. Problema 1

Mensaje sin leer por Fran5 »

Spoiler: mostrar
Si $A$ tiene $a$ elementos y $B$ tiene $b$ elementos, entonces $A+B$ tiene como mucho $ab$ elementos. Luego queremos que $2k^2 \geq 2021$ de donde $k \geq 32$. Notemos además que $0 \in A$ y $0 \in B$ para que $0 \in A+B$.

Es facil construirse el ejemplo al tomar $A = \{0,64,128,64 \cdot 3, \ldots, 64 \cdot 30, 1957 \}$ y $B = \{0,1,2,3, \ldots, 63\}$.

Todo número de $A+B$ es de la forma $n = 64i+j$ con $0 \leq j \leq 63 $ y $0 \leq i \leq 30$, ó $n=1957+j$ con $0 \leq j \leq 63$, con lo que en ambos casos $0 \leq n \leq 2020$.

Recíprocamente, todo número $0 \leq n \leq 1984$ se escribe como $64q+r$ con $0 \leq q \leq 30$ y $0 \leq r \leq 63$ y todo número $1985 \leq n \leq 2020$ se escribe como $1957+r$ con $0 \leq r \leq 63$.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Responder