Publicamos la solución al divertimento Un corro sin deberes. En esta ocasión, Pablo Cano Wall nos ha hecho llegar una solución del problema (se han recibido otras respuestas con soluciones parciales). Gracias a todos por participar.
Divertimento:
Durante el descanso, \(n\) profesores de la Facultad se sientan en un corro alrededor de un estudiante para mandarle deberes sin piedad. Antes de ser sepultado por varias relaciones de ejercicios, el estudiante les propone el siguiente juego, que los profesores aceptan: selecciona un profesor \(p_1\) y le propone un divertimento de los numerosísimos que pueblan el afamado blog del IMUS. Luego, en el sentido de las agujas del reloj, le propone otro al siguiente profesor, \(p_2\). Después propone otro al que ocupa el segundo lugar después de \(p_2\) (llamémoslo \(p_3\)), saltándose un profesor. Después se salta dos y le propone otro divertimento al tercero después de \(p_3\), y así sucesivamente, saltando un profesor más en cada asignación. Los profesores \(p_i\) no tienen por qué ser distintos, y los profesores pueden recibir más de un divertimento.
¿Qué valores de \(n\) le permiten al estudiante proponer un divertimento a cada uno de los profesores para poder escapar mientras estos están absortos en los desafíos asignados?
Solución:
Solo cuando \(n\) es una potencia de dos puede salir indemne el alumno. Asignemos un número natural entre \(0\) y \(n-1\) a cada profesor. El alumno le asigna un divertimento al profesor en la posición cero, y después, en el paso \(k\)-ésimo, donde \(k>0\), le asigna un divertimento al profesor que ocupa el lugar \(1+2+\ldots+k\) módulo \(n\). Lo que nos estamos preguntando, por tanto, es si la expresión \(1+\ldots+k=k(k+1)/2\) recorre todos los posibles enteros módulo \(n\), para cualquier \(k\geq0\).
Trabajemos en primer lugar módulo un primo impar \(p\), y sea \(f(x)\) el polinomio \(x(x+1)/2\). En ese caso, \(f(x)=f(-x-1)\) para todo \(x=0,\ldots,p-1\). En particular, si consideramos \(f(x)\) como una aplicación con el conjunto de enteros módulo \(p\) como origen y destino, no toma todos los valores posibles (no es sobreyectiva), porque no es inyectiva (pues siempre hay un \(x\in\{0,\ldots,p-1\}\) tal que \(x\neq-x-1\) módulo \(p\)) y el origen y el destino son finitos de igual cardinal. Por tanto, existe un \(m\in\{0,\ldots,p-1\}\) tal que, para todo \(k\geq0\), \(k(k+1)/2\not\equiv m\) módulo \(p\). En particular, \(k(k+1)/2\not\equiv m\) módulo un múltiplo de \(p\) cualquiera. En conclusión, si \(n\) no es una potencia de dos, siempre habrá al menos un profesor libre para mandarle deberes al pobre e imaginativo alumno.
Veamos, recíprocamente, que si \(n=2^b\), para cierto \(b\geq0\), todos los profesores se enfrascan en un divertimento, es decir, que \(k(k+1)/2\) recorre todos los valores posibles módulo \(n\). Lo probaremos por inducción. Evidentemente, si \(b=0\) el enunciado es cierto. Supongamos que también lo sea si \(b=r\), para cierto \(r\geq0\), y veamos que si \(b=r+1\) también es posible.
Estamos asumiendo que \(k(k+1)/2\) pasa por todos los posibles valores módulo \(2^r\) a medida que \(k\) recorre todos los enteros no negativos. En particular, recorre al menos la mitad de los enteros módulo \(2^{r+1}\). Fijemos un \(k\) concreto, y tomemos \(k’=2^{r+1}+k\). En ese caso,
$$k'(k’+1)/2=2^{2r+1}+2^{r+1}k+2^r+k(k+1)/2.$$
Esta cantidad es la misma módulo \(2^r\), pero módulo \(2^{r+1}\) es \(2^r+k(k+1)/2\), por lo que por cada entero \(k\), tomando \(k’=2^{r+1}+k\), obtenemos dos valores distintos módulo \(2^{r+1}\) por cada posible valor módulo \(2^r\), siendo los enteros de cada par \((k,k’)\) distintos de los de cualquier otro. En particular, la expresión \(k(k+1)/2\) recorre todos los valores módulo \(2^{r+1}\) y hemos terminado.
Dejar una contestacion