Problema de combinatoria: Acertijo de la caja

Question

Un enorme grupo de personas vive una extraña existencia a base de cajas. Cada día, todos cambian la caja en la que están, y cada día comparten su caja con exactamente una persona, y nunca comparten una caja con la misma persona dos veces.

Uno de los habitantes de las cajas se pone enfermo. La enfermedad se contagia por co-citación de cajas. ¿Cuál es el número mínimo de personas que están enfermas el día n?

---

Información adicional (no incluida originalmente en el problema):

Secuencia OEIS potencialmente relevante: http://oeis.org/A007843

Answer 1

Utilicé la fuerza bruta, minimizando lo posible, hasta el día 20, luego me sentí lo suficientemente cómodo como para tratar de hacer una conjetura sobre el número mínimo de pacientes en días sucesivos. Surgió un patrón bastante evidente, y el número era exactamente la secuencia de oeis.org/A007843 . Lo primero que he notado, después de tener todos los resultados de los primeros 20 días escritos, es que siempre que el número mínimo de pacientes se convierte en una potencia de 2, se hace claramente obvio cuánto tiempo va a ser válida la contención de la enfermedad, en el caso mínimo: se da como $\log_2 x$ donde x es el número mínimo de pacientes. Así que he reescrito el número mínimo de pacientes en términos de potencias de 2 $ (2^0, 2^1, 2^2, 2^2+2^1, 2^3, 2^3+2^1, 2^3+2^2, 2^3+2^2+2^1, 2^4, 2^4+2^1, 2^4+2^2, 2^4+2^2+2^1, 2^4+2^3, 2^4+2^3+2^1, 2^4+2^3+2^2, 2^4+2^3+2^2+2^1, ...).$ Cada elemento de esta secuencia representa el número mínimo de pacientes en algún momento, en orden consecutivo. Obsérvese que, el exponente del último término de cada ítem expone el número de días en los que la enfermedad se va a mantener contenida en el mismo nivel exhibido por el valor del ítem, es decir (1 paciente en el Día 0, 2 pacientes durante 1 día, 4 pacientes durante 2 días, 6 pacientes durante 1 día, 8 pacientes durante 3 días, 10 pacientes durante 1 día, 12 pacientes durante 2 días, ...). Por lo tanto, la secuencia de los días sucesivos a partir del Día 0 es (1, 2, 4, 4, 6, 8, 8, 10, 12, 12, 14, 16, 16, 16, 18, 20, 20, 22, 24, 24, 24, 26, 28, 28, 30, ...) como se muestra en Secuencia OEIS . (Quería publicar esto como comentario pero parece que no se me permite )

Answer 2

Por si acaso esto ayuda a alguien:

(En cada paso debemos cubrir un $N\times N$ tablero con $N$ torres que no se atacan a sí mismas, diagonal prohibida). Esto da la secuencia (empiezo a numerar el día 1 para N=2) : (2,4,4,6,8,8,10,12,12,14,16,16)

Actualizado: a. Breve explicación: cada columna-fila corresponde a una persona; los números $n$ Las celdas muestran los emparejamientos de los enfermos correspondientes al día $n$ (día 1: par {1,2}; día 2: pares {1,4}, {2,3})

b. Esto, como la mayoría de las respuestas aquí, supone que estamos interesados en una secuencia de emparejamientos que minimicen el número de enfermos para todos $n$ . Pero se puede argumentar que la pregunta no es clara en este sentido, y que podría estar interesado en minimizar el número de enfermos para uno fijo $n$ . En este caso, el problema es más sencillo, véase la respuesta de Daniel Martin.

Answer 3

Si queremos minimizar el número de personas infectadas sólo después de un número fijo $n$ de días -- lo que significa que no tenemos una respuesta que esté en función de $n$ como $n$ tiende a infinito -- entonces la respuesta depende de la paridad de $n$ : para impar $n$ la respuesta es $n + 1$ , mientras que para incluso $n$ la respuesta es $n + 2$ .

Primero observe que no puede haber menos entonces $n + 1$ individuos infectados en el día $n$ ya que el primer infectado ha compartido cajas con al menos $n$ otras personas.

