Maratón de Problemas

[Fran2001]

Solución 366:

Spoiler: mostrar

Sea $d(n)$ la cantidad de divisores de $n$, es fácil ver que $d(n)$ es impar si y solo si $n$ es un cuadrado perfecto.
Notemos ahora que $f(n)=d(1)+d(2)+\dots +d(n)+\sqrt n$.
Esto puede verse por inducción: para $n=1$ es cierto, y si se cumple para $n=k$, entonces para $n=k+1$ estamos sumando $1$ a los términos de la forma $\lfloor\frac{k+1}a\rfloor$, donde $a|k+1$. Es decir, estamos sumando $d(k+1)$, como queríamos.
Ahora procedamos nuevamente por inducción, notando que $f(1)$ es par. Supongamos que $f(k)$ también lo es. Si $k+1$ es un cuadrado perfecto, entonces $f(k+1)=f(k)+d(k+1)+\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt k\rfloor$.
Notemos que $d(k+1)$ es impar, y que $\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt k\rfloor=1$. Por lo tanto $f(k+1)$ es par.
Si $k+1$ no es un cuadrado perfecto, entonces $d(k+1)$ es par, y $\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt k\rfloor=0$. Por lo tanto $f(k+1)$ sigue siendo par, y estamos.

[Fran2001]

Problema 367:
Hay $2n$ personas sentadas alrededor de una mesa redonda, jugando al psicólogo.
Como no se pueden decir las reglas de este juego, vamos a inventar otro. Supongamos que estas personas tienen en total $m$ precintos.
Puden pasarse los precintos siempre y cuando sigan las siguientes reglas:
a) Cada persona solo puede pasarle precintos a sus vecinos.
b) Cada vez que alguien pasa un precinto, debe tirar otro.
Supongamos que Emi es una de las personas que está jugando.
Como está re manija, quiere terminar el juego teniendo sí o sí un precinto.
Hallar el menor $m$ tal que, sin importar cómo estén distribuidos los precintos al comienzo, hay una estrategia que nos asegura que Emi reciba al menos uno.

[Monazo]

Llamamos a un par de enteros positivos $a$ y $b$ "generadores de cuadrado", si $ab+1$ es un cuadrado perfecto. Determinar para cada $n$ entero positivo si es posible dividir el conjunto $\{1,2,\dots,2n \}$ en $n$ parejas de "generadores de cuadrados".

[BrunZo]

Spoiler: mostrar

Yo digo que esto es posible para todo entero positivo $n$ par, pero para $n$ impar es imposible. Veamos por qué:

La clave que vamos a usar para $n$ par es que $(k-1)(k+1)+1 = k^2$. De este modo, consideremos las parejas:
$$(4k+1, 4k+3),\quad (4k+2, 4(k+1))$$
para algún $k$ entre $0$ y $n/2-1$ (recordemos que $n$ es par). Entonces, notemos que cada pareja es "generadora de cuadrados" y además logramos cubrir todos los números del $1$ hasta el $2n$. Con esto, terminamos un ejemplo para $n$ par.

Ahora, vemos que $n$ impar es imposible:

Tomemos un número $a$ que tenga resto $2$ módulo $4$. Yo digo que si $(a, b)$ es generadora de cuadrados, entonces $b$ es múltiplo de cuatro. Para ver esto, notemos que si es generadora de cuadrados, entonces
$$ab+1=k^2\iff ab=k^2-1=(k-1)(k+1)$$
Ahora bien, como $a$ es par, sabemos que el lado derecho es par, pero $k-1$ y $k+1$ tienen la misma paridad, así que tienen que ser ambos pares. Más aún, sabemos que uno de ellos tiene que ser múltiplo de cuatro, de modo que el producto es múltiplo de $8$. Pero como $a$ no es múltiplo de $4$, para llegar a que el lado derecho sea múltiplo de $8$, necesitamos que $b$ sea múltiplo de $4$, como queríamos demostrar.

