Nacional 2018 P2 N3

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

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años 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
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Nacional 2018 P2 N3

Mensaje sin leer por Monazo »

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.
Soy una Estufa en Piloto
:shock:
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: Nacional 2018 P2 N3

Mensaje sin leer por Fran5 »

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 //
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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 FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Gianni De Rico »

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
♪♫ do re mi función lineal ♪♫
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 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 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

Re: Nacional 2018 P2 N3

Mensaje sin leer por tuvie »

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-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

Re: Nacional 2018 P2 N3

Mensaje sin leer por Matías V5 »

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  
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
Peznerd
Mensajes: 113
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Peznerd »

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-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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 FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Gianni De Rico »

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$.
♪♫ do re mi función lineal ♪♫
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: Nacional 2018 P2 N3

Mensaje sin leer por Fran5 »

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 //
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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 FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
Peznerd
Mensajes: 113
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Nacional 2018 P2 N3

Mensaje sin leer por Peznerd »

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