Las preguntas menos deberían estar preparadas para un examen

Question

$N$ de los estudiantes realizarán una prueba de papel con $M$ pregunta y para la consideración de la trampa, cada papel será diferente, pero no totalmente. Hay en la mayoría de las $K$ preguntas de la misma en cualquiera de los dos papeles. Dada la $N$, $M$ y $K$, $I$ quiero saber el menor número de preguntas debe ser preparado.

Ejemplo:

$N = 3\qquad 3~ \text{estudiantes} \\ M = 2 \qquad 2 ~\text{preguntas} \\ K = 1 \qquad \text{1 pregunta es la misma}$

Respuesta: $3$ (te $3$ preguntas ABC y luego del primer alumno de papel es AB, el segundo es BC y la tercera es AC)

Otro Ejemplo:

$N = 12\qquad M = 3\qquad K = 1$

Respuesta: $9$

111000000 -> means first student's paper is `ABC`
100110000 -> means second student's paper is `ADE`
010101000
001100100
000011100
010010010
001001010
100000110
001010001
100001001
010000101
000100011

La matriz es de $12 \times 9$, significa $9$ preguntas es suficiente para $12$ papel con $3$ preguntas y en la mayoría de las $1$ misma pregunta de a pares.

Answer 1

Este es uno de los problemas clásicos en teoría de conjuntos Extremal, y no es ninguna solución combinatoria simple, que supongo que están esperando. Este trabajo arrojará algo de luz sobre su complejidad.