Ahora bien, notemos que si $n$ es impar, entonces $2n$ es $2$ módulo $4$, así que en la lista $\{1,2,3,...,2n\}$, hay $\frac{n-1}{2}$ múltiplos de $4$ y $\frac{n+1}{2}$ números que son $2$ módulo $4$. Pero sabemos que cada uno de estos últimos tiene que emparejarse con uno de los primeros, pero $\frac{n+1}{2}>\frac{n-1}{2}$, así que el emparejamiento es imposible.

Problema 368:

En la Ciudad de La Plata, el Intendente está pensando en remodelar su ciudad construyendo algunas plazas. Como bien es sabido, La Plata es una ciudad cuadrada y el Intendente quiere que todas las plazas también sean cuadradas (los lados de cada cuadrado son calles transitables, los bordes de la ciudad también son transitables); y además, al Intendente le gustaría que las plazas no se superpongan y que cubran toda el área de la ciudad (es decir, que no queden huecos sin cubrir). El Arquitecto Mayor, luego de escuchar el proyecto, le dice que para que el trazado sea eficiente, se necesita que se cumpla la siguiente condición: "no puede haber ningún recorrido con forma de cuadrado (a través de calles transitables) en cuyo interior haya más de una plaza; a menos que el recorrido bordee toda la Ciudad". Al Turko, que está muy atento a todas las noticias de su amada Ciudad, le preocupa muchísimo saber cuántas plazas van a quedar después de la remodelación. Determinar todas las posibles cantidades de plazas en las que se puede partir la Ciudad para que se cumplan los requisitos.

[Fran2001]

Solución 367:

Spoiler: mostrar

Fede me hizo notar que este problema ya está en el Foro (es una versión general del Problema 5 de la COFFEE Iván Sadofschi).
Vamos a comenzar numerando a las personas.
Le asignamos a Emi el $0$, y luego a cada persona le asignamos la distancia en personas a la que se encuentra de Emi (por ejemplo, las $2$ personas sentadas al lado de Emi tienen el $1$, y la persona diametralmente opuesta tiene el $n$).
Ahora, para cada precinto que tenga la persona $i$, definimos su peso como $w_i=\frac 1{2^i}$. Así, el peso de cada precinto de Emi es $1$, el peso de cada precinto de sus vecinos es $\frac 12$ y el peso de cada precinto de la persona diametralmente opuesta es $\frac 1{2^n}$.
Ahora basta notar que si una persona $i$ tiene precintos, y pasa alguno a la $i+1$, entonces la suma de los pesos decrece: el peso del precinto que movimos disminuyó, y el peso del precinto que tiramos desapareció.
Además, si la persona $i$ pasa un precinto a la persona $i-1$, la suma de los pesos no varía: teníamos $2$ precintos con peso $\frac 1{2^i}$, y ahora tenemos uno solo con peso $\frac 1{2^{i-1}}$.
Es decir que la suma de los pesos es una monovariante: nunca puede crecer.
Si Emi termina con un precinto, la suma de los pesos en ese momento va a ser al menos $1$. Por lo tanto, si inicialmente el peso total es menor que $1$, no vamos a poder hacerle llegar un precinto a Emi.
Ahora, si tenemos menos de $2^n$ precintos, e inicialmente tiene todos la persona $n$, el peso total inicial va a ser menos de $1$.
Es decir que necesitamos al menos $2^n$ precintos.
Es fácil ver que con $2^n$ precintos siempre vamos a poder hacerle llegar uno a Emi, mirando el lado con mayor peso de la mesa y jugando solo por ese lado.
Por lo tanto $m=2^n$.

[Fran2001]

