Nacional 2018 P2 N3

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

OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Mención
Mensajes: 135
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 3
Nivel: 1

Nacional 2018 P2 N3

Mensaje sin leer por Monazo » Dom 11 Nov, 2018 8:24 am

Hay $n$ caballeros numerados de $1$ a $n$ y una mesa redonda con $n$ sillas. El primer caballero elige su silla, y a partir de él, el caballero número $k+1$ se sienta $k$ lugares a la derecha del caballero número $k$, para todo $1\leq k\leq n-1$ (se cuentan sillas ocupadas y vacías). En particular, el segundo caballero se sienta al lado del primero. Hallar todos los valores de $n$ para que los $n$ caballeros ocupen las $n$ sillas siguiendo el procedimiento descripto.

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 885
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2018 P2 N3

Mensaje sin leer por Fran5 » Dom 11 Nov, 2018 8:58 am

When plagias al nacional de méxico
1  
"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 OFO - Medalla de Oro
Mensajes: 1064
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Gianni De Rico » Dom 11 Nov, 2018 9:02 am

Fran5 escribió:
Dom 11 Nov, 2018 8:58 am
When plagias al nacional de méxico
Que a su vez había plagiado a otra competencia vieja
Queda Elegantemente Demostrado

tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado FOFO 7 años - Jurado
FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 594
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 10
Nivel: Exolímpico

Re: Nacional 2018 P2 N3

Mensaje sin leer por tuvie » Dom 11 Nov, 2018 12:58 pm

Fran5 escribió:
Dom 11 Nov, 2018 8:58 am
When plagias al nacional de méxico
En realidad habría que chequear a que hora se rindió en México, porque fue el mismo día. :lol:
1  

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 926
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Re: Nacional 2018 P2 N3

Mensaje sin leer por Matías V5 » Lun 12 Nov, 2018 3:42 am

tuvie escribió:
Dom 11 Nov, 2018 12:58 pm
Fran5 escribió:
Dom 11 Nov, 2018 8:58 am
When plagias al nacional de méxico
En realidad habría que chequear a que hora se rindió en México, porque fue el mismo día. :lol:
Dado que cuando empezó la prueba acá, en México eran las 6:30 am, creo que se puede afirmar que acá fue primero :P
1  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Peznerd
Mensajes: 106
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Peznerd » Vie 25 Oct, 2019 9:27 am

Mucha habladuría pocas soluciones!! :roll:
Me está comiendo la cabeza el problema
1  
Un día vi una vaca sin cola vestida de uniforme

$$\int u \, dv=uv-\int v \, du\!$$

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1064
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Gianni De Rico » Sab 26 Oct, 2019 8:08 pm

Este problema lo contaron en la premiación, no recuerdo completamente la solución, así que voy con la mía (puede ser parecida)

Respuesta:
Spoiler: mostrar
Los valores de $n$ que cumplen son las potencias de $2$.
Solución:
Spoiler: mostrar
Decimos que $n$ funciona si los caballeros pueden ocupar todas las sillas. Cambiamos la numeración de los caballeros, de $0$ a $n-1$, de esta forma, el $k$-ésimo caballero se sienta $k$ lugares a la derecha del $(k-1)$-ésimo caballero. Numeramos las sillas de $0$ a $n-1$ en sentido antihorario, de modo que la silla número $0$ sea la del primer caballero. De esta forma, el $k$-ésimo caballero se sienta en la silla número $\frac{k(k+1)}{2}\pmod n$. Notemos que $n=1$ funciona, a partir de ahora, supongamos que $n>1$.

Veamos primero que si $n$ es impar, entonces $n$ no funciona.
En efecto, consideremos dos caballeros, ioaki, el caballero número $0$, y Emi, el caballero número $n-1$, y veamos que ambos se sientan en la misma silla. Para eso, basta ver que $\frac{n(n-1)}{2}\equiv 0\pmod n$. Como $n$ es impar, tenemos que $n=2t+1$ para algún natural $t$, luego, $\frac{n(n-1)}{2}=\frac{(2t+1)2t}{2}=(2t+1)t=nt\equiv 0\pmod n$. Por lo tanto, ioaki y Emi se sientan en la misma silla de la mesa redonda. Luego, los $n$ impares no funcionan.

