Durante 6.042, los estudiantes están sentados en un n × n cuadrícula. Un repentino brote de gripe del castor (una rara variante de la gripe aviar que dura una eternidad; los síntomas incluyen el anhelo de los conjuntos de problemas y el deseo de sesiones de estudio con helado) hace que algunos estudiantes se contagien. He aquí un ejemplo en el que =6 n=6 y los estudiantes infectados se marcan con ×.
Ejemplo.
Ahora la infección comienza a propagarse cada minuto (en pasos de tiempo discretos). Dos estudiantes se consideran adyacentes si comparten un borde (es decir, delante, detrás, a la izquierda o a la derecha, pero NO en diagonal); así, cada estudiante es adyacente a 2,3, 2 , 3 , o 4 4 otros. Un estudiante está infectado en el siguiente paso de tiempo si:
el estudiante ya estaba infectado (ya que la gripe del castor dura para siempre), o el alumno se encuentra junto a al menos dos alumnos ya infectados. En el ejemplo, la infección se propaga como se muestra a continuación.
Ejemplo.
En este ejemplo, en los siguientes pasos de tiempo, todos los estudiantes de la clase se infectan.
Teorema. Si menos de n estudiantes de la clase están inicialmente infectados, toda la clase nunca estará completamente infectada.
Demuestra este teorema.
Sugerencia: Cuando uno quiere entender cómo un sistema como el anterior "evoluciona" en el tiempo, suele ser una buena estrategia (1) identificar una propiedad apropiada del sistema en la etapa inicial, y (2) demostrar, por inducción en el número de pasos de tiempo, que la propiedad se conserva en cada paso de tiempo. Así que busque una propiedad (del conjunto de estudiantes infectados) que permanezca invariable a medida que avanza el tiempo.
Fuente: MIT OCW Mathematics for Computer Science, Problem Set 2, Problem 3.
No estoy muy seguro de cómo puedo demostrarlo. Pero esto es lo que he intentado:
Prueba por inducción:
Sea P(n) la proposición: Si se infectan inicialmente menos de los alumnos de la clase, nunca se infectará por completo toda la clase.
- Caso base: n = 0, P(0) es verdadera por definición ya que no hay estudiantes infectados para propagar la enfermedad para empezar.
2)Paso inductivo:
P(n) => P(n-1)
Conjunto de estudiantes totales: {n^2}
El número total de estudiantes en el conjunto anterior será n^2 en la cuadrícula n*n.
conjunto de estudiantes infectados inicialmente (en t = 0):
{S,....,Sn-1}
A medida que pasa el tiempo este conjunto de estudiantes infectados aumenta, asumiendo que P(n) es verdadera el número de estudiantes en el conjunto de estudiantes infectados nunca alcanzará el número de estudiantes en el conjunto de estudiantes totales.Por lo tanto, toda la clase nunca será infectada.Por lo tanto, ¡probado!
Si no es así, ¿por qué? Cualquier ayuda será muy apreciada.