Problema 368 bis:
Brian tiene $3$ cuentas bancarias, cada una con una cantidad entera de pesos. Tiene permitido transferir plata de una cuenta a la otra, pero de forma que la cantidad de plata de la cuenta que recibe se duplique. Puede realizar esta operación cuantas veces quiera.
Demostrar que Brian siempre puede lograr que toda su plata esté en $2$ cuentas, dejando la otra vacía.

[Fran2001]

Solución 368 bis:

Spoiler: mostrar

Esta solución no es mía, pero me gusta.
Sean $A; B; C$ las cuentas. La idea de la solución demostrar que si $mín\{A; B; C\}\neq 0$, entonces siempre podemos hacerlo más chico.
Si lo miramos un poco, esto de un algoritmo para ir reduciendo enteros tiene pinta de Euclides.
Supongamos que $A\leq B\leq C$, vamos a escribir entonces $B = q\cdot A+r$. Ahora queremos encontrar una serie de operaciones que haga que $B$ quede con $r$ pesos.
Es decir, queremos quitarle $q\cdot A$ pesos a $B$.
Ahora una pequeña motivación para el próximo paso:
¿Podemos quitarle $q\cdot A$ pesos a $B$ directamente?
Está claro que esto lo podemos hacer si y solo si $q$ es potencia de $2$. Entonces, si $q$ no es potencia de $2$, vamos a tener que hacer algunos pasos intermedios.
No tendría sentido que pasemos de $B$ a $C$ o de $A$ a $C$, porque nos cambiaría $B$ o $A$ de alguna forma extraña, y estamos viendo la división de $B$ por $A$. Tampoco tendría mucho sentido que pasemos de $C$ a $B$, porque estaríamos aumentando $B$. O sea que los únicos pasos que vamos a hacer son de $B$ a $A$ y de $C$ a $A$.
Notemos que en cada paso de $B$ a $A$ o de $C$ a $A$, esta última se duplica.
Es decir que en cada paso de $B$ a $A$, si previamente hicimos $k$ pasos a $A$ (desde $B$ o $C$), estamos pasando $2^k\cdot A$ pesos.
Y esto nos pide a gritos que expresemos a $q$ en su desarrollo binario.
Así, si $b_nb_{n-1}\dots b_0$ es $q$ expresado en binario, para en el paso $k$ vamos pasar de $B$ a $A$ si $b_k=1$, y vamos a pasar de $C$ a $A$ si $b_k=0$ (notemos que esto siempre podemos hacerlo, ya que inicialmente $C\geq B$).
Luego de $n$ pasos, habremos pasado $(b_n\cdot 2^n+b_{n-1}\cdot 2^{n-1}+\dots +b_0\cdot 2^0)\cdot A=q\cdot A$ pesos de $B$ a $A$, y estamos.

Queda abierto para que proponga el que quiera.

[Emerson Soriano]

Problema 369

Encontrar todas las funciones $f:\mathbb{N}\to \mathbb{N}$ tales que, para cualesquiera números enteros positivos distintos $x$, $y$, $z$, el número $x+y+z$ es un cuadrado perfecto si y sólo si $f(x)+f(y)+f(z)$ es un cuadrado perfecto.

Aclaración. $\mathbb{N}$ es el conjunto de todos los enteros positivos.

[BrunZo]

Spoiler: mostrar

Vamos a usar el siguiente minilema:

Minilema: Dadas constantes $A\neq B$, la cantidad de soluciones enteras de $X^2-A=Y^2-B$ es finita.
Demostración: La igualdad es equivalente a $A-B=X^2-Y^2=(X-Y)(X+Y)$. Sea $p=X-Y, q=X+Y$, entonces vale que $X=\frac{p+q}{2}$ e $Y=\frac{q-p}{2}$ que es solución solo si $p$ y $q$ tienen la misma paridad. Pero además, necesitamos que $pq=A-B$, y como $A-B\neq 0$, tiene una cantidad finita de divisores, por lo que hay una cantidad finita de pares ordenados $(p,q)$, de donde se concluye en minilema.

