26
$\begingroup$

Pizza strategy game

Two friends A, B want to share a (circular) pizza, by playing a game.

A does a (straight line) cut
B also does a cut
A does another cut and
B does the last cut.

Now they alternate turns picking one slice at a time until last, starting from A.

Does B have a strategy (at least) not to eat less pizza?

I think the key is to make equal pieces, i.e. splitting the pizza in pairs of pieces of equal area.

$\endgroup$
  • 3
    $\begingroup$ Are you allowed to fold the pizza? $\endgroup$ – Viktor Mellgren Oct 26 '17 at 10:43
  • 1
    $\begingroup$ How do you define a cut? Does it need to pass the center of the pizza? Does it need to be made perpendicular to the top surface of the pizza? $\endgroup$ – Joel Reyes Noche Oct 27 '17 at 13:35
47
$\begingroup$

Yes, $B\;$can achieve equality.

Assume the players are not allowed to make no cut (i.e., pass), but are allowed to make a cut which coincides with a previous cut.

After $A$'s first cut, let $B\;$make a cut, $l\;$say, along the perpendicular bisector of $A$'s cut.

Thereafter, for every cut that $A\;$makes, let $B\;$make a cut symmetrical about $l\;$to $A's$ cut (i.e., the same cut as $A$ except reflected about the line $l$). Note: It might coincide with $A$'s cut.

It follows that every final piece appears with even multiplicity, up to congruence, so in the worst case, as $A\;$chooses pieces, $B$'s next choice can at least match.

$\endgroup$
  • $\begingroup$ Wow thanks a lot for your solution!! I understand the first two cuts: this way we have 4 pieces, equal by two. Can you explain the rest? How does B make a cut symmetrical about l to A's cut? $\endgroup$ – Samuel Oct 26 '17 at 1:35
  • 1
    $\begingroup$ I edited in an explanation (and a slight modification of the rules). $\endgroup$ – quasi Oct 26 '17 at 1:41
  • 12
    $\begingroup$ NIce answer! Note that if A's second cut is symmetrical about B's first cut, then that means that B's second cut can really be any other cut symmetrical about B's first cut, so B's second cut need not coincide with A's second cut in that case. $\endgroup$ – Bram28 Oct 26 '17 at 1:46
  • 2
    $\begingroup$ Even if $A$ is allowed to pass on his first cut, $B$ can just pick a diameter on his first cut, and he's good to go. $\endgroup$ – Arthur Oct 26 '17 at 7:13
  • 2
    $\begingroup$ @Sheljohn: After every cut by $B$, the two sides of the line $l$ are mirror images of each other, so for every region on one side of the line, there is a reflected version (hence congruent) on the other side. $\endgroup$ – quasi Oct 26 '17 at 15:07
39
$\begingroup$

To illustrate @quasi's excellent answer:

  1. $A$ makes the lower cut, in red
  2. $B$ makes the blue bisector to the lower cut, crossing the midpoint, $D$
  3. $A$ makes the upper, red cut
  4. $B$ makes the upper blue cut, which is the reflection the upper, red cut in the blue bisector

enter image description here

After this, $A$ and $B$ can each take turns in taking the next biggest piece and end up with half a pizza each.

$\endgroup$
  • 1
    $\begingroup$ Nice illustration! $\endgroup$ – Bram28 Oct 26 '17 at 1:50
  • 1
    $\begingroup$ @Bram28 Nice answer :) $\endgroup$ – Jam Oct 26 '17 at 1:53
  • 1
    $\begingroup$ @Jam I would've preferred italian sausage :) Speaking of that, the problem becomes more interesting if you take toppings into account - how does B ensure he gets an equal amount of pepperoni as A? $\endgroup$ – Χpẘ Oct 26 '17 at 3:42
  • 3
    $\begingroup$ @Χpẘ (it's hard for people to ping you with your username): That is an interesting question. Namely given a density function on the disk, can B ensure he gets the same mass (integral of density over the chosen pieces)? I think the answer is no, but it's complicated: A first cuts into two different (in mass) pieces. After the first 2 moves, A can make a new cut near where a prior cut met the edge to create 2 tiny distinct pieces, such that there are now 3 tiniest pieces with masses $x,y,z$ where $x \ll y \ll z$. Then 1 more cut cannot make the 2 tiniest sizes each have 2 pieces. Lots of cases! $\endgroup$ – user21820 Oct 26 '17 at 7:49
  • 3
    $\begingroup$ I suppose you deserve -1 for choosing a pizza with chorizo. $\endgroup$ – Evargalo Oct 26 '17 at 12:20
2
$\begingroup$

Like many card games (bridge, whist, 500, etc.) there is a bidding/cutting stage and a playing/selecting stage.

The required strategy boils down to the single/final cut stage - where the following player gets to choose a piece and thus the best strategy for cutting is to ensure an equal partition exists (as OP suggests). In this case since A always gets to choose first, B has to ensure balance. With N rounds the obvious equal partition criterion is that there exists a partitioning into two sets of N pieces with equal total area. Leaving 2N-1 pieces is bad because A can always choose at least as big a piece as B will get (greedy selection), and then gets an extra piece at the end.

The obvious way of achieving the equal partition criterion is for B to always cut so as to achieve even reflective symmetry (as explained by @quasi and illustated by @jam). Note that B must always achieve an even number of pieces so B's first cut must divide both segments left by A while ensuring matching sizes for each selection stage as A can always be greedy and get ahead, and B has to be able to catch up immediately or will never catch up (given A adopts a greedy strategy).

A greedy selection strategy is thus appropriate for B as well - always take the biggest remaining piece.

What happens if A achieves the symmetric equal partition criterion? Then if B is allowed to make no cut or repeat a cut that is a solution, otherwise any cut perpendicular to the axis maintains the criterion.

Note that this is a slightly more general (necessary and sufficient) strategy than that of quasi (for the generalization to N pairs of cuts). For example, it will sometimes be possible to enforce even symmetry along another axis than B's first cut - e.g. A's first cut if it is a diameter.

Note that I am familiar with other forms of this problem (literally - my family used this approach for "cakes" more often than pies or pizzas, not to mention the related problems for "treasure" where dividing rather than cutting).

  1. At least 2 people, but the straight line cut need not be an unbounded line, but can for example create a sector (cut to an approximate centre where there is already a cut to or through the centre, e.g. an approximate diameter - used with round cakes). Once an initial cut has been made, anyone can choose to take a piece rather than cut.

  2. At least 2 people, but each bar the last making a single cut, last choosing first and the rest choosing in the same order (they will always have at least one portion to choose from that they deem fair or better if they cut to make a fair segment (usually a problem involving rectangular cake and making full width cuts).

$\endgroup$

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.