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.
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
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$.
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$).
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.
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)
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é?