Matar moscas con un matamoscas de tablero de damas

Question

Problema original

Seis moscas descansan en una mesa. Tienes un matamoscas con un patrón de tablero de ajedrez, mucho más grande que la mesa. Muestra que siempre hay una manera de posicionar y orientar el matraz para matar al menos cinco de las moscas. Cada mosca es mucho más pequeña que un matamoscas cuadrado y se mata si cualquier porción de un cuadrado negro golpea cualquier parte de la mosca. (Fuente: El Olimpiada de la hora de las matemáticas de la Universidad de Washington en 2017 ).

Mi problema

¿Siempre es posible matar a todos $6$ ¿Las moscas? Más generalmente, si hay $n$ moscas en la mesa, ¿cuántas podemos garantizar que mataremos?

Progreso

No he hecho muchos progresos para resolver la variante más fuerte. El problema original se puede probar de la siguiente manera:

Orientar el matamoscas de tal manera que uno de sus "bordes" (si el matamoscas se coloca en el plano de coordenadas cartesianas con un cuadrado negro siendo $0 \leq x,y \leq 1$ los bordes son las líneas $x=n$ o $y=m$ para el número entero $m,n$ ) coincide con la línea entre las moscas $1$ y $2$ . Ahora, "deslícelo" a lo largo de esta línea para que la mosca $3$ también está al límite. Así que, las moscas $1,2,$ y $3$ ahora están todos muertos. Necesitamos matar a dos de los restantes $3$ moscas. Ahora consideramos esta orientación y colocación con el matamoscas "volteado", de modo que los cuadrados negros son ahora blancos y los blancos son ahora negros. Ya que cada uno de los $3$ las moscas que quedan mueren por una de estas orientaciones, al menos una de ellas debe matar $2$ de las moscas restantes, y $5$ total.

Esta prueba, cuando se amplía, muestra que podemos matar al menos

$$ \left\lceil \frac {n+3}{2} \right\rceil $$

moscas si tenemos $n$ pero no parece ser terriblemente extensible más allá de allí. Traté de probar que, por lo menos uno de los $ \binom {6}{2} \cdot 4$ las opciones de la configuración original del matamoscas, todas $3$ Las moscas que quedan mueren por la misma orientación, pero no tuve éxito en relacionar una configuración con otra.

La única idea que tenía era que podría ser posible probar que uno puede elegir "volar" $3$ " de una manera más inteligente para garantizar que todos los restantes $3$ las moscas mueren por la misma orientación, pero no pude probar esto y, aunque se pruebe, es poco probable que se generalice.

Tampoco pude construir un contraejemplo (o incluso uno que se parezca a un contraejemplo sin una prueba de que lo sea).

Answer 1

Supongamos que los cuadrados del matamoscas tienen una longitud lateral $1$ . Entonces si $5$ de la $6$ las moscas están uniformemente espaciadas alrededor del límite de un círculo de radio $ \frac { \sqrt2 }{2}$ centrado en el $6^{ \text {th}}$ mosca, no podemos aplastar todas las moscas a la vez.

Si queremos aplastar todas las moscas, en particular necesitamos aplastar la mosca central. Así que el centro del círculo de la mosca tiene que estar contenido en uno de los cuadrados negros. Dibuja las diagonales de este cuadrado negro (están en azul en el diagrama de arriba). Cortan el cuadrado en cuatro triángulos rectos, y la mosca central debe aterrizar en uno de esos triángulos (un límite está bien). Sin pérdida de generalidad, la mosca central está en el cuarto adyacente al cuadrado blanco $A$ como en el diagrama de arriba.

Afirmo que el cuadrado blanco $A$ contiene al menos un $90^ \circ $ arco del círculo de la mosca. Como resultado, debe contener al menos uno de los otros $5$ moscas, ya que están espaciadas $72^ \circ $ aparte, y esa mosca se salva.

Para ver esto, primero note que el arco contenido en $A$ es minimizado cuando la mosca central se encuentra en una de las diagonales azules. De hecho, no importa dónde se encuentre la mosca central, el movimiento de la mosca hacia abajo en el diagrama (hasta que llega a una diagonal azul) siempre mantiene constante la medida de este arco, o bien la disminuye.

Por simetría, asumamos también que la mosca central está en la mitad derecha del cuadrado. Así que podemos considerar el caso extremo en el que las esquinas del cuadrado negro medio están en $\{(0,0), (0,1), (1,0), (1,1)\}$ y la mosca central está en $(x,x)$ para $x \in [ \frac12 ,1]$ . En este caso, el arco se encuentra $A$ en dos puntos: el punto $(1,x + \sqrt { \frac12 -(1-x)^2})$ y el punto $(x - \sqrt { \frac12 - (1-x)^2}, 1)$ . Estos forman un ángulo de exactamente $90^ \circ $ con el punto $(x,x)$ así que el arco contenido en $A$ es siempre al menos de este tamaño.

(Nótese que siempre tenemos $0 \le x - \sqrt { \frac12 - (1-x)^2}$ y $x + \sqrt { \frac12 -(1-x)^2} \ge 1$ que es lo que hace que estos puntos de intersección sean válidos y por qué elegimos el radio $ \frac { \sqrt2 }{2}$ .)

---

Para los muy grandes $n$ no deberíamos ser capaces de aplastar más que $( \frac12 + o(1))n$ de los archivos (es decir, si $f(n)$ es el número de moscas que siempre podemos aplastar $n$ Entonces $ \lim_ {n \to \infty } \frac {f(n)}{n} = \frac12 $ ).

Esto es probablemente cierto para casi cualquier arreglo de moscas. Pero para ser concretos, supongamos que tenemos $n = k^4$ moscas empaquetadas en un $k^2 \times k^2$ cuadrícula cuadrada con una distancia de $ \frac1k $ entre las moscas adyacentes. Entonces, no importa cómo se coloquen estas moscas en el matamoscas:

1. Hay al menos $ \frac12k ^2 - O(k)$ cuadrados blancos enteros en el casco convexo de la formación de la mosca. Para ver esto, corta el avión en $2 \times 2$ cuadrados, cada uno de los cuales contiene $2$ cuadrados blancos y $2$ cuadrados negros del matamoscas. Contando los cuadrados fraccionarios, tiene que haber $ \frac14k ^2$ de estos $2 \times 2$ cuadrados para cubrir el casco convexo de la formación de la mosca. Puede haber como mucho $O(k)$ cuadrados fraccionarios ya que sus centros tienen que estar dentro de la distancia $ \sqrt2 $ de la frontera y todos están a una distancia mínima $2$ aparte de cada uno de ellos. Así que hay $ \frac14k ^2 - O(k)$ completo $2 \times 2$ cuadrados, cada uno de los cuales contiene $2$ cuadrados blancos.
2. Cada uno de estos cuadrados blancos contiene al menos $k^2 - O(k)$ moscas, que se salvan como resultado. Un argumento similar se aplica aquí. Dibuja un pequeño cuadrado de longitud lateral $ \frac1k $ centrado en cada mosca; entonces cada cuadrado blanco del matamoscas contiene $k^2$ cuadrados diminutos, contando fracciones de pequeños cuadrados sólo parcialmente contenidos, las fracciones de pequeños cuadrados hacen un $O(k)$ y todos los pequeños cuadrados completamente dentro del cuadrado blanco contienen una mosca que sobrevive.

Así que al menos $ \frac12 k^4 - O(k^3) = \frac12n - O(n^{3/4})$ de las moscas sobreviven. El término de error ciertamente no es óptimo, pero la fracción de $n$ obviamente lo es.