Veamos ahora que si $n$ tiene algún factor primo impar, entonces $n$ no funciona.
En efecto, sea $n=a\cdot 2^b$ con $a$ impar y mayor que $1$. Supongamos que $n$ funciona, luego, para cada $k$, existe un índice $i_k\in \{0,1,\ldots ,n-1\}$ tal que $\frac{k(k+1)}{2}\equiv i_k\pmod n$, además, tenemos que $i_p\neq i_q$ si $p\neq q$. En particular, tomando $p=0$ y $q=2^ma-1$ (con $0\leqslant m\leqslant b$) tenemos que $i_p\equiv 0\pmod a$, y que $i_q\equiv 0\pmod a$, de donde hay $1+b+1$ múltiplos de $a$ en el intervalo $[0,a\cdot 2^b-1]$, pero hay exatamente $b+1$ múltiplos de $a$ en el intervalo $[0,a\cdot 2^b-1]$ (explícitamente, son $0,a,2a,4a,\ldots ,2^ma,\ldots ,2^{b-1}a$). Luego, llegamos a un absurdo que proviene de suponer que $n$ funciona. Por lo tanto, si $n$ tiene algún factor primo impar, entonces $n$ no funciona.

Finalmente, veamos que si $n$ es una potencia de $2$, entonces $n$ funciona.
En efecto, sea $n=2^t$. Supongamos que existen dos valores $0<b<a<n$ tales que $\frac{a(a+1)}{2}\equiv \frac{b(b+1)}{2}\pmod n$, de donde $a(a+1)-b(b+1)\equiv 0\pmod n$. Notemos que $$a(a+1)-b(b+1)=(a-b)(a+b+1)$$ por lo que $(a-b)(a+b+1)\equiv 0\pmod n$. Por otro lado, tenemos que $$2a\equiv 0\pmod 2\Rightarrow a-b\equiv -(a+b)\equiv a+b\pmod 2\Rightarrow a-b\not \equiv a+b+1\pmod 2$$ de donde exactamente uno de ellos es par, por lo que debe ser una potencia de $2$ mayor o igual a $n$, pero tenemos que $0<a-b<n$ y que $0<b+1\leqslant a\leqslant n-1\Rightarrow 0<a+b+1\leqslant n-2<n$. Por lo tanto, llegamos a un absurdo y no existen dos valores $0<b<a<n$ tales que los caballeros $a$ y $b$ se sienten en la misma silla.
Basta ver que ninguno se sienta en la silla número $0$. En efecto, supongamos lo contrario, luego existe $0<g<2^t$ tal que $\frac{g(g+1)}{2}\equiv 0\pmod{2^t}$. Por lo tanto, $g(g+1)\equiv 0\pmod{2^{t+1}}$, pero exactamente uno de entre $g$ y $g+1$ es par, por lo que debe ser una potencia de $2$ mayor o igual a $2^{t+1}$, lo que es absurdo pues $0<g<g+1\leqslant 2^t<2^{t+1}$. Luego, ninguno se sienta en la silla número $0$.
Entonces el caballero número $0$ se sienta en la silla número $0$ y el resto se sientan todos en sillas distintas y distintas de la silla $0$. Por lo tanto, todos los caballeros se sientan en sillas distintas. Entonces si $n$ es una potencia de $2$, funciona.

Finalmente, $n$ funciona si y sólo si $n$ es una potencia de $2$.
Queda Elegantemente Demostrado

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 885
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2018 P2 N3

Mensaje sin leer por Fran5 » Lun 28 Oct, 2019 9:07 am

Gianni De Rico escribió:
Sab 26 Oct, 2019 8:08 pm
pero hay exatamente $b+1$ múltiplos de $a$ en el intervalo $[0,a\cdot 2^b-1]$ (explícitamente, son $0,a,2a,4a,\ldots ,2^ma,\ldots ,2^{b-1}a$).
Esto está #Chequeado ??
1  
"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 OFO - Medalla de Oro
Mensajes: 1064
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Gianni De Rico » Lun 28 Oct, 2019 10:32 pm

Fran5 escribió:
Lun 28 Oct, 2019 9:07 am
Gianni De Rico escribió:
Sab 26 Oct, 2019 8:08 pm
pero hay exatamente $b+1$ múltiplos de $a$ en el intervalo $[0,a\cdot 2^b-1]$ (explícitamente, son $0,a,2a,4a,\ldots ,2^ma,\ldots ,2^{b-1}a$).
Esto está #Chequeado ??
Pifié, esos son los múltiplos en el conjunto de los divisores no negativos de $n$ y menores a $n$. En algún momento (cuando tenga tiempo/ganas) resviso ese argumento.
Queda Elegantemente Demostrado

Peznerd
Mensajes: 106
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Peznerd » Dom 10 Nov, 2019 12:06 am

Gianni De Rico escribió:
Sab 26 Oct, 2019 8:08 pm
Este problema lo contaron en la premiación, no recuerdo completamente la solución, así que voy con la mía (puede ser parecida)

