14
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Another way of formulating the question is "what is the minimum number of flies which cannot be swatted with a checkerboard". This can be generalised to more than two dimensions as well. It seems to me to be a good question. $\endgroup$ – Mark Bennet Feb 25 '18 at 22:34
  • 1
    $\begingroup$ If a single swatter square was bigger than the table you could guarantee killing all the flies ! The question must be looking for guaranteed minimum kill not only for any arrangement of flies, but also for any possible ratio of areas. $\endgroup$ – WW1 Feb 26 '18 at 1:21
  • $\begingroup$ @WW1 Yes. My question is over all possible areas of the table for a fixed flyswatter square size (or all possible flyswatter square sizes for a fixed table size, if you prefer). $\endgroup$ – Carl Schildkraut Feb 26 '18 at 5:22
  • 1
    $\begingroup$ Perhaps it would be worth considering the (perhaps simpler) $n=5$ case? A proof that all $5$ flies can be killed (or a counterexample) may offer some insight into the $n=6$ and general $n$ cases. $\endgroup$ – Connor Harris Feb 28 '18 at 15:25
  • $\begingroup$ @user254433 What relevance does this have to the question? $\endgroup$ – Carl Schildkraut Mar 2 '18 at 3:03
10
+150
$\begingroup$

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.

flyswatter diagram

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer! If I'm interpreting this correctly, it gives a proof that, of $n$ flies, you can (necessarily) get at most $\left\lfloor\frac{3n+2}{4}\right\rfloor$ of them. Do you have any idea or instinct how sharp this is for large $n$? $\endgroup$ – Carl Schildkraut Mar 2 '18 at 18:26
  • $\begingroup$ How do you get $\left\lfloor\frac{3n+2}{4}\right\rfloor$? The only upper bound I can think of that follows immediately is $\left\lceil \frac56 n\right\rceil$, and I suspect that that's not tight. $\endgroup$ – Misha Lavrov Mar 2 '18 at 19:28
  • $\begingroup$ Sorry - I mean $\left\lceil \frac{3n+2}{4}\right\rceil$. If you put $n-1$ points around a circle of radius $\sqrt{2}/2$. You will always miss an arc of at least $90^{\circ}$, which contains at least $\lfloor \frac{n-2}{4}\rfloor$ points. Is this logic correct? Edit: It's not; the solution given presumes the center point is necessarily chosen. It shouldn't be too hard to prove that even if the center point is not chosen, you can't miss less than $90^{\circ}$, but I'm not sure. $\endgroup$ – Carl Schildkraut Mar 2 '18 at 19:52
  • 1
    $\begingroup$ I've added an argument that explains why, for large $n$, we can't swat more than $\frac12n$ plus a lower-order term of the flies. $\endgroup$ – Misha Lavrov Mar 3 '18 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.