Rioplatense 2022 - N2 P5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Rioplatense 2022 - N2 P5

Mensaje sin leer por Matías V5 »

Sea $n$ un entero positivo. Con los números enteros del $1$ al $4n$ inclusive se quiere formar parejas, de manera que en cada una de ellas el producto de los números sea un cuadrado perfecto. Cada número puede estar en a lo sumo una pareja y los dos números de cada pareja deben ser diferentes.
Determine para cada $n$ la máxima cantidad de parejas que se pueden formar.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: Rioplatense 2022 - N2 P5

Mensaje sin leer por enigma1234 »

Spoiler: mostrar
Sea $f(n)$ el número pedido para cada $n$. Sea $j:\mathbb{N}\to \{0,1\}$ tal que $j(k)=1$ si $k$ es libre de cuadrados, y $j(k)=0$ si $k$ no es libre de cuadrados.

Sea $S=\{1,2,\dots,4n\}$. Definamos para $k\in \mathbb{N}$ el conjunto: $A_k=\{k,2^2k,3^2k,..\}\cap S$ si $j(k)=1$ y $A_k=\emptyset$ si $j(k)=0$.

Lema 1: $A_1,A_2,\dots, A_{4n}$ tienen unión $S$ y son disjuntos dos a dos. ($A_1,A_2,\dots, A_{4n}$ es una partición de $S$)
Spoiler: mostrar
Puesto que cada número $1\leq m\leq 4n$ puede ser escrito como $m=m_1^2\times m_2$ con $j(m_2)=1$ y $1\leq m_2\leq m\leq 4n$ de manera única, luego $\cup_{i=1}^{4n} A_k=S$. (y al ser única esta forma de descomponer cada $m$, $A_1, A_2\dots, A_{4n}$ son disjuntos dos a dos)
Lema 2: $f(n)=\sum_{k=1}^{4n} \left\lfloor\frac{|A_k|}{2}\right\rfloor$
Spoiler: mostrar
Es claro ver que para una pareja $(a,b)$ tal que $1\leq a\neq b\leq 4n$:
$ab$ es un cuadrado $\iff$ $a,b$ están en el mismo conjunto $A_k$ en la partición de $S$.
Luego, el problema nos pide hallar la cantidad máxima de parejas de manera que los números en la misma pareja están en el mismo conjunto $A_k$. Claramente esto es igual a $\sum_{k=1}^{4n} \left\lfloor\frac{|A_k|}{2}\right\rfloor$.
Lema 3: $\left\lfloor\frac{|A_k|}{2}\right\rfloor=j(k)\times \left\lfloor\sqrt{\frac{n}{k}}\right\rfloor$ para todo $1\leq k\leq 4n.$
Spoiler: mostrar
Si $j(k)=0$, tenemos $|A_k|=0$ asi que la igualdad es cierta.
Si $j(k)=1$, sea $A_k=\{k,2^2\times k,\dots,L^2\times k\}$. Luego $|A_k|=L$, donde $L$ cumple que $L^2\times k\leq 4n< (L+1)^2\times k$, es decir $L=\left\lfloor\sqrt{\frac{4n}{k}}\right\rfloor$.
Luego: $$\left\lfloor\frac{|A_k|}{2}\right\rfloor=\left\lfloor\frac{\left\lfloor\sqrt{\frac{4n}{k}}\right\rfloor}{2}\right\rfloor= \left\lfloor\frac{\sqrt{\frac{4n}{k}}}{2}\right\rfloor=\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=j(k)\times \left\lfloor\sqrt{\frac{n}{k}}\right\rfloor,$$
donde la segunda igualdad es cierta debido a que $\left\lfloor\frac{\left\lfloor x\right\rfloor}{2}\right\rfloor= \left\lfloor\frac{x}{2}\right\rfloor$ para todo $x$ real.
Lema 4: $f(n+1)-f(n)=\sum_{k=1}^{n+1} j(k)\times \left(\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor\right)$ para todo $n\geq 1$.
Spoiler: mostrar
Primero veamos que $$f(n)=\sum_{k=1}^{4n} j(k)\times \left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=\sum_{k=1}^{n} j(k)\times \left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=\sum_{k=1}^{n+1} j(k)\times \left\lfloor\sqrt{\frac{n}{k}}\right\rfloor,$$ pues $\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=0$ para $n+1\leq k\leq 4n$.
Luego:
$$f(n+1)-f(n)=\sum_{k=1}^{n+1} j(k)\times \left(\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor\right)$$
Sea $1\leq l\leq 4n$ tal que $n+1\in A_l$. Como $n+1=l\times m^2$ para cierto $m$, luego $l\leq n+1$.

Lema 5: $B(k)=j(k)\times \left(\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor\right)= 0$ para todo $1\leq k\leq n+1, k\neq l$, y $B(l)=1$.
Spoiler: mostrar
Como:
$$0\leq \left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor < \sqrt{\frac{n+1}{k}}+1-\sqrt{\frac{n}{k}}\leq n+1+1-n=2,$$
entonces $\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=0$ o $1$.

Supongamos que $\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=1$. Luego, si $\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor=m$, entonces:

$$\sqrt{\frac{n}{k}} <m\leq \sqrt{\frac{n+1}{k}}\to n<k\times m^2\leq (n+1)\to \text{$k\times m^2=n+1$}\to k\in A_l $$

Luego, si $B(k)\neq 0$, tenemos que $j(k)\neq 0\to j(k)=1$ y $\left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor\neq 0\to \left\lfloor\sqrt{\frac{n+1}{k}}\right\rfloor-\left\lfloor\sqrt{\frac{n}{k}}\right\rfloor=1\to k\in A_l$ y $B(k)=1$.
Como $k\in A_l$ y $j(k)=1$, luego necesariamente $k=l$, obteniendo lo querido.
Por lo tanto, como $f(n+1)-f(n)=\sum_{k=1}^{n+1} B(k)=B(l)=1$ para todo $n\geq 1$, entonces $f(n)=f(1)+n-1=n$, debido a que claramente $f(1)=1$.
Responder