Supongamos ahora $n$ es impar. Tome un juego $V$ que contiene $n + 1$ ciudadanos del mundo de la caja (uno de ellos es el infectado). Tome un gráfico completo en $V$ . Descomponga sus bordes en combinaciones perfectas $M_1, \dots, M_{n}$ . Cada uno de los perfectos $M_i$ te dice cómo será la co-box-itation en el día $i$ . Asumir que la gente fuera de $V$ compartir cajas sólo con personas ajenas a $V$ durante estos $n$ días. Este esquema hace que todos en $V$ enfermo de día $n$ mientras que nadie fuera de $V$ está enfermo en el día $n$ .

Para $n$ días, con $n$ incluso, la prueba de que puede haber tan poco como $n + 2$ Los individuos infectados son similares a los del párrafo anterior.

La prueba de que no puede haber menos de $n + 2$ individuos infectados es la siguiente. Ya sabemos que, al final del día $n - 1$ Hay por lo menos $n$ individuos infectados (porque $n - 1$ es impar). Si hay precisamente $n$ es porque han compartido cajas entre ellos durante estos $n - 1$ días. Como no se les permite repetir pareja, en el $n$ -día, cada uno tiene que compartir una caja con un individuo no infectado, lo que lleva a $2n$ individuos infectados al final del día $n$ . Si hay exactamente $n + 1$ individuos infectados al final del día $n - 1$ entonces todavía es posible que algunos de ellos compartan una caja en el día $n$ pero $n$ es par, por lo que uno de estos $n + 1$ los individuos se verán obligados a compartir una caja con una persona sana.

-- EDITADO --

De hecho, todo grafo completo de orden par puede descomponerse en emparejamientos perfectos (véase el teorema 3.5 en la página 20 del libro One-Factorizations de W. D. Wallis).

Answer 4

Dejemos que $f(n)$ sea el número mínimo de enfermos en el día $n$ (secuencia $1, 2, 4, 4, 6, 8, 8, 8,\ldots$ si empezamos con $n=0$ ), dejemos que $g(n)$ es el número máximo de días que se puede mantener la enfermedad $\le n$ (secuencia $0, 1, 2, 2, 4, 4, 5, 5, 8, 8, \ldots$ si empezamos con $n=0$ ), por lo que $g(n)=\max \{k\mid f(k)\le n\}$ y $f(n)=\min\{k\mid g(k)\ge n\}$ retenciones. Queremos mostrar para $n\ge 1$ que $g(n)=r(n)+1$ donde $$\tag1 r(n):=\left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n4\right\rfloor+\left\lfloor\frac n8\right\rfloor+\ldots$$ es el exponente de $2$ en $n!$ . Por inspección, vemos que $g(n)=r(n)+1$ se mantiene al menos para $n\in\{1,2,3,\ldots,9\}$ .

Lema 0: $f(n)$ es incluso para $n>0$ . Si $n>1$ es impar entonces $g(n)=g(n-1)$ .

Prueba: Obviamente, después de que el paciente $0$ siendo el único enfermo inicialmente, los enfermos vienen por parejas según la última casilla en la que estaban. La afirmación sobre $g$ es dual a esto. $_\square$

Lema 1: $f(n+f(n))\le 2f(n)$ y $g(2n)\ge g(n)+n$ .

Prueba: Asegúrese de que $f(n)$ la gente está enferma el día $n$ , introduzca $f(n)$ personas frescas y dejar que se cofundan con la primera $f(n)$ personas de forma circular para la siguiente $f(n)$ días. La declaración sobre $g$ es dual a esto. $_\square$

Corolario: $g(n)\ge r(n)+1$ para todos $n\ge 1$ . $f(n)\le \mathrm{A007843}(n)$ .

Prueba: Observe que $r(2n+1)=r(2n)=r(n)+n$ por lo que los lemas 0 y 1 hacen inducción sobre $n$ trabajo. La afirmación sobre $f$ es doble (utilizando la descripción en OEIS). $_\square$

Lema 2: $g(n)\le n$ .

Prueba: Sólo hay que tener en cuenta que el paciente 0 no puede coboxitarse con más de $n-1$ otras personas. $_\square$

Corolario: $g(n)=r(n)+1$ si $n$ es una potencia de $2$ .

---

(continuará)