Ahora sí, vamos al problema. Para todo $N$ natural, vamos a denotar por $S_N$ al conjunto de $x$ naturales con $f(x)=N$.

Proposición 1: $S_N$ es finito para todo $N$
Demostración: Supongmos que $S_N$ tiene al menos $2$ elementos (si no ya terminamos). Tomemos tres elementos $a, b, c\in S_N$ con $b\neq c$. Fijemos un $z$ tal que $a+b+z$ sea un cuadrado. Entonces, $f(a)+f(b)+f(z)=2N+f(z)$ es un cuadrado. Más aún, para todo $x\in S_N$ vale que $f(x)+f(b)+f(z)=2N+f(z)$ es un cuadrado, luego $x+b+z$ es un cuadrado para todos estos $x$. Entonces, todos los $x\in S_N$ son de la forma $X^2-(b+z)$ para algún $X$ entero.
Similarmente, vale que $f(x)+f(c)+f(z)=2N+f(z)$ siempre es un cuadrado, luego todos los $x\in S_N$ son de la forma $Y^2-(c+z)$ con $Y$ entero.
En consecuencia, $x=X^2-(b+z)=Y^2-(c+z)$, pero como $b+z\neq c+z$, por el minilema sabemos que esto tiene una cantidad finita de soluciones, por lo que el conjunto $S_N$ no puede ser infinito.

