Combinación de probabilidad y sistema binario en un problema de combinatoria

Question

Esta pregunta no es tan difícil pero me ha fascinado bastante la forma de resolverla. Se plantea de la siguiente manera:

Dados n estudiantes que participan en un concurso de m preguntas. En cada etapa, un estudiante puede elegir hacer la pregunta en inglés o en alemán o saltársela. Por cada dos preguntas, existe un alumno que elige hacer las dos preguntas y hacerlas en diferentes idiomas. ¿Cuál es el mayor valor que puede tomar m

Sugerencia : La respuesta a esta pregunta es $m \le 2^n$ , es de esperar que se utilice el sistema binario

He resuelto este problema, utilizando la inducción matemática. ¡Sin embargo, la solución utilizando la probabilidad simplemente parece mejor! ¡Se agradece cualquier solución!

Answer 1

Hay una solución muy sencilla con las secuencias binarias y el principio de encasillamiento.

Imagina una tabla cuyas filas están indexadas por el $m$ las columnas están indexadas por el $n$ estudiantes, y la entrada para la pregunta $q$ y el estudiante $p$ se determina como sigue:

• Si $p$ no contestó $q$ ou $p$ respondió $q$ en inglés, entonces la entrada es $0$ .

• Si $p$ respondió $q$ en alemán, entonces la entrada es $1$ .

Cada pregunta $q$ ahora tiene una fila de $0$ y $1$ asociados a ella. Afirmo que dos preguntas diferentes deben tener secuencias binarias diferentes. De hecho, para cada par de preguntas, existe un alumno que ha respondido a una pregunta en inglés y a la otra en alemán, lo que implica que una de las secuencias tiene un $0$ en ese lugar y otro como $1$ .

Dado que hay $2^n$ posibles secuencias binarias, y cada una de las $m$ preguntas tiene una diferente, debe ser el caso que $m\le 2^n$ . (Esto puede verse como una aplicación del principio de encasillamiento; si se asume $m\ge 2^n+1$ (entonces, si las preguntas son palomas y las secuencias son casilleros, se tendrían dos palomas en el mismo casillero, contradiciendo lo establecido anteriormente).