Maratón de Problemas

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 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 985
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran5 »

NicoRicci escribió:
Sab 21 Nov, 2020 8:50 am
Solución 362
Spoiler: mostrar
$n = 6$______$c_1 \leftarrow c_2 \leftarrow c_3 | c_4 \leftarrow c_5 | c_6$
No sé si entendí bien el problema (es medio raro :P )

Qué pasaría si
Spoiler: mostrar
$c_2 \leftarrow c_1$
???
No podríamos poner entonces $c_4 \leftarrow c_5 | c_6 | c_1 \leftarrow c_2 \leftarrow c_3$
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

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: 288
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: Maratón de Problemas

Mensaje sin leer por BrunZo »

Fran5 escribió:
Sab 21 Nov, 2020 4:37 pm
No sé si entendí bien el problema (es medio raro :P )

Qué pasaría si
Spoiler: mostrar
$c_2 \leftarrow c_1$
???
No podríamos poner entonces $c_4 \leftarrow c_5 | c_6 | c_1 \leftarrow c_2 \leftarrow c_3$
Perdón por meterme, jajaj
Spoiler: mostrar
No sé si te entendí bien, pero para mí lo que el quiso decir al fin y al cabo es que siempre existe la partición una partición en cadenas por dos razones:
  • No puede haber ciclos.
  • No puede haber dos que apunten al mismo punto.
Así que hay cadenas y dentro de cada cadena el orden está determinado, así que solo te importa como ordenar las cadenas, que es $k!$ donde hay k cadenas.
Ahora sí, he creado un monstruo...
Spoiler: mostrar
Vamos a agregar cosas, :p

Sean $E$ y $F$ en $AB$ tales que $AD=DE$ y $AC=CF$. Sea $A'$ la reflexión de $A$ por $BC$. Por último, sea $B'$ en $AB$ tal que $A'B=A'B$.
Genial...

geogebra-export (1).png

Ahora vamos a transformar la condición en algo potable de la forma más horripilante posible:
Denotemos por $l$ a $AB$. Entonces, nos consta que, como $P$ y $Q$ están dentro del lado, $BP=l-AP$ y $BQ=l-AQ$. De este modo, la condición se vuelve:
$$AP^2+3(l-AP)^2=4AP^2-6l\cdot AP+3l^2=(2AP)^2-3l(2AP)+3l^2=k$$
$$AQ^2+3(l-BQ)^2=4AQ^2-6l\cdot AQ+3l^2=(2AQ)^2-3l(2AQ)+3l^2=k$$
Pero entonces la cuadrática $P(x)=x^2-3l x+3l^2-k$ tiene como raíces a $2AP$ y a $2AQ$, por lo que $P(x)=(x-2AP)(x-2AQ)=x^2-(2AP+2AQ)x+4AP\cdot AQ$, así que $2AP+2AQ=3l$ (estoy seguro que existen mejores formas de deducir esto de la igualdad dada... pero es lo que hay, jaja)
Bueno y con esto solo falta notar que en realidad $AF=2AP$ y $AE=2AQ$, así que lo que en realidad tenemos es que
$$AE+AF=3l$$
Pero bueno, una sutileza acá, como $P$ y $Q$ esaban en el lado, $AE<2l$ y $AF<2l$, por lo que $AE>l$ y $AF>l$, así que los punto aparecen en el orden $A$, $B$, $F$, $E$.

Ahora, sí, empieza lo bueno:
Como $AC=CF=CA'$, vale por ángulo central que $\angle A'CF=2\angle A'AF$. Pero similarmente $\angle A'DE=2\angle A'AE=\angle A'AF$, de modo que los triángulos isósceles $A'CF$ y $A'DE$ tienen el mismo ángulo, así que son congruentes y $A'E=A'F$. Pero sabiendo esto, sabemos que los pares $E$, $F$ y $B$, $C$ son simétricos con respecto al pie de la perpendicular a $BC$ por $A'$, de modo que $B'E=BF$, pero entonces: (!)
$$AE+AF=AB+BE+AB+BF=2AB+BE+B'E=2l+BB'$$
Pero entonces, como sabíamos que lo primero es igual a $3l$, entonces sabemos que $BB'=l$. Pero bueno, por reflexión sabemos que $A'B=AB=l$ y por definición sabemos que $A'B=A'B'=l$, con lo que vemos que $BA'B'$ es equilátero (!!)
De esto se sigue que $\angle A'BB'=60^{\circ}$, de donde $\angle ABA'=120^{\circ}$ y entonces, por reflexión $\angle ABC=60^{\circ}$ (!!!)