Proposición 2: Si $x+y=x'+y'$, entonces $f(x)+f(y)=f(x')+f(y')$.
Demostración: Supongamos que $f(x)+f(y)=s\neq s'=f(x')+f(y')$. Consideremos $z=K^2-(x+y)=K^2-(x'+y')$ para todo $K$ entero positivo lo suficientemente grande. Sabemos que $x+y+z=x'+y'+z$ son cuadrados y en consecuencia $s+f(z)=X^2$ y $s'+f(z)=Y^2$ con $X$ e $Y$ enteros, pero otra vez, por el minilema $f(z)=X^2-s=Y^2-s'$ tiene una cantidad finita de soluciones, así que $f(z=K^2-(x+y))$ solo recorre una cantidad finita de valores. Pero como podemos tomar infinitos $K$, tenemos infinitos posibles $z$ que adentro de la $f$ nos dan una cantidad finita de valores, luego una cantidad infinita de los $z$ nos tiene que dar el mismo valor, lo cual contradice la prop 1. Luego efectivamente $s=s'$.

Ahora bien, como $1+n=2+(n-1)$, entonces $f(n)-f(n-1)=f(2)-f(1)$, de donde se sigue que $f(n)$ tiene que ser lineal (ya que está definida solo en los naturales). Es decir, $f(x)=mx+b$ con $m, b$ enteros. De este modo, la condición se transforma en $x+y+z$ es un cuadrado si y solo si $m(x+y+z)+3b$ lo es. Pero $x+y+z=s$ toma todo valor entero mayor o igual a $3$, luego decimos que para todo $s\geq 3$, $ms+3b$ es un cuadrado perfecto si y solo si $s$ lo es. (*)

Ya acá viene la parte engorrosa: notemos que $ms+3b$ recorre todos los números congruentes a $3b$ módulo $m$. Supongamos primero que $m$ no divide a $3b$. Entonces, si $u_0^2$ es el primer cuadrado con resto $3b\not\equiv 0$, vale que los siguientes son, en orden, $(m-u_0)^2$, $(m+u_0)^2$, $(2m-u_0)^2$, etcétera. Sean $s_1$ y $s_2$ tales que $ms_1+3b=(m-u_0)^2$, $ms_2+3b=(m+u_0)^2$. Entonces vale que $s_2-s_1=4u_0$. Por (*), sabemos que $s_1$ y $s_2$ pueden ser $1$, $2$, $4$, $9$, $16$ (a partir de $s\geq 3$ no pueden ser no cuadrados; si $0$ diese cuadrado, sería el primero, pero $s_1$ y $s_2$ son segundo y tercero; y como $4$, $9$ y $16$ sí o sí tienen que dar un cuadrado, $s_2$, que es el tercero que da un cuadrado, cumple $s_2\leq 16$). Entonces, solo hay dos posibles diferencias múltiplos de $4$: $s_1=1$ y $s_2=9$ o $s_1=4$ y $s_2=16$. La segunda es imposbile ya que si $4$ fuese el segundo en dar cuadrado, como $9$ da cuadrado sí o sí, éste último tendría que ser $s_2$. Si se diese la primera, $u_0=2$ y necesariamente $3b$ sería el primer cuadrado, o sea $3b=u_0^2=4$, lo cual es absurdo. En consecuencia, el caso en el que $m$ no divide a $3b$ es imposible.

Falta el caso en el que $3b=mk$ y nos queda que $m(s+k)$ recorre todos los múltiplos de $m$. Ahora, si $l^2$ es el primer cuadrado positivo múltiplo de $m$ (digamos $l^2=mj$, vale que $j$ es libre de cuadrados), los cuadrados que son múltiplos de $m$ son $0$, $l^2$, $(2l)^2$, $(3l)^2$, etcétera. Entonces, si $s_i$ y $s_{i+1}$ dan dos cuadrados consecutivos, vale que $s_{i+1}-s_i=(2i+1)j$. Pero sabemos que $4, 9, 16$ dan cuadrados consecutivos, así que $(2i+1)j$ toma los valores $5, 7$ en ese orden, de donde necesariamente $j=1$. O sea, $m=l^2$ es un cuadrado perfecto, y entonces $l^2(s+k)$ es cuadrado si y solo si $s+k$ lo es. Pero, usando el minilema por última vez, si $k\neq 0$, entonces $s+k$ y $s$ solo pueden ser cuadrados en simultáneo una cantidad finita de veces, lo cual contradice (*). En definitiva, $k=0$ y nos queda que $b=0$ y $m=l^2$, lo que nos da $f(x)=l^2x$.

Y bueno, para terminar, notemos que $f(x)=l^2x$ funciona para cualquier $l$ entero positivo, ya que $x+y+z$ es cuadrado si y solo si $l^2(x+y+z)$ lo es. Con esto, finalizamos el problema.

En caso de que esté bien (bastante dudoso) replanteo el problema 368, que todavía no fue resuelto:

Problema 370:

En la Ciudad de La Plata, el Intendente está pensando en remodelar su ciudad construyendo $n\geq 2$ plazas. Como bien es sabido, La Plata es una ciudad cuadrada y el Intendente quiere que todas las plazas también sean cuadradas (los lados de cada cuadrado son calles transitables, los bordes de la ciudad también son transitables); y además, al Intendente le gustaría que las plazas no se superpongan y que cubran toda el área de la ciudad (es decir, que no queden huecos sin cubrir). El Arquitecto Mayor, luego de escuchar el proyecto, le dice que para que el trazado sea eficiente, se necesita que se cumpla la siguiente condición: "no puede haber ningún recorrido con forma de cuadrado (a través de calles transitables) en cuyo interior haya más de una plaza; a menos que el recorrido bordee toda la Ciudad". Al Turko, que está muy atento a todas las noticias de su Ciudad, le preocupa muchísimo saber cuántas plazas van a quedar después de la remodelación. Determinar todas las posibles cantidades de plazas en las que se puede partir la Ciudad para que se cumplan los requisitos.

Pista:

Spoiler: mostrar

Se pueden todos los enteros $n\geq 4$ excepto el $5$.

[Juaco]

Spoiler: mostrar

esto esta muy relacionado (creo) con la cuadratura del cuadrado y sus derivados. En Internet hay muchas versiones agregando o quitando restricciones, se pueden encontrar Muchas fácilmente.

Vamos a dividir en $4$ partes:

es posible para todo $n $ impar tal que $n \geq 13$:

Spoiler: mostrar

vamos a dividir el cuadrado grande (la ciudad completa) en 4 rectángulos de $n × (n+1) $ y un cuadrado central de $1 × 1$ de la siguiente manera:

Screenshot_2021-05-22-15-54-33-1.png

Ahora esos rectángulos los dividimos en cuadrados así

Screenshot_2021-05-22-15-53-51-1.png

Ahora quedan claramente $2 (2n + 2) + 1$ cuadrados y obviamente el caso en que los rectángulos iniciales son de $2×1$ no se puede por lo que el mínimo es $13$ (cuando elo rectángulo es de $2 × 3$) y para todos los demás también se va a poder

es posible para todo $n$ par tal que $n \geq 4$:

Spoiler: mostrar

la imagen con la configualación lo dice todo:

Screenshot_2021-05-22-15-59-13-1.png

los casos para $n = \{2; 3; 5\} $ no se pueden:

Spoiler: mostrar

vamos primero a ver que $n $ no puede ser menor que $4$, esto es porque para cada esquina del cuadrado grande (que tiene $4$ esquinas) tiene que haber un cuadrado por lo que si $n < 4$ entonces por palomar va a haber un cuadrado que ocupe $2$ esquinas y por tanto todas, entonces esos casos no se pueden.
Vamos ahora con $n = 5$:
los lados de los cuadrados chicos por supuesto no pueden superar la mitad del lado del cuadrado grande, pero vamos a ver que pasa si son más chicos:
1) si quedan espacios entre todos entonces lo que falta para llenar el cuadrado es una figura cóncava y por tanto no se puede llenar con un solo cuadrado
2) vemos ahora que si $2$ cuadrados "opuestos" tienen medida del lado la mitad del grande entonces quedan $2$ regiones separadas (cuadradas) y por lo tanto en alguno de esos $2$ cuadrados va a haber $2$ cuadrados lo que contradice la condición del arquitecto mayor, y si los $2$ cuadrados de lado la mitad del grande son adyacentes entonces pasa lo mismo que en el primer caso (Lo que falta para llenar el cuadrado es una figura concava)
3) para terminar, si 3 cuadrados tienen longitud un medio (asumiendo que el grande tiene longitud $1$) entonces pasa lo mismo que en la parte de los "cuadrados opuestos"

