square cake with raisins

Question

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$?

-

Some insights:

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

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

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

Answer 3

Too long for a comment, so I am posting it here.

i can tell the strategy that i think is the best for Alice to place the raisins:

first, put 4 raisins at the four corners, and call any two diaginal raisins A and B;

then,put 2 raisins C and D inside the square, or in the boundary,each raisin A or B can form a square with one of the two raisins that is nearer to it,and take the segment CD as the diagonal, you can form a rectangle inside the square;

then, put another two raisins E and F inside the rectangle or in the boundary, each raisin of C and D can form a square with E or F, and take EF as the diagonal, you can form a smaller rectangle inside the rectangle,continue in this way, untill Alice used all the n raisins.

Answer 4

I think I found a lower bound.

Here is a recursive algorithm Bob can use:

If $n \leq 1$, then no pieces are possible; If $2 \leq n \leq 4$, then a single piece is possible; and if $5 \leq n \leq 8$, then at least 2 pieces are possible.

If $8 \leq n$, Divide the cake (without cutting it) to 4 identical square quarters. Count the number of raisins in each quarter. Proceed according to the number of quarters with at least 2 raisins (there must be at least one such quarter):

• Case 1: There is exactly 1 quarter with at least 2 raisins. In this case, the other 3 quarters contain at most 3 raisins. Shrink the former quarter until the remainder contains exactly 4 raisins. The remainder can be covered by 3 (possibly overlapping) squares, and contains 4 raisins, so at least one of the 3 covering squares contains 2 raisins, and Bob can cut a single piece out of it. The shrinked quarter contains at least $n-3$ raisins. Cut it recursively.
• Cases 2, 3, 4: There are 2, 3 or 4 quarters with at least 2 raisins. Cut each of them recursively, and ignore the other quarters.

Let $P(n)$ be the number of pieces Bob can get with this algorithm:

• $n \leq 1$: $P(n)=0$.
• $2 \leq n \leq 4$: $P(n) \geq 1$.
• $5 \leq n \leq 8$: $P(n) \geq 2$.
• $8 \leq n$: $P(n)$ is at least the minimum of the following cases:
  • Case 1: $1 + P(n-3)$
  • Case 2: $min_{i,j}P(i) + P(j)$, such that $i+j+2 = n$, and $i,j \geq 2$.
  • Case 3: $min_{i,j,k}P(i) + P(j) + P(k)$, such that $i+j+k+1 = n$, and $i,j,k \geq 2$.
  • Case 4: $min_{i,j,k,l}P(i) + P(j) + P(k) + P(l)$, such that $i+j+k+l = n$, and $i,j,k,l \geq 2$.

These recurrence relations hint that $P(n)$ is linear. To find a lower bound on $P(n)$, we will assume that there are some $a$ and $b$ such that:

$$P(n) \geq {(n+b) \over a}$$

and prove this by induction. During the induction proof, we will find what $a$ and $b$ must be in order for the proof to be correct.

First, the relation must be true for all $2 \leq n \leq 8$. Thus:

• For $2 \leq n \leq 4$, it must be true that: $1 \geq (n+b)/a$. Thus: $a \geq b+4$.
• For $5 \leq n \leq 8$, it must be true that: $2 \geq n/a + b$. Thus: $2a \geq b+8$.

• For $8 \leq n$, we have to check all 4 cases:

  • Case 1: $1 + P(n-3) \geq 1 + (n+b-3)/a = (n+b+a-3)/a \geq (n+b)/a$. For this to hold, we must have: $a \geq 3$.
  • Case 2: $P(i) + P(j) \geq (i+j+2b)/a = (n-2+2b)/a \geq (n+b)/a$. For this to hold, we must have: $b \geq 2$.
  • Case 3: $P(i) + P(j) + P(k) \geq (i+j+k+3b)/a = (n-1+3b)/a \geq (n+b)/a$. For this to hold, we must have $2b \geq 1$ (this trivially follows from the previous requirement).
  • Case 4: $P(i) + P(j) + P(k) + P(l) \geq (n+4b)/a > (n+b)/a$. For this to hold, we must have $3b \geq 0$ (this trivially follows from the previous requirement).

The assignment $a=6$ and $b=2$ fulfils all the requirements. Thus we get the following lower bound:

$$ P(n) \geq {(n+2) \over 6} \ \ \ \ \ [n \geq 2]$$

There is still a large gap between the lower bound of approximately $n/6$, to the upper bound of approximately $n/2$.

Exercises to the readers:

• Prove a better lower bound, of approximately $n/4$, for the case where Bob is allowed to cut, not only squares but also 2-balanced rectangles (i.e. rectangles whose width/height ratio is between 1/2 and 2). Note that in this case, the upper bound is still approximately $n/2$.
• Suppose Bob finds a way to cut 3 squares in a cake with 7 raisins (this is in par with the upper bound). Based on this assumption, prove a better lower bound, of approximately $n/4$, for $n \geq 5$. Hint: you have to split some of the cases to sub-cases, where some of the rectangles contain at least 2 but less than 5 raisins.