Alice bakes a square cake, with $n$ raisins (= points).
Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins.
Note that a single raisin can be shared by two pieces (if it is on their boundary), or even four pieces (if it is on their corner).
Bob tries to maximize the number of pieces $p$, and Alice tries to minimize $p$ by a sophisticated placement of the raisins.
For a given $n$ (number of raisins), how should Alice place the raisins such as to minimize $p$, and what is the minimum?
Here are some simple cases:
- For n=0, 1, obviously p=0.
- For n=2, 3, 4, Alice can make p=1, by placing the raisins on the corners of the cake, since the only square piece that can contain 2 raisins is the entire cake.
- For n=5, the minimum p is 2: there is at least one quarter of the cake that contains 2 raisins. Bob can cut a piece that contains these 2 raisins on its boundary, and is entirely contained within that quarter of the cake. Now there is enough room for another square, that contains one of these raisins and another raisin.
What is the minimum $p$ for a given $n$?
- Given two raisins, the minimum length of a square that contains both of them is the chessboard distance between them.
- Therefore, it seems that Alice's best strategy is to maximize the chessboard distances, and so force Bob to use large squares. This makes sense, but I cannot prove this.
- If n is a square number ($n = k^2$), then Alice can place the raisins in a k-by-k grid, such that the smallest chessboard distance between raisins is $1/(k-1)$. In this case, Bob can cut at most $(k-1)^2$ squares. But is this really Alice's best strategy?
- Bob can always do best with pieces that have raisins only on their boundary (He never has to cut a piece which has a raisin in the interior). PROOF: For any two raisins, there is a square that contains both of them in the boundary. If a piece contains two raisins in the interior, or one in the interior and one in the boundary, Bob can shrink that piece to get a square that has these two raisins in the boundary. This square will be entirely contained in the original square, and so will not affect the other pieces.