Por fin.
Dejo abierto para que otro proponga.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

No vengo a proponer nada, solamente a dejar una solución menos monstruosa
Spoiler: mostrar
Nacional 2016 - N2 P2
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

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 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 985
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran5 »

BrunZo escribió:
Sab 21 Nov, 2020 8:03 pm

Perdón por meterme, jajaj
Spoiler: mostrar
No sé si te entendí bien, pero para mí lo que el quiso decir al fin y al cabo es que siempre existe la partición una partición en cadenas por dos razones:
  • No puede haber ciclos.
  • No puede haber dos que apunten al mismo punto.
Así que hay cadenas y dentro de cada cadena el orden está determinado, así que solo te importa como ordenar las cadenas, que es $k!$ donde hay k cadenas.
No hay por qué, siempre viene bien aclarar la situación del problema.
Spoiler: mostrar
No veía obvio por qué no podría haber un ciclo
Por ejemplo, que $c_1 \leftarrow c_2$ implica que necesariamente tiene que estar $c_1$ antes que $c_2$? O puede $c_2$ cantar primero sin que haya problema?
Si es como vos decís (no puede haber ciclos) entonces toda cadena necesariamente "termina" en algún cantante sin preferencia, ya que necesariamente alguien debería comenzar a cantar en cada ciclo!
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

Bueno, ahora sí vengo a proponer

Problema 364
Sean $a,b,c$ enteros distintos, y sea $P$ un polinomio de coeficientes enteros.
Demostrar que $P(a)=b$, $P(b)=c$ y $P(c)=a$ no pueden cumplirse todas al mismo tiempo.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

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 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 985
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran5 »

Solución 364
Spoiler: mostrar
Voy a usar el hecho de que $x-y$ divide a $P(x)-P(y)$ para cualesquiera $x,y$ enteros.

Esto es $a-b | P(a)-P(b)$

Pero $P(a)-P(b) = b-c$, con lo que $a-b | b-c$

Análogamente es $b-c | c-a $ y $c-a | a-b$

Pero sabemos que es imposible que tres enteros distintos se dividan entre si!
Problema 365

Para qué números $n$ es $\frac{1}{n+1} \binom{2n}{n}$ un entero impar?
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

Solución 365
Spoiler: mostrar
Primero que nada, los números siempre son enteros porque son los números de Catalan.
Ahora vamos a reventar el problema con valuaciones (no hay que asustarse, es solamente ver el exponente de $2$ en la factorización de todo el número, eso se simboliza con $\nu _2$). Como tiene que ser impar y es entero, lo que queremos es que su $\nu _2$ sea $0$$$\begin{align*}\nu _2\left (\frac{1}{n+1}\binom{2n}{n}\right )=0 & \iff \nu _2 \left (\binom{2n}{n}\right )-\nu _2(n+1)=0 \\
& \iff \nu _2\left (\frac{(2n)!}{n!n!}\right )=\nu _2(n+1) \\
& \iff \nu _2((2n)!)-2\nu _2(n!)=\nu _2(n+1)
\end{align*}$$por Legendre$$\nu _2(k!)=k-s_2(k)$$donde $s_2(k)$ es la suma de los dígitos de $k$ en base $2$ (esta es la única parte verdaderamente teórica de la solución). Luego, queremos ver que$$2n-s_2(2n)-2n+2s_2(n)=\nu _2(n+1)$$pero $s_2(2n)=s_2(n)$, ya que multiplicar por $2$ en binario es agregar un $0$ al final, entonces lo que queremos es que$$s_2(n)=\nu _2(n+1)$$claramente si $n$ es par tenemos que $s_2(n)=\nu _2(n+1)=0$, de donde $n=0$, que anda. Veamos entonces qué pasa cuando $n$ es impar.
Notemos que si $n$ en base $2$ termina en $k$ números $1$, entonces $\nu _2(n+1)=k$, por ejemplo, $39$ en binario es $100111$, y $40$ es $101000$, además, como $40=2^3\cdot 5$, tenemos que $\nu _2(40)=3$ (acá está pasando exactamente lo mismo que si un número en decimal termina en muchos $9$, cuando le sumás $1$ se te hacen todos $0$, y esos $0$s cuentan justamente la cantidad de factores $10$ del número).
Bueno, pero entonces dijimos que $s_2(n)=\nu _2(n+1)=k$, y como los dígitos en binario son $0$ o $1$, entonces $s_2(n)$ cuenta la cantidad de dígitos $1$ de $n$ en base $2$, es decir que $n$ tiene exactamente $k$ dígitos $1$ en base $2$, y como termina con $k$ dígitos $1$, no puede haber ningún otro, además, no puede empezar con $0$. Entonces todos los dígitos de $n$ en binario son $1$s, así que $n=2^k-1$ (notar que esto también incluye al $0$, de hecho, todo el razonamiento vale incluso para cuando $n$ en binario termina en $0$, pero me pareció más visual hacer ese caso aparte) para $k\in \mathbb{N}_0$.

