Pregunta sobre aritmética modular, posiblemente relacionada con el teorema chino del resto

Question

'6 profesores inician cursos de conferencias los lunes, martes, miércoles, jueves, viernes y sábados, y anuncian sus intenciones de dar conferencias a intervalos de 2,3,4,1,6,5 días respectivamente. El reglamento de la Universidad prohíbe dar clase los domingos (por lo que hay que omitir la clase del domingo). ¿Cuándo será la primera vez que los seis profesores se vean obligados a omitir una clase?

Creo que se puede resolver utilizando el teorema del resto chino, pero no estoy consiguiendo nada. Cualquier progreso que haga lo publicaré, pero todavía no he hecho nada que valga la pena añadir a esto. Cualquier ayuda será muy apreciada.

EDIT: Ok, así que he reducido el problema a encontrar el valor positivo mínimo tal que, d=11(mod 12), 6(mod 5), 0(mod 7).

Answer 1

Por suerte, el siete es primo, así que todos los profesores tendrán que saltarse una de cada siete clases. Que el próximo domingo sea el número cero, que $i$ ser el domingo $i$ semanas en el futuro, y dejar que $N$ denotan el número de un domingo, en el que todos deben faltar a clase. El profesor Monday tendrá que faltar este domingo y todos los domingos siguientes, de modo que $N\equiv 0 \pmod 2$ . Al Prof. Tuesday le gustaría primero predicar el domingo $\#1$ exactamente $12=4\cdot3$ días después del inicio de su curso, por lo que $N\equiv 1\pmod 3$ . El profesor Wednesday también perderá una oportunidad el próximo domingo, así que $N\equiv 0\pmod 4$ . El ansioso castor prof. Jueves estará irritado todos los domingos, por lo que puede quedar fuera del cómputo. El profesor perezoso del viernes se sentirá molesto (¿o aliviado?) el domingo. $\#4$ (cuatro semanas completas más dos días de Vie a Dom = $30=5\cdot 6$ días), por lo que $N=4\pmod 6$ . El primer fallo del profesor Saturday es $15=3\cdot5$ días después de que su curso haya comenzado el domingo $\#2$ Así que $N\equiv 2\pmod 5.$

PERO no voy a resolver esto por ti. Compruebe lo anterior, y entonces utilizar el CRT para encontrar los posibles valores de $N$ . Para obtener un crédito extra, debería observar que no estaba claro a priori que los seis profesores fueran a faltar a una conferencia el mismo domingo. Se produjeron varios encajes milagrosos, por lo que reconozco el mérito de quien compuso este problema.

Answer 2

Que el número $1$ etiqueta el primer lunes. Entonces los horarios de los profesores hacen que sus días de clase satisfagan las congruencias siguientes: $$\begin{align*} d_1&\equiv1\pmod2,\\ d_2&\equiv2\pmod3,\\ d_3&\equiv3\pmod4,\\ d_4&\equiv4\pmod1,\\ d_5&\equiv5\pmod6,\\ d_6&\equiv6\pmod5. \end{align*}$$ Para encontrar el domingo en el que el último profesor se ve obligado a abstenerse de dar clase, tomaremos la solución positiva mínima de cada sistema $d_i=i\pmod\circ$ , $d_i=0\pmod 7$ (para que el profesor $i$ debería estar dando conferencias por el horario pero no puede porque es domingo) y encontrar el máximo entre ellos. Acabo de comprobar múltiplos de $7$ mentalmente hasta que encontré soluciones para cada una de ellas. Las soluciones son $7,14,7,7,35,21$ por lo que $35$ días todos los profesores habrán omitido una conferencia en algún momento.

---

Por otro lado, si busca el primer domingo en el que los seis profesores simultáneamente omitir una lectura, entonces debemos resolver todas las congruencias anteriores para una única $d$ al mismo tiempo, con la congruencia adicional de $0\bmod7$ . Obsérvese que el módulo $1$ se cumple trivialmente y puede descartarse, el módulo $2$ congruencia se subsume en el módulo $4$ congruencia y el módulo $3$ congruencia se subsume en el módulo $6$ congruencia, por lo que reducir da $d\equiv$ $$\begin{align*}3&\bmod4,\\5&\bmod6,\\1&\bmod5,\\0&\bmod7.\end{align*}$$ Las dos primeras pueden resolverse en $11\bmod12$ dejando los módulos restantes coprimos para que puedas utilizar el método de construcción general del artículo de Wikipedia sobre la Teorema chino del resto para resolver este sistema. El cálculo es $$11\cdot35\cdot(35_{12}^{-1})+1\cdot84\cdot(84_5^{-1})=4571\equiv371\bmod420$$ de ahí que nuestra solución sea el día 371. (¿Pero qué clases locas duran más de un año sin parar?)

Answer 3

CONSEJO $\ $ Es fácil ya que $\rm\ n\equiv -1\ $ para casi todos los módulos. Por lo tanto, por ejemplo

$$\rm\qquad\ \ n \equiv -1\ \ (mod\ i,\:j,\:k)\ \ \Rightarrow\ \ n\equiv -1\ \ (mod\ \ lcm(i,j,k)) $$

Dicho en términos más elementales $\rm\ \ i,\:j,\:k\ |\ n+1\ \ \Rightarrow\ lcm(i,j,k)\ |\ n+1$

Así que puede sustituir la mayor parte del cálculo del resto chino por otro mucho más sencillo $\rm\:lcm\:$ cálculos. Se puede realizar la misma optimización en cualquier problema CRT en el que los valores sean los mismos para más de un módulo, es decir, en el que la solución tenga valor "constante", por ejemplo $\rm\:n\:$ es constante $\rm\equiv -1\:$ para los tres módulos anteriores. Para otro ejemplo de optimización CRT análoga, véase esta respuesta, donde la optimización anterior simplifica un cálculo de tres páginas a un cálculo trivial de tres líneas.

Answer 4

Si quieres utilizar el Teorema del Resto Chino, debes numerar los días empezando por la primera clase del lunes; luego, para encontrar el domingo en que todos omiten una clase, hallas el número del día en que cae. Ahora ya puedes usar la aritmética.

Las condiciones dadas sobre 1) los días en que empiezan los profesores y 2) los intervalos entre sus clases muestran que los números de los días en que cada profesor da clase satisfacen una condición de congruencia. Los domingos cumplen otra condición de congruencia. Se necesita la solución positiva más pequeña de todas estas congruencias, y una forma de resolverlas es utilizar la prueba constructiva de la CRT. Sin embargo, creo que una solución más rápida y sencilla será combinar un poco de ensayo-error con el enunciado de la CRT para demostrar que la solución que has encontrado es la más pequeña.

Answer 5

La respuesta puede simplificarse aún más: 371 (mod 420) = 371 (mod 420 ÷2) = 161 (mod 210). El (161 ÷7=) 23º domingo, cuando los 6 profesores se ven obligados a omitir una conferencia. Observación: si se mantiene x = 1 (mod 2) y x= 2 (mod 3) en lugar de los equivalentes x = 3 (mod 4) = 3 (mod 4÷2) =1 (mod 2), x = 5 (mod 6) = 5 (mod 6 ÷2) = 5 (mod 3) = 2 (mod 3), resp., entonces se obtendría directamente : x = 161 (mod 210). Véase: https://tomcircle.wordpress.com/2017/01/05/crt-problem/