square cake with raisins

Solution 1:

Edit (31 May 2013): The proof of the upper bound below is wrong (see comments), the lower bound should still hold.

Let $p(n)$ be the optimal value of $p$ if both players play optimally. I will prove that $p(n)\leq (n+2)/3$ and will sketch a proof of $p(n)\geq C n$ for an absolute constant $C>0$.

Alice can attain $p(n)\leq (n+2)/3$. Proof is by induction on $n$. Identify the cake with $[0,1]^2$ in the Cartesian plane. Place three raisins at $(0,1)$, $(1,0)$, and $(1,1)$. Then take an optimal placement of $n-3$ raisins, scale by a factor $1/3$ to make a placement in $[0,1/3]^2$. The result is a set of $n$ raisins. Now, if $p\geq 2$, then at most one of the three corner raisins belong to a square. We thus obtain that either $p(n)<2$ or $p(n)\leq 1+p(n-3)$. In either case, the induction step is complete.

Next I explain Bob's strategy. Assume that instead of $[0,1]^2$ square the whole game happens on the infinite plane $\mathbb{R}^2$. So, the squares are allowed to extend beyond cake's boundary. Before cutting the squares out, which is an irreversible operation, Bob should mentally choose which squares to cut, as follows. He starts with no squares at all. For each raisin $r$ there is a unique smallest square $S(r)$ that is centred at $r$ and contains at least one other raisin. (I assume that $n\geq 2$ for $S(r)$ to be well-defined.) At each step Bob does the following:

1) If square $S(r)$ does not intersect any of the squares in his mental list, then Bob add $S(r)$ to the list.

2) If square $S(r)$ meets some existing squares, then $S(r)$ is added only if it is smaller than the squares that it intersects. In that case, the square it intersects are removed from the list.

The process terminates because if we sort the squares sizes, then the resulting sequence becomes lexicographically smaller at each step.

Now if the point $r'$ is not in the resulting list of squares because $S(r')$ intersects some smaller (or equal) $S(r)$, then we say that the point $r'$ blames the point $r$. I claim a point $r$ can be blamed by at most $8$ other points. Sadly, I do not see a clean proof, though it is fairly obvious from drawing the pictures. Assuming the claim, it follows that $n$ is at most $9$ times the number of squares (each square contains the centre, and at most eight other points can blame it).

In the above I assumed that the game is played on $\mathbb{R}^2$. I do not think it should be a major difficulty, but again I do not see a clean way to deal with it either.

Solution 2:

I think I found an upper bound:

$$P(n) \leq ceiling({n \over 2}) - 1$$

PROOF (following the discussion with Boris Bukh): suppose the number of raisins is $n=2k+2$ (with $k \geq 1$), and suppose the cake is the square $[1,3^k]x[1,3^k]$.

Alice can place the raisins in the following positions:

$(1,1) (1,3) (1,9) ... (1,3^k)$

$(3,1) (9,1) ... (3^k,1) (3^k,3^k)$

What is the best Bob can do?

• First, consider the top-right raisin $(3^k,3^k)$. The chessboard distance between this raisin and any other raisin is $3^k-1$, which is the length of the entire cake. Therefore, the only piece that can use that raisin is the entire cake. Therefore, Bob had better discard this raisin and not use it.
• Now, the remaining raisins are: One bottom-left raisin $(1,1)$; k left-side raisins $(1,3^i)$, and k bottom-side raisins $(3^j,1)$. Any piece that uses a bottom-side raisin and a left-side raisin necessarily contains the bottom-left corner $(1,1)$, therefore Bob can have at most one such piece. All other pieces must use either two bottom-side raisins, or two left-side raisins.
• Suppose Bob cuts a left-side piece that contains two adjacent raisins $(1,3^i)$ and $(1,3*3^i)$, with $1 \leq i \leq k-1$. The side-length of this piece is at least $2*3^i$. Therefore it contains the point $(2*3^i,2*3^i)$. The same goes for any bottom-side piece that contains the two adjacent raisins $(3^i,1)$ and $(3*3^i,1)$. Therefore, Bob can have only one of those two pieces, and therefore he can have at most k-1 pieces that contain bottom-side or left-side pieces (for $1 \leq i \leq k-1$).
• In total, Bob can have at most k square pieces, proving the upper bound $p \leq ceiling(n/2)-1$.

ADDITION (2013-06-12): Suppose Bob is allowed to cut, not only squares, but also R-balanced rectangles, defined as rectangles whose width/height ratio is between R and 1/R, for $R \geq 1$ (note that a square is 1-balanced).

Alice can use the above construction, with two minor modifications:

• Instead of 3, use a factor of $(2+R)$ .
• Drop the top-right raisin (now the total number of raisins is $2k+1$).

Bob can still have at most k square pieces, and the upper bound is $p \leq floor(n/2)$.

Thus, allowing r-balanced rectangles instead of squares, for any finite r, doesn't improve Bob's situation very much - it allows him to get either zero or one additional piece.