En resumen, $\frac{1}{n+1}\binom{2n}{n}$ es un entero impar si y sólo si $n=2^k-1$ con $k\in \mathbb{N}_0$.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Gianni De Rico »

Me olvidaba, que proponga el que quiera
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
Mensajes: 57
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 5
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Fedex »

Solución 365:
Spoiler: mostrar
Primero veamos cuando $\frac{(2n)!}{(n)!(n+1)!}$ es impar.
Para ello necesariamente:
$v_2(n!) + v_2((n+1)!) = v_2((2n)!)$
$\sum_{i=1}^{\infty} \lfloor \frac{n}{2^i} \rfloor + \sum_{i=1}^{\infty} \lfloor \frac{n+1}{2^i} \rfloor = \sum_{i=1}^{\infty} \lfloor \frac{2n}{2^i} \rfloor = n + \sum_{i=1}^{\infty} \lfloor \frac{n}{2^i} \rfloor$
$\sum_{i=1}^{\infty} \lfloor \frac{n+1}{2^i} \rfloor = n$
Ahora sea $x$ entero tal que $2^x \leq n+1 < 2^{x+1}$
$\sum_{i=1}^{\infty} \lfloor \frac{n+1}{2^i} \rfloor =\sum_{i=1}^{x} \lfloor \frac{n+1}{2^i} \rfloor = n \leq (n+1)(\frac{1}{2} + \frac{1}{4} + ... + \frac{1}{2^x}) = (n+1)(\frac{2^{x-1} + ... + 1}{2^x}) = (n+1)(1 - \frac{1}{2^x})$
$n \leq n + 1 - \frac{n+1}{2^x}$
$\frac{n+1}{2^x} \leq 1$
Y a la vez $\frac{n+1}{2^x} \geq 1$ entonces $2^x = n+1$.
$n = 2^x - 1$.
Ahora también queremos ver que para $n$ de esta forma:
$v_p(n!) + v_p((n+1)!) \leq v_p((2n)!)$
Para determinar que este valor es entero.
Sabemos que para $p=2$ hay igualdad.
Para primo $p>2$ como $n+1 = 2^x$ solo aporta factores $2$.
$v_p(n!) = v_p((n+1)!)$
$2v_p(n!) \leq v_p((2n)!)$
Que sería verdad de demostrar:
$2 \lfloor \frac{n}{p^i} \rfloor \leq \lfloor \frac{2n}{p^i} \rfloor$
$2 \lfloor c \rfloor \leq \lfloor 2c \rfloor$
Sea $m_c$ la mantisa de $c$.
Si $0 \leq m_c < \frac{1}{2}$
$\lfloor 2c \rfloor = 2 \lfloor c \rfloor$
Si $\frac{1}{2} \leq m_c < 1$
$\lfloor 2c \rfloor = 2 \lfloor c \rfloor + 1$
Por lo que tambien se cumple la desigualdad y estamos.

$\frac{(2n)!}{(n)!(n+1)!}$ es entero impar para $n = 2^x -1$.
La subo porque la estaba escribiendo de antes (soy muuuuuuuy lento) y ya que estoy la mando :|
1  
$\frac{9}{1^2} \binom{20}{18}$

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
Mensajes: 57
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 5
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Maratón de Problemas

Mensaje sin leer por Fedex »

Bueno propongo yo.

Problema 366:
Sea:
$f(n) = \lfloor \frac{n}{1} \rfloor + \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor + ... + \lfloor \frac{n}{n} \rfloor + \lfloor \sqrt{n} \rfloor$
Demostrar que $f(n)$ es par para todo natural $n$.
$\frac{9}{1^2} \binom{20}{18}$

Responder