Killing Flies with a Checkerboard Flyswatter

Original Problem

Six flies rest on a table. You have a swatter with a checkerboard pattern, much larger than the table. Show that there is always a way to position and orient the swatter to kill at least five of the flies. Each fly is much smaller than a swatter square and is killed if any portion of a black square hits any part of the fly. (Source: The 2017 UW Math Hour Olympiad).

My Problem

Is it always possible to kill all $6$ flies? More generally, if there are $n$ flies on the table, how many can we guarantee to kill?

Progress

I haven't really made that much progress towards solving the stronger variant. The original problem can be proven in the following manner:

Orient the flyswatter such that one of its "edges" (if the flyswatter is placed on the Cartesian coordinate plane with one black square being $0\leq x,y\leq 1$, the edges are the lines $x=n$ or $y=m$ for integer $m,n$) coincides with the line between flies $1$ and $2$. Now, "slide" it along this line so that fly $3$ is also on an edge. So, flies $1,2,$ and $3$ are now all killed. We need to kill two of the remaining $3$ flies. We now consider this orientation and placement with the flyswatter "flipped" so that black squares are now white and white are now black. Since each of the $3$ remaining flies is killed by one of these orientations, at least one of them must kill $2$ of the remaining flies, and $5$ total.

This proof, when extended, shows that we can kill at least

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

flies if we have $n$, but doesn't seem to be terribly extendable beyond there. I tried to prove that, for at least one of the $\binom{6}{2}\cdot 4$ choices of the original flyswatter configuration, all $3$ remaining flies are killed by the same orientation, but I was unsuccessful in relating any one configuration with another.

The only idea I had was that it might be possible to prove that one can choose "fly $3$" in a smarter fashion to guarantee that all the remaining $3$ flies are killed by the same orientation, but I was unable to prove this and, even if proven, it is unlikely to generalize.

I was also unable to construct a counterexample (or even one that looks like a counterexample without a proof that it is one).

Solution 1:

Suppose the squares on the flyswatter have side length $1$. Then if $5$ of the $6$ flies are uniformly spaced around the boundary of a circle of radius $\frac{\sqrt2}{2}$ centered on the $6^{\text{th}}$ fly, we can't swat all flies at once.

If we want to swat all the flies, in particular we need to swat the center fly. So the center of the fly circle has to be contained in one of the black squares. Draw the diagonals of this black square (these are in blue in the diagram above). They cut the square into four right triangles, and the center fly must land in one of those triangles (a boundary is fine). Without loss of generality, the center fly is in the quarter adjacent to white square $A$, as in the diagram above.

I claim that the white square $A$ contains at least a $90^\circ$ arc of the fly circle. As a result, it must contain at least one of the other $5$ flies, since they are spaced $72^\circ$ apart, and that fly is spared.

To see this, first note that the arc contained in $A$ is minimized when the center fly lies on one of the blue diagonals. In fact, no matter where the center fly is, moving the fly downwards in the diagram (until it hits a blue diagonal) always either keeps the measure of this arc constant, or else decreases it.

By symmetry, let's also assume that the center fly is in the right half of the square. So we can consider the extremal case where the corners of the middle black square are at $\{(0,0), (0,1), (1,0), (1,1)\}$ and the center fly is at $(x,x)$ for $x \in [\frac12,1]$. In this case, the arc meets $A$ at two points: the point $(1,x + \sqrt{\frac12-(1-x)^2})$ and the point $(x - \sqrt{\frac12 - (1-x)^2}, 1)$. These form an angle of exactly $90^\circ$ with the point $(x,x)$, so the arc contained in $A$ is always at least this size.

(Note that we always have $0 \le x - \sqrt{\frac12 - (1-x)^2}$ and $x + \sqrt{\frac12-(1-x)^2} \ge 1$, which is what makes these intersection points valid and why we chose the radius $\frac{\sqrt2}{2}$.)

For very large $n$, we shouldn't be able to swat more than $(\frac12 + o(1))n$ of the files (that is, if $f(n)$ is the number of flies we can always swat out of $n$, then $\lim_{n \to \infty} \frac{f(n)}{n} = \frac12$).

This is probably true for just about any closely-packed arrangement of flies. But to be concrete, suppose we have $n = k^4$ flies packed in a $k^2 \times k^2$ square grid with a distance of $\frac1k$ between adjacent flies. Then no matter how these flies are placed on the flyswatter:

1. There are at least $\frac12k^2 - O(k)$ entire white squares in the convex hull of the fly formation. To see this, chop the plane up into $2 \times 2$ squares, each containing $2$ white squares and $2$ black squares of the flyswatter. Counting fractional squares, there have to be $\frac14k^2$ of these $2\times 2$ squares to cover the convex hull of the fly formation. There can be at most $O(k)$ fractional squares since their centers have to be within distance $\sqrt2$ of the boundary and are all at least distance $2$ apart from each other. So there are $\frac14k^2 - O(k)$ complete $2\times 2$ squares, each one of which contains $2$ white squares.
2. Each of these white squares contains at least $k^2 - O(k)$ flies, which are all spared as a result. A similar argument applies here. Draw a tiny square of side length $\frac1k$ centered at each fly; then each white square of the flyswatter contains $k^2$ tiny squares, counting fractions of tiny squares only partially contained, the fractions of tiny squares make an $O(k)$ contribution, and all tiny squares completely inside the white square contain a fly which survives.

So at least $\frac12 k^4 - O(k^3) = \frac12n - O(n^{3/4})$ of the flies survive. The error term certainly isn't optimal, but the fraction of $n$ obviously is.