Billetes de "Lotería Matemática" - encontrar el conjunto mínimo ganador

Question

La "lotería matemática" se juega de la siguiente manera: un jugador marca seis casillas en un cuadrado de 6x6 de 6x6. A continuación, se extraen seis "casillas perdedoras". Un jugador gana si ninguna de las casillas perdedoras está marcado en su billete de lotería.
1)Demostrar que se pueden completar nueve boletos de lotería de tal manera que al menos uno de de ellos gane.
2)Demuestra que esto no es posible con sólo ocho entradas.

Mi intento es el siguiente;

Primero dividí el cuadrado en 6 rectángulos (figura 1).
Si uno de los rectángulos no contiene una cruz, entonces algún boleto (boleto 1 a boleto 6) ganaría el juego.

Ahora consideramos el caso en el que cada rectángulo tiene una cruz.
Ahora toma los dos rectángulos de la parte superior izquierda del cuadrado (figura 2). Estos tienen un total de dos cruces.
Las dos primeras columnas juntas contienen una cruz y la tercera y cuarta columnas juntas contienen una cruz.
Hay cuatro casos y necesitamos al menos cuatro boletos (del boleto 7 al boleto 10) para asegurar la victoria.

Sólo voy a conseguir un mínimo de diez entradas. Cómo puedo demostrar que sólo se requieren nueve entradas y que por ocho no es posible?

Referencia: Combinatoria de Stephan Wagner, página 42, problema 49 . https://math.sun.ac.za/swagner/Combinatorics.pdf

Answer 1

Sólo para dar una opción concreta de 9 boletos que tendrán al menos un boleto ganador:

Supongamos, por el contrario, que todos ellos son billetes perdedores. Los amarillos obligan a 3 casillas perdedoras en la mitad superior. Entonces los 3 cuadrados perdedores restantes llenarán la mitad inferior. Por el encasillamiento, al menos 2 de estos cuadrados perdedores estarán en el 3x3 inferior izquierdo o en el 3x3 inferior derecho.

Digamos que hay al menos dos casillas perdedoras en el 3x3 inferior izquierdo, lo que significa que como máximo hay una casilla perdedora en el 3x3 inferior derecho. En este caso, uno de los boletos rojos no tendrá una casilla perdedora, ya que la casilla perdedora está en una de las 3 columnas.

Y viceversa, si al menos dos casillas perdedoras están en el 3x3 de abajo a la derecha, entonces uno de los boletos morados no tendrá una casilla perdedora.

Editar. También se puede encontrar una referencia para este problema aquí https://www.cut-the-knot.org/pigeonhole/MathLotto.shtml

Answer 2

Aquí se demuestra que, dado un conjunto de 8 boletos, siempre podemos encontrar 6 casillas perdedoras tales que cada boleto ha marcado al menos una casilla perdedora.

Si hay una casilla que está marcada en 3 boletos, elegimos esa casilla junto con una casilla de cada uno de los otros 5 boletos para ser perdedores. Supongamos entonces que cada casilla está marcada como máximo en 2 boletos. Por el principio del casillero, debe haber una casilla marcada exactamente en dos boletos; llámese casilla A. Los 6 boletos restantes evitan la casilla A, así que aplicando de nuevo el principio del casillero, debe haber una casilla diferente marcada en dos de los 6 boletos restantes; llámese casilla B. Como casillas perdedoras, elegimos entonces la casilla A, la casilla B y una casilla de cada uno de los 4 boletos restantes.

Un argumento muy similar puede demostrar que, si tenemos una colección de 9 boletos con la propiedad de que al menos uno será ganador, entonces no se puede marcar ninguna casilla en 3 o más de esos boletos.