esto muestra que $n = 5$ no es una posibilidad
ahí adjunto unas imágenes para que se vea claro:

Screenshot_2021-05-22-16-10-34-1.png

Screenshot_2021-05-22-16-13-50-1.png

Screenshot_2021-05-22-16-15-05-1.png

El ultimo caso son los valores restantes de $n $ que son $7, 9, 11$:

Spoiler: mostrar

como son pocos basta con dar ejemplos de configuraciones que cumplan los requisitos y ahí van las imagenes:

Screenshot_2021-05-22-16-26-04-1.png

Screenshot_2021-05-22-16-36-08-1.png

Screenshot_2021-05-22-17-14-53-1.png

Buenos ahí están probados todos los casos, la respuesta es, como decía ya de antemano el problema, todos los enteros mayores que $3$ menos el $5$

Bueno, ahora que veo, en los impares sólo demostré para los casos $n \equiv 1 (4) $ y me faltan los otros, $n \equiv 3 (4) $

De todos modos, es sabido que en el problema de los cuadrados de cuadratura simple y la colcha de la señora Perkins el mínimo es $n = 21$ y para todos los mayores se puede, pero ese mínimo es con la restricción de que todos los cuadrados sean de tamaños diferentes, para lo demás, solo faltan unos pocos casos que se pueden hacer a mano, para todos los $n $ impares tales que $19 \geq n \geq 7$ ya tengo las posibles configuraciones que eran mi solución original, así que las puedo subir luego, solo tengo que hacerlas prolijas