Probar que si a menos de $n$ de los estudiantes en clase son inicialmente infectadas, la clase entera nunca será completamente infectado.

Question

Durante 6.042, los estudiantes están sentados en un $n$ × $n$ cuadrícula. Un repentino brote de gripe beaver (una rara variante de la gripe aviar, que dura para siempre; los síntomas incluyen anhelo de los conjuntos de problemas y el deseo de los helados sesiones de estudio) hace que algunos estudiantes a infectarse. Aquí es un ejemplo donde $n = 6$ e infectados estudiantes están marcados ×.

Ejemplo.

Ahora que la infección comienza a extenderse cada minuto (en tiempo discreto-pasos). Dos estudiantes consideran adyacentes si comparten una arista (es decir, frente, atrás, izquierda o derecha, pero NO en diagonal); por lo tanto, cada estudiante es adyacente a $2, 3,$ o $4$ otros. Un estudiante está infectado en el siguiente paso de tiempo si bien:

• el estudiante fue previamente infectados (desde beaver la gripe dura para siempre), o
• el estudiante es adyacente a al menos dos ya infectados por los estudiantes.

En el ejemplo, la infección se propaga como se muestra a continuación.

Ejemplo.

En este ejemplo, durante las próximas tiempo-pasos, todos los estudiantes en la clase de infectarse.

Teorema. Si menos de $n$ de los estudiantes en clase son inicialmente infectadas, la clase entera nunca ser completamente infectado.

Demostrar este teorema.

Sugerencia: Cuando uno quiere entender cómo un sistema como el de arriba "evoluciona" a lo largo del tiempo, normalmente, es una buena estrategia para (1) identificar una propiedad adecuada del sistema en el etapa inicial, y (2) demostrar por inducción sobre el número de pasos, que la propiedad es se conserva en cada momento paso. Así que busque una propiedad (de la serie de los infectados estudiantes) que permanece invariable a medida que avanza el tiempo.

Fuente: MIT OCW Matemáticas para Ciencias de la computación, Conjunto de problemas 2, 3 de problemas.

No estoy realmente seguro de cómo puedo demostrar esto. Me arriesgué y asumió que yo sería el uso de la inducción ya que esto parece un problema que requiere un invariante a ser usado para demostrar el teorema.

Otra cosa que me he dado cuenta es que si $k$ de los estudiantes son inicialmente infectados, entonces el perímetro de la figura formada por los infectados de los estudiantes como la propagación de la infección es en la mayoría de las $4k$. Así, esta podría ser mi invariante.

Así que, esto es lo que tengo hasta ahora:

Teorema: Si menos de $n$ de los estudiantes en clase son inicialmente infectadas, la clase entera nunca ser completamente infectado.

Prueba: por inducción

Agradecería cualquier y todos los consejos que me ayudara a conseguir el balanceo de la bola con esta prueba.

Answer 1

Usted resolver su propio problema! Tenga en cuenta la duración de la frontera. Si hay $<n$ infectados plazas inicialmente, la longitud es en la mayoría de las $4(n-1)$. No se puede aumentar, pero si terminamos con todas las plazas infectado el límite sería la longitud de la $4n$.

En el siguiente diagrama se considere lo que sucede cuando la plaza de $b$ se infecta. En el primer caso tenemos nuevo límite por encima y por debajo de él (por $a,c$ son no infectadas), pero perdemos el límite en cualquiera de los lados de $b$, por lo que no hay cambio neto.

En el segundo caso, tenemos una pérdida neta de 2 (perdemos tres lados de la frontera y el aumento sólo 1). En el tercer caso tenemos una pérdida neta de 4.

Así, en todos los casos, no podemos aumentar la longitud total de la frontera - debemos perder al menos 2 y se puede obtener en la mayoría de los 2.

Answer 2

Teorema: Si menos de $n$ de los estudiantes en clase son inicialmente infectadas, la clase entera nunca ser completamente infectado.

Prueba: por inducción. Definimos el perímetro de un infectado conjunto de los estudiantes como el número de aristas con la infección en exactamente un lado. Dejamos $x$ indicar el tamaño del perímetro.

Deje $P(k)$ ser la proposición de que después de $k$ tiempo discreto-pasos, el perímetro es de menos de $4n$.

Caso Base: $P(0)$ es cierto.

Esto es trivialmente cierto, ya que el perímetro no podría haber posibles cambiado después de $0$ tiempo discreto-pasos. El perímetro de los infectados región sigue siendo ser $x$.

Inductivo Paso: para todos los números enteros no negativos, debemos mostrar que $P(k)\Rightarrow P(k+1)$

Suponemos que $P(k)$ es cierto para los efectos de la inducción. Así, esto significa que estamos suponiendo que el perímetro de la infeted región es en la mayoría de las $x$ después $k$ pasos.

En el paso $k + 1$, el perímetro de la infectada región sólo puede cambiar de dos maneras. Desde cada uno de los nuevos infectados plaza adyacente a al menos dos infectados previamente cuadrados, cada uno de los nuevos infectados plaza:

perder al menos dos bordes del perímetro de los infectados región, o agregar en la mayoría de los dos bordes del perímetro. Por lo tanto, el perímetro de la infectada región no puede aumentar.

Así, hemos demostrado que para todos los números enteros no negativos, $k$, $P(k)\Rightarrow P(k+1)$

Q. E. D.