Respuesta:
Spoiler: mostrar
Los valores de $n$ que cumplen son las potencias de $2$.
Solución:
Spoiler: mostrar
Decimos que $n$ funciona si los caballeros pueden ocupar todas las sillas. Cambiamos la numeración de los caballeros, de $0$ a $n-1$, de esta forma, el $k$-ésimo caballero se sienta $k$ lugares a la derecha del $(k-1)$-ésimo caballero. Numeramos las sillas de $0$ a $n-1$ en sentido antihorario, de modo que la silla número $0$ sea la del primer caballero. De esta forma, el $k$-ésimo caballero se sienta en la silla número $\frac{k(k+1)}{2}\pmod n$. Notemos que $n=1$ funciona, a partir de ahora, supongamos que $n>1$.

Veamos primero que si $n$ es impar, entonces $n$ no funciona.
En efecto, consideremos dos caballeros, ioaki, el caballero número $0$, y Emi, el caballero número $n-1$, y veamos que ambos se sientan en la misma silla. Para eso, basta ver que $\frac{n(n-1)}{2}\equiv 0\pmod n$. Como $n$ es impar, tenemos que $n=2t+1$ para algún natural $t$, luego, $\frac{n(n-1)}{2}=\frac{(2t+1)2t}{2}=(2t+1)t=nt\equiv 0\pmod n$. Por lo tanto, ioaki y Emi se sientan en la misma silla de la mesa redonda. Luego, los $n$ impares no funcionan.

Veamos ahora que si $n$ tiene algún factor primo impar, entonces $n$ no funciona.
En efecto, sea $n=a\cdot 2^b$ con $a$ impar y mayor que $1$. Supongamos que $n$ funciona, luego, para cada $k$, existe un índice $i_k\in \{0,1,\ldots ,n-1\}$ tal que $\frac{k(k+1)}{2}\equiv i_k\pmod n$, además, tenemos que $i_p\neq i_q$ si $p\neq q$. En particular, tomando $p=0$ y $q=2^ma-1$ (con $0\leqslant m\leqslant b$) tenemos que $i_p\equiv 0\pmod a$, y que $i_q\equiv 0\pmod a$, de donde hay $1+b+1$ múltiplos de $a$ en el intervalo $[0,a\cdot 2^b-1]$, pero hay exatamente $b+1$ múltiplos de $a$ en el intervalo $[0,a\cdot 2^b-1]$ (explícitamente, son $0,a,2a,4a,\ldots ,2^ma,\ldots ,2^{b-1}a$). Luego, llegamos a un absurdo que proviene de suponer que $n$ funciona. Por lo tanto, si $n$ tiene algún factor primo impar, entonces $n$ no funciona.

Finalmente, veamos que si $n$ es una potencia de $2$, entonces $n$ funciona.
En efecto, sea $n=2^t$. Supongamos que existen dos valores $0<b<a<n$ tales que $\frac{a(a+1)}{2}\equiv \frac{b(b+1)}{2}\pmod n$, de donde $a(a+1)-b(b+1)\equiv 0\pmod n$. Notemos que $$a(a+1)-b(b+1)=(a-b)(a+b+1)$$ por lo que $(a-b)(a+b+1)\equiv 0\pmod n$. Por otro lado, tenemos que $$2a\equiv 0\pmod 2\Rightarrow a-b\equiv -(a+b)\equiv a+b\pmod 2\Rightarrow a-b\not \equiv a+b+1\pmod 2$$ de donde exactamente uno de ellos es par, por lo que debe ser una potencia de $2$ mayor o igual a $n$, pero tenemos que $0<a-b<n$ y que $0<b+1\leqslant a\leqslant n-1\Rightarrow 0<a+b+1\leqslant n-2<n$. Por lo tanto, llegamos a un absurdo y no existen dos valores $0<b<a<n$ tales que los caballeros $a$ y $b$ se sienten en la misma silla.
Basta ver que ninguno se sienta en la silla número $0$. En efecto, supongamos lo contrario, luego existe $0<g<2^t$ tal que $\frac{g(g+1)}{2}\equiv 0\pmod{2^t}$. Por lo tanto, $g(g+1)\equiv 0\pmod{2^{t+1}}$, pero exactamente uno de entre $g$ y $g+1$ es par, por lo que debe ser una potencia de $2$ mayor o igual a $2^{t+1}$, lo que es absurdo pues $0<g<g+1\leqslant 2^t<2^{t+1}$. Luego, ninguno se sienta en la silla número $0$.
Entonces el caballero número $0$ se sienta en la silla número $0$ y el resto se sientan todos en sillas distintas y distintas de la silla $0$. Por lo tanto, todos los caballeros se sientan en sillas distintas. Entonces si $n$ es una potencia de $2$, funciona.

Finalmente, $n$ funciona si y sólo si $n$ es una potencia de $2$.
Muy elegante. Me marié en la parte de $i_k$, $i_p$ e $i_q$ ¿De dónde salieron y para qué?
Un día vi una vaca sin cola vestida de uniforme

$$\int u \, dv=uv-\int v \, du\!$$

Responder