¿Puede este rompecabezas ser resuelto matemáticamente?

Question

Hay $6$ personas en un barco. Como el viaje es largo, deciden tomar turnos. En cada turno, algunos de despertador y de control de la nave mientras otros duermen. Cómo muchos de estos cambios son necesarios para que dos personas $A$ e $B$ existe un cambio tal que $A$ despierta y se $B$ duerme (mínimo)?

Yo:

No sé por qué, pero sentí que el número mínimo de sesiones será cuando $3$de las personas duerme y el otro $3$ wake. Así llegué a la siguiente solución :

El SUEÑO
123
356
146
245

Por lo que el número de sesiones es de 4. Pero creo que mi solución a ser una cuestión de suerte. Así que mi pregunta es
"Hay una solución matemática a esta pregunta?"

Answer 1

La prueba de que $4$ es un límite inferior para el número de cambios necesarios:

Hay $6\cdot5=30$ pares ordenados $(A,B)$ de personas distintas de las personas en el barco, por lo que los cambios deben combinar para tener al menos $30$ pares ordenados de (persona despierta, dormida persona).

Si en un turno $k$ la gente está despierta y $6-k$ está dormido, entonces el número de pares ordenados es $k(6-k)$. Esto se maximiza cuando se $k=3$, cuando no se $9$ tales pares ordenados.

Por lo tanto, es imposible para $3$ turnos para cubrir todas las posibilidades, ya que no puede haber más de $27$ pares ordenados cubierto entre ellos.

Answer 2

Supongamos que tenemos listas $$L_1,L_2,...,L_k$$ of sleeping people. List $ L_i$ connect with a pair of people $ \ {x, y \}$ if exactly one of them is on the list. Let $ s_i = | L_i |$. Then list $ L_i$ is connected with at most $% # PS