11
$\begingroup$

You are an inmate at Infinity Prison, where prisoners must work together to solve a challenging riddle every day to ensure their very survival. But today is your lucky break; the warden has decided to throw a pizza party!

The catch: the prisoners only get to eat the pizza if they divide it fairly, one slice per prisoner. If the warden is not satisfied with fairness, they'll all be executed.

The other catch: no one but the warden knows how many prisoners there are; just that it's a very large number.

The warden places a single, giant, circular pizza in a room, otherwise empty except for:

  • A pen and sheet of paper.
  • A pizza cutter.
  • An InfinityTech™ digital protractor (can measure angles of arbitrary precision).

The rules:

  1. Each prisoner enters the room once, one at a time.
  2. Each prisoner must make a single, straight cut from the edge of the pizza to the center.
  3. If anyone interacts with the pizza in any other way, every prisoner will be executed.

Eventually your turn is called, and to your dismay you find an untouched pizza and blank piece of paper; you're the first one in the room. What do you do to absolutely guarantee your survival?

Some assumptions you can make (not really spoilers, just clarifications):

All other prisoners want to survive as well, and know the rules, but you're not sure how smart they are.


Each prisoner can make perfectly straight cuts, and use the protractor to measure any real angle with perfect accuracy.


There's absolutely no way to determine how many prisoners there are; cells are soundproof with no windows and only one prisoner is let out at a time.


"Fairly" is to be judged by the warden; you're not 100% sure how it's judged but you have some guesses. Different solutions are possible given different definitions and that's ok; we're no longer looking for a single "best" solution.


Don't worry about toppings. You'll only be judged on crust volume.


There's no trick or outside-the-box thinking required. Just pure logic. For instance, the answer is nothing like "live in the room and eat the infinitely large pizza until you die of old age".

EDIT: The top answers are already better than the answer I had in mind; in retrospect this is because I didn't add enough constraints, but the solutions people are coming up with are so interesting I think it's best to leave it open-ended.

$\endgroup$
  • 7
    $\begingroup$ I believe your "semi-spoiler" should be unspoilered because it's a crucial part of the definition of the puzzle; without that this puzzle is a bit underspecified. $\endgroup$ – ffao Sep 23 '17 at 4:29
  • 3
    $\begingroup$ I'm not seeing the downside of "live in the room and eat the infinitely large pizza until you die of old age" :P $\endgroup$ – Ben Millwood Sep 25 '17 at 12:46
  • 1
    $\begingroup$ Your comment about thinking that some solutions posted are better than originally intended, @Taylor Brandstetter, frees you up to post your solution separately if you'd like. It would certainly get an easy vote from me, especially for shedding light on what motivated this surprisingly interesting puzzle. You could start by posting your solution (discreetly spoilered like any other solution) and later revise/extend it into a making-of/wrap-up post that outright tells how you thought of this. $\endgroup$ – humn Sep 26 '17 at 3:33
  • 1
    $\begingroup$ Logic twist: Is the Warden expecting a slice, too? $\endgroup$ – NinjaDuckie Sep 28 '17 at 11:59
  • 1
    $\begingroup$ Some great answers here - has one of them risen above the others in your mind enough to consider it a best answer? If so, please don't forget to reward the effort that went into these answers by $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio Oct 2 '17 at 4:18
9
$\begingroup$

Continuation 2 has been added, with seemingly ideal results.

Ben Aveling’s solution. inspired three new solutions (“Continuations”) to this surprisingly playful puzzle that is interestingly reminiscent of Benford’s and Zipf’s laws. $\require{begingroup} \begingroup \def\safeMathJax{\text{\endgroup error}} \def \p {{\kern 1mu p}} \def \r {{\large r}} \def \x {{x \kern1mu}} \def \P {{ \kern1mu p \kern2mu}} \def \s{{ \large s}} \def \= {~ = ~} \def \* {\kern2mu \cdot \kern1mu} $

Beginning with an untouched pizza, I will...

...make a cut from anywhere on the edge of the pizza to the center.

With that taken care of, more than one way to continue have come to mind.


Continuation 1 — Based on error correction, simplified to introduce analysis.

Now to write a note to my fellow pizza partier/prisoners.

Dear fellow pizza partier/prisoner,
You are invited to...

1. Find the largest slice. If you see only one cut in the pizza, consider the whole thing to be the largest slice.
2. Measure that slice’s angle in degrees and call it $A \LARGE\raise-.3ex\strut$.
3. Cut an angle of  $\dfrac {\raise-2mu 1} { \frac{2}{A} + \frac{{\large\ln}\,2}{720} \, }$   degrees into the slice.

  4. By the way,        $ \small \dfrac{\raise-2mu{\ln2}}{720} \approx \, 0.0009627044174443684853... $

With love, fellow pizza partier/prisoner.

If my fellow pizza partier/prisoners make sense of that, this is how the first nine cuts should go.

                  |                                                                       |
 After my cut     |                             360.0°                                    |
                  |                                                                       |
 After prisoner 2 |             153.4°            |             206.6°                    |
                  |                               |                                       |
 After prisoner 3 |                               |      94.0°    |     112.6°            |
                  |                               |               |                       |
 After prisoner 4 |      71.4°    |      82.0°    |               |                       |
                  |               |               |               |                       |
 After prisoner 5 |               |               |               | 53.4° |      59.2°    |
                  |               |               |               |       |               |
 After prisoner 6 |               |               | 44.9° | 49.0° |       |               |
                  |               |               |       |       |       |               |
 After prisoner 7 |               | 39.4° | 42.5° |       |       |       |               |
                  |               |       |       |       |       |       |               |
 After prisoner 8 | 34.5° | 36.9° |       |       |       |       |       |               |
                  |       |       |       |       |       |       |       |               |
 After prisoner 9 | 34.5° | 36.9° | 39.4° | 42.5° | 44.9° | 49.0° | 53.4° | 28.8° | 30.4° |
        .         |       |       |       |       |       |       |       |       |       |
        .         |       .       .       .       .       .       .       .       .       |
        .         |       .       .       .       .       .       .       .       .       |


Now for some analysis while waiting for pizza, or execution. Begin with an ideal sequence of cuts where slices are re-cut in the same order as they were produced. The sequence above begins ideally but hasn’t been examined thoroughly for monotonicity.

     .---.
    :     :.------.
   360°  360°      :                     SLICE SIZES AS A LEAPFROGGING SEQUENCE
    |     |      .-'-.
    |     |     :     :
    |     |     :.----:-------.                  Each prisoner  p  finds  p-1
    |     |    207°   :      .-'-.               slices and divides the slice
    |     |     |     :     :     :              of size  s_p  into slices of
    |     |     |     :.----:-----:-------.       size  s_(2p-1)  and  s_2p .
    |     |     |    153°   :     :        :
    |     |     |     |     :.----:--------:----------.
    |     |     |     |    113°   :        :           :
    |     |     |     |     |     :.-------:-----------:-----------.
    |     |     |     |     |     94°      :           :            :
    |     |     |     |     |     |      .-'-.         :            :
    |     |     |     |     |     |     :     :      .-'-.          :
    |     |     |     |     |     |    82°    :     :     :         :
    |     |     |     |     |     |     |    71°    :     :       .-'-.
    |     |     |     |     |     |     |     |    59°   53°     :     :
    |     |     |     |     |     |     |     |     |     |     49°   45°   .   .  .
    |     |     |     |     |     |     |     |     |     |      |     |
    |     |     |     |     |     |     |     |     |     |      |     |
                      |                 |     |
   s_1   s_2   s_3   s_4   s_5   s_6   s_7   s_8   s_9   s_10   s_11  s_12   .   .  .

                      |                 |     |

                     s_p     =     s_(2p-1) + s_2p

For aesthetics as much as fairness, the sequence of slice sizes (angles), $\s_p \kern2mu$, would ideally form a smooth curve. For convenience, how about a slice-size function, $\s(\p)$, that approximates $\s_p$ and satisfies $\s(\p) \approx \s(2\P{-}1) + \s(2\p) \,$?   As such, prisoner $p$ arrives around time = $p$ and divides a slice of size $\s(\p)$ into two slices intended to be re-cut by prisoners $2\P{-}1$ and $2\p$ around time = $2\p$.

$$ \s_p= \s(\p) = \dfrac {\large\tfrac{360}{\ln2}} {\, \P-\tfrac12 ~} $$ That’s just $\dfrac{\raise-2mu 1}{\, \raise4mu p \,}$, scaled and shifted so that all current slices add up to a full 360° of pizza. $$ \sum_{\P+1}^{2\p} \s_i ~\approx \int_{\P+\frac12}^{2\p+\frac12} \!\! \s(x)dx ~\approx~ 360^\circ $$

If at any stage the largest slice’s angle to be divided, $A$, happens to be larger or smaller than ideal, it may be treated as merely being out of place in the sequence. Thus every slice’s ideal position, $x$, is deduced such that $\s(x)=A$, before dividing $A$ into slices with angles $\s(2x)$ and $A{-}\s(2x)$.

\begin{array}{rrl}{} & A \kern-1em{} & \= \, \s(x) \,{} \= \dfrac{\large\tfrac{360}{\ln2}} {\, x-\tfrac12 ~}{} \\[1ex]{} \Longrightarrow & x \kern-1em{} & \= {\large\tfrac{360}{A \ln2}} + \tfrac12{} \\[2ex]{} \Longrightarrow & \s(2x) \kern-1em{} & \= \dfrac {\large\tfrac{360}{\ln2}} {\, 2x-\tfrac12 ~}{} \= \dfrac {\large\tfrac{360}{\ln2}} {\,{} {\large\tfrac{720}{A \ln2}} + \tfrac12 ~}{} \= \dfrac {1} {\, {\large\tfrac{2}{A}}{} + {\large\tfrac{\ln2}{720}} ~}{} \end{array}

That last calculation is what was recommended in the note to other prisoners.

This approach was designed to be relatively simple to calculate. It is also meant to be good at correcting mistakes in earlier slices, which will be tested in the section for Continuation 3.



Continuation 2 — Each cut is based on the number of slices.

Steps 2 through 4 of Continuation 2’s note to fellow pizza partier/prisoners are:

2. Count the number of slices so far and call that number $n \raise-2ex\strut$.
3. Cut the largest slice into two pieces whose angles have a ratio of  $\ln(2n{+}1)-\ln 2n ~$ to  $\ln(2n{+}2)-\ln(2n{+}1)$.

  4. You can do it, pizza pal, just remember that  $ \ln x \= \x{-}1 - \frac{(\x{-}1)^2}2 + \frac{(\x{-}1)^3}3 - \cdots $

And here is how the first nine cuts would go this time.

                  |                                                                       |
 After my cut     |                                     360.0°                            |
                  |                                                                       |
 After prisoner 2 |                     210.6°            |             149.4°            |
                  |                                       |                               |
 After prisoner 3 |             115.9°    |      94.7°    |                               |
                  |                       |               |                               |
 After prisoner 4 |                       |               |      80.1°    |      69.4°    |
                  |                       |               |               |               |
 After prisoner 5 |      61.2°    | 54.7° |               |               |               |
                  |               |       |               |               |               |
 After prisoner 6 |               |       | 49.5° | 45.2° |               |               |
                  |               |       |       |       |               |               |
 After prisoner 7 |               |       |       |       | 41.6° | 38.5° |               |
                  |               |       |       |       |       |       |               |
 After prisoner 8 |               |       |       |       |       |       | 35.8° | 33.°5 |
                  |               |       |       |       |       |       |       |       |
 After prisoner 9 | 31.5° | 29.7° | 54.7° | 49.5° | 45.2° | 41.6° | 38.5° | 35.8° | 33.5° |
        .         |       |       |       |       |       |       |       |       |       |
        .         |       .       .       .       .       .       .       .       .       |
        .         |       .       .       .       .       .       .       .       .       |

This comes from how Ben Aveling figured out a way to obtain a very fair result by basing each cut solely on the number of slices cut so far. Extending the terms used here, Ben Aveling’s solution is...

$$ \r_p \= \frac{\s_{2\P-1}}{\s_{2\p}} \= \frac{n+1}{n} $$

...prisoner $p$ divides slice $\s_p$ into slices $\s_{2\P-1}$ and $\s_{2\p}$ to have a size ratio, $\r_p$, based on the number of slices so far, $n$. Incidentally, $n = \P{-}1$.   A plot of  $\log\sum\kern-1mu\textsf{error}\kern1mu^2$ shows how much smoother this is than Continuation 1 or straightforward halving of the largest slice.   Each $\sum\kern-1mu\textsf{error}\kern1mu^2$ reflects the unfairness when there are $n$ slices and each of those slices has an $\textsf{error}$ that equals the difference between its size and the $n$ slices’ average size.

This plot also shows how fluctuations repeat at intervals that keep doubling.   The fluctuations also reveal that different approaches take turns being better than the others.   Along comes Continuation 2, a tweak on Ben Aveling’s approach, to produce a fluctuation-free(!) error graph.

And along comes Continuation 2’s derivation of $\r_p$.   The fluctuations in the first plot make clear how any cut’s inaccuracy is echoed among an infinite cascade of future cuts, which is part of the fun challenge in this puzzle. Writing out the consequences of $\s_3$ and $\s_4$ is enough to establish a general formula for $\s_p$ and hence for an ideally smooth $\r_p$.

\begin{array}{rl}{} \s_3 \kern-1em{} & \= \s_5 + \s_6{} \= (\s_9 + \s_{10}) + (\s_{11} + \s_{12}){} \\[-1ex]{} & \= \s_{17}+\s_{18} + \s_{19}+\s_{20} + \s_{21}+\s_{22} + \s_{23}+\s_{24}{} \= \cdots{} \= {\displaystyle \lim_{i\to\infty} \int_{\large 2\*2^i{+}1}^{\large 3\*2^i} \!\! \s(x)dx}{} \\[1ex]{} & \= \frac{360}{\ln2} (\ln3-\ln2){} \\[4ex]{} \s_4 \kern-1em{} & \= \s_7 + \s_8{} \= (\s_{13}+\s_{14}) + (\s_{15}+\s_{16}){} \\[-1ex]{} & \= \s_{25}+\s_{26} + \s_{27}+\s_{28} + \s_{29}+\s_{30} + \s_{31}+\s_{32}{} \= \cdots{} \= {\displaystyle \lim_{i\to\infty} \int_{\large 3\*2^i{+}1}^{\large 4\*2^i} \!\! \s(x)dx}{} \\[1ex]{} & \= \frac{360}{\ln2} (\ln4-\ln3){} \\[5ex]{} \s_p \kern-1em{} & \= \frac{360}{\ln2} \big( \ln p - \ln(\P-1) \, \big){} \end{array}
$ \begin{array}{rrl}{} \Longrightarrow & \r_p \kern-1em{} & \= \dfrac {\s_{2\P-1}} {\s_{2\p}}{} \= \dfrac {\ln(2\P{-}1)-\ln(2\P{-}2)} {\ln2\p-\ln(2\P{-}1)}{} \\[2ex]{} & & \= \dfrac {\ln(2n{+}1)-\ln 2n} {\ln (2n{+}2)-\ln(2n{+}1)}{} \end{array} $


Continuation 3 — More accurate version of error-correcting Continuation 1.

Being refined.

$\endgroup$

$\endgroup$
  • $\begingroup$ Are you sure you mean 120 and 240? $\endgroup$ – paparazzo Sep 23 '17 at 14:35
  • $\begingroup$ I believe that as N increases there are relatively more cases where the pure halving has lower variance than the initial two-thirds and one-thirds split. (yes I prefer Ben's too it has lower variance even more often). $\endgroup$ – Jonathan Allan Sep 23 '17 at 15:09
  • $\begingroup$ This is actually effectively the same as your first answer. You'll end up with cycles between every slice being the same size, and there being a 50/50 split of pieces with a 2:1 size ratio. Which means if you have bad luck that's what the prisoner count produces, you'll be executed. You want to guarantee your success, without relying on luck. $\endgroup$ – Taylor Brandstetter Sep 24 '17 at 4:09
  • $\begingroup$ No problem, @Taylor Brandstetter, I'm not stuck on this approach and am writing up a revision that produces a very smooth result and involves $\large\frac{720}{\ln2}$. The 2:1 ratio of largest to smallest slices probably cannot be worked around, with any system, but I agree that the present solution here is clunky. $\endgroup$ – humn Sep 24 '17 at 4:18
  • 1
    $\begingroup$ @humn Oh, a twist I never considered; what if the pizza size distribution was made to match an average human weight distribution, so each person can find a size they're happy with, "to each according to his need"? See, this is where constraining the problem more would have helped (but also possibly made things less interesting). $\endgroup$ – Taylor Brandstetter Sep 26 '17 at 8:39
6
$\begingroup$

Same start as @humn, but a variation

Objective:

Maximise 'fairness'

Defined as

Minimise 'unfairness'

Therefore,

Make one cut, into the centre
Write the following note.

Dear fellow pizza partier/prisoner,
You are invited to...
1. Count the number of slices - call that N.
2. Find the largest slice. (If you see only one cut in the pizza, consider the whole thing to be the largest slice.)
2. Divide that slice into two smaller pieces, in the following ratio:
The larger of the two resultant pieces should be (N+1)/(2*N+1) of the original piece
The smaller of the two resultant pieces should be N/(2*N+1) of the original piece

With love, fellow pizza partier/prisoner.

After every cut:

The largest slice is no more than twice converges to twice the size of the smallest slice, with all other slices somewhere in between.

Also works if:

You are the 2nd prisoner, and the first prisoner has made a cut but left the note blank.

Note:

I originally tried cutting each piece into 2/3 and 1/3. It was better than 1/2 + 1/2, but not as good as the above.
After 10 cuts:
Dividing into 1/2, 1/2: <0.083 0.083 0.083 0.083 0.083 0.083 0.167
Dividing into 2/3, 1/3: 0.049 0.049 0.065 0.099 0.099 0.132 0.148
Dividing into N/(2*N+1), (N+1)/(2*N+1): 0.068 0.070 0.075 0.079 0.083 0.088 0.095 0.101 0.103 0.119 0.121

$\endgroup$
  • $\begingroup$ Certainly better than always halving the (a) largest slice considering we want to minimise expected variance for any large N (halving will have lower variance for N close to powers of 2, but more often than not this method will have lower variance). Is it the best though? $\endgroup$ – Jonathan Allan Sep 23 '17 at 14:54
  • $\begingroup$ You can just the the largest in half and have the same spread $\endgroup$ – paparazzo Sep 23 '17 at 14:57
  • $\begingroup$ @Paparazzi you are mistaken, maybe try both methods and inspect the variance of slice sizes over varying population sizes. $\endgroup$ – Jonathan Allan Sep 23 '17 at 15:13
  • $\begingroup$ Don't want to argue. Just a comment. $\endgroup$ – paparazzo Sep 23 '17 at 15:15
  • 1
    $\begingroup$ The largest/smallest ratio actually goes above 2 after 10 prisoners, and converges to it, since as N gets large, "N/(2N+1)" approaches 1/2. $\endgroup$ – Taylor Brandstetter Sep 24 '17 at 5:15
4
$\begingroup$

We've already advanced way beyond this, but the answer I had in mind originally:

First of all, you want the golden ratio (Φ). You calculate as many Fibonacci numbers as you can using your head, and the backside of the piece of paper once it starts becoming too much to remember. Then you divide the successive numbers (smallest by largest), subtract it from 1, multiply by 360 degrees, and write down the result ($107.507764$...) at the top of the other side. Or maybe you remember a better method of calculating it; either way, you end up with the angle you want ($\frac{360}{Φ^2}$) with an extremely high degree of precision. Below the number you write these instructions:


DON'T PICK UP THIS PAPER!

Dear fellow prisoner,

The right edge of this paper marks the last position a cut was made. To find which position you should cut at, simply travel the number of degrees at the top of this paper, clockwise around the pizza (which means left, if you follow the crust left from the right edge of this piece of paper). Then make your cut there (if you went the right direction, it shouldn't be on top of another cut), and NOW, you must pick up the paper and move it such that its right edge lines up with your new cut.

This technique will ensure there are always 3 sizes maximum, and that the ratio between them is always the golden ratio. Notice that your new slice will divide the existing slice into the golden ratio; this will keep happening as the process continues clockwise, for however many people we have.

This is much worse than some of the other solutions proposed, but does follow some additional constraints:

- No one is a human calculator, and other prisoners might not even be trusted to calculate things on paper.
- You only have one sheet of paper, so you only have so much space to do calculations.
- Finding the largest pizza slice if there are hundreds of different sizes is too hard/error-prone/time-consuming.

So in retrospect:

If I wanted this to be "the" answer, I should have constrained the problem more. Also, saying "prisoners can measure any angle and cut perfectly straight" implies prisoners have superhuman abilities, which leads you away from thinking of their practical limitations. So I should have designed the story with, say, a robotic cutter that takes an angle to move as input, but fallible humans that must input the number.

So, lesson learned as first-time puzzle author; feel free to rate the puzzle down. But having it open-ended resulted in some quite interesting solutions, and my learning some things, so I consider it a personal victory.

By the way, what inspired this problem:

I was writing software that generated a line chart each time the user performed a measurement, being put on the same graph as all other measurements. I needed the colors to be sufficiently "distinct" so two charts aren't confused. But I didn't want the colors to be re-calculated every time a new measurement is made; that would disrupt the experience. And I didn't know in advance how many measurements they would take.

So instead of angle on a pizza, I did this but for color on a color wheel. This technique has the advantage that it's dirt simple, and doesn't require keeping track of any history. Though it's far from "ideal", in the same way my expected answer is far from the ones other people came up with; depends on what the constraints are. An ideal solution for my problem would actually involve calculating how much charts overlap, since it would be fine to use the same color for charts that aren't even close to touching each other.

$\endgroup$
  • 2
    $\begingroup$ Such an interesting intended solution, and background story, Taylor Brandstetter, you'll have to try harder to convince me that the other solutions are better than this, which doesn't even need the protractor beause you can use the paper to also measure arc length while you're at it. $\endgroup$ – humn Sep 28 '17 at 0:44
  • $\begingroup$ Notice that all my cut-in-half approaches tend to naturally leave the biggest piece adjacent to the smallest piece, so in practice as long as you can identify one piece as being twice the size of another, you don't need to do any calculation or tricky size identification. $\endgroup$ – Ben Millwood Jan 18 '18 at 14:23
  • $\begingroup$ I think I have an idea for the constraints for your solution to be amazing: When a prisoner enter the room, he can only see the last cut been made through the pizza ! $\endgroup$ – Florian Bourse Jan 18 '18 at 16:47
3
$\begingroup$

I claim the following bound on any optimal solution:

The ratio of sizes between the largest to the smallest slice is "in the limit at least $2$", which is to say that for any $\epsilon > 0$ the ratio must eventually exceed $2 - \epsilon$ (though it need not necessarily ever actually be $2$).

Proof:

Firstly, this is immediate if you ever cut a piece that isn't one of the current largest pieces. Then one of your new pieces must be no larger than half of the piece you cut, and therefore strictly less than half the size of the largest piece. Likewise, each cut you make must create a new piece that is the new (possibly-joint-) smallest (since otherwise the old smallest piece was less than half the size of the old largest).

Now, this means that every piece eventually becomes the biggest piece, and moreover that if any two pieces are ever close together in size, then eventually the biggest and second-biggest pieces will be at least that close together in size.

By the pigeonhole principle and the previous observation, if you have $N$ pieces, the biggest (of size $s$, say) and second-biggest pieces will eventually have size within $O(s/N)$ of each other (this isn't as obvious as it sounds, but if you're careful you can prove it).

Now you need to cut the larger slice: one of the pieces you cut out of it will be size at most $s/2$, and thus the ratio to the new largest (previously second-largest) slice cannot be more than $O(1/N)$ less than $2$. But $N$ can be as large as you like, so this ratio will eventually get arbitrarily close to $2$.

This bound is attained by:

The "naive" solution of just always cutting the biggest piece in half. You find yourself with at most two different slice sizes, "large" and "small", and at each stage you cut one large in half to make two small.

but more interestingly also by:

Initially cut the pizza into two pieces, in area ratio $1:\sqrt 2$, and from then on always cut the largest piece in half. You will find yourself with up to three sizes of piece at any given time, say "small", "medium" and "large", in size ratios $1 : \sqrt 2 : 2$, and at each step you cut a large piece into two small pieces, until you run out of large pieces, at which point you relabel all the medium pieces as large and all the small pieces as medium and continue.

and by this point you can see these are just $k = 1$ and $k = 2$ of a family of solutions parametrised by $k$:

in which you have $k + 1$ "size buckets", in ratios increasing by $2^{1/k}$, and you always cut the largest piece in half to move it from the largest bucket to the smallest bucket. I believe without having proven it that over time the number of pieces in each bucket will roughly scale the same way as the sizes, but in the opposite direction: $2^{1/k}$ times as many pieces for each "smaller" size (obviously the actual ratios are, well, rational, but my guess is they'll converge to this no matter where they start from).

If we believe (I'm not sure) that larger $k$ are better, this hints at:

a strategy that doesn't cut pieces perfectly in half, with the aim of essentially increasing $k$ over time,

but I haven't done any more in-depth analysis as to what might lead someone to prefer some of these solutions over others (and I haven't ruled out the possibility that you might prefer a completely different solution attaining the bound, or even a solution that doesn't attain the bound, but is better in some other way).

$\endgroup$
3
$\begingroup$

We're told that we don't know how smart the other prisoners are, and no calculator is provided on the equipment list, so any solution involving mathematical equations that the least smart prisoner will not be able to do in their head will be doomed to failure...

However clever the procedure is, it must be able to be followed by the least smart prisoner without use of a calculator, so calculation of logs, exponentials, etc. cannot be required of the subsequent prisoners.

We're also told that no prisoner can interact with the pizza in any way other than making a cut. Performing measurements on the pizza using the digital protractor (and especially if the prisoner needs to find the largest amongst many similarly-sized pieces) would seem an awful lot of interaction...

After reading the instructions, each prisoner should be able to identify at first glance where to make the cut in order to avoid any appearance of prohibited "interaction" with it. Measurement of the single piece that is to be cut is assumed to be allowed (if not, the position can be calculated relative to a fixed reference).

First prisoner ("you") is assumed to be a mathematical genius or someone who has smuggled a calculator into the prison or prepared notes in advance, etc.

First we choose (or create) a non-moveable reference mark and describe how other prisoners would be able to locate the "12 o'clock" position on the pizza. This must be able to be precisely determined (to at least 1/N of the circumference of the pizza). Our cut is made at "12 o'clock".

If the warden won't allow a reference mark, it will instead be necessary to count the number of cuts, and the relevant paragraphs redrafted to mention this.

We then leave a note on the paper as follows:

Dear fellow prisoners,

We don't know how many of us there are, so must ensure that the pieces are always as equal as possible, especially when lots of us have made a cut.

Imagine the pizza is a clock face - I have made the first cut at the "12 o'clock" position. If you're the second prisoner, please make your cut just after the "7 o'clock" position, at precisely 210.8831175 degrees.

After that we will have a number of rounds, each taking twice as long as the previous round, and each dividing each slice of pizza into two smaller parts of pizza. After many rounds it will be close to dividing in half, but please pay attention to the exact ratio to make sure the system works correctly if another round is required.

Start by facing the pizza from the 12 o'clock position. This can be identified by [description of how to identify it]. From this viewpoint, the "1 o'clock" position will be to your left and the "11 o'clock" position to your right.

Check if the piece just past 12 o'clock (to your left as you look at it) is larger than the piece just before 12 o'clock. If so, you are the first prisoner of the current round, and must cross off the previous round's ratio, and note the ratio for the current round.

Otherwise, simply note the ratio for the current round. Proceed clockwise around the pizza until you find a piece that is bigger than the previous piece you passed. This is the largest piece of the pizza at present, and the one that you must cut.

Your piece of pizza must be cut in precisely the ratio that you noted down, with the larger piece to your right, and the smaller piece to your left. Take as long as you need to determine the precise answer.

The following are the ratios to use. If there are more than 1024 of us in total, you'll need to extend the table by halving the amount after 0.5000...

Round 1 : 0.585786438 (Prisoner 2 only - this is the "just after 7 o'clock" position)

Round 2 : 0.543213617 (Prisoners 3-4)

Round 3 : 0.521647309 (Prisoners 5-8)

Round 4 : 0.510828731 (Prisoners 9-16)

Round 5 : 0.505415001 (Prisoners 17-32)

Round 6 : 0.50270758 (Prisoners 33-64)

Round 7 : 0.5013538 (Prisoners 65-128)

Round 8 : 0.500676901 (Prisoners 129-256)

Round 9 : 0.500338451 (Prisoners 257-512)

Round 10 : 0.500169225 (Prisoners 513-1024)

This works because

in the limit, it represents an integral of 2^-n from 0 to 1. Each round "slices" an approximation of that integral into two pieces.
The "7 o'clock" position referred to is the ratio of the integral of 2^-n from 0 to 0.5 to the same integral from 0 to 1.
The other ratios for round k are evaluated by dividing the integral from 0 to 2^-(k+1) by the integral from 0 to 2^-k. By the time there've been 10 rounds, the next ratio can be calculated to the required precision simply by halving the difference from 0.5.
Note that the ratio between every adjacent piece generated on each round will be identical, and each will, on average, be half of the piece that occupied the same position on the previous round.
These ratios can also be used to calculate how close to the limit of 2 the current ratio between smallest and largest piece is. e.g. during round 3, the piece we cut in half would have been 0.543213617 of the total of it and the next piece. The smallest piece we generate is (1-0.521647309) of this. Thus after a round 3 cut (except the final one), the ratio is (1-0.543213617) / (0.543213617*(1-0.521647309)) = 1.7579...
During round 10, the ratio is about 1.99797, which seems so close to 2 that a modified procedure for later rounds might simply say to walk around the pizza until you find the discontinuity in slice size and then cut the larger slice in half, effectively moving the discontinuity by 1 place (or 2 places if you count the smaller pieces!)

$\endgroup$
1
$\begingroup$

I'm not as well familiar with logarithms and stuff as guys above. I am a simple programmer. And my goal was to try to simplify an answer. I also from Ukraine, so writing math stuff in English sometimes is hard for me. But correct me if you will, it's ok.

So, the logical approach is next:

Just to clarify before start. numbers will represent the angle (assuming whole pizza is 360 degrees, and the biggest (MAX) slice have exact amount of calculated degrees.


Each time new prisoner starts, he will need to do some basic calculations. I will show some of the examples later. Assume we have MAX (aka biggest slice. for the first prisoner we take whole pizza). Now find NEXT_MAX with multiplying it by 0.55 (we go with 55 and 45 % dividing. I thought it might be closest number for the person who is not that familiar with all that fancy math, like me). Now each prisoner takes his NEXT_MAX and calculates it as a current MAX (again, there will be some examples below), and so on.


BUT! This will go not so well, and also will be complicated. So we simplify it: by rounding value to the next biggest decimal point (not sure how it should sound in English, I will explain exact representation for this just in few lines). We also do use MAX value using our pool of available slices, finding the biggest one each time prisoner comes.

So here are some example explanations:

we start with 200 and 160, as it is the closest rounded values after multiply by 0.55. How we got this: 360 - roundedToTenth(360*0.55). Next value which we start from will be 200. As it is the next MAX available for us: 200 - roundedToTenth(200*0.55), which lead us to having 110 and 90. Now we see that our next max is 160. Do same calculations, and so on. Each iteration of such calculations you should measure biggest angle, and cut by that measurement.

note:

there's also cool trick, if you follow this logic, you meet similar numbers more and more after dividing values, you'll see in a table later. There's also a trick when we go to 60.

And here I will try to show you calculations for some deeper values (this table should represent our pool of available slices):

            360
        200     160
    110     90      70
60      50      40      30
    30      20      10
    20      10      5
        3       2
            1

after we go to 1, we have 0.55. I am not sure how it will be better to go from here as on. But if we switch to decimal part as of regular number - 50. Then we can continue as we did for 50 (0.5 onto 0.3 and 0.2 and so on), having infinite cycle of few really small slices, but who cares when we have our measurement tool.

  • also, that was kinda cool riddle, I learned some cool stuff from other answers today (laws and stuff), thank you guys!
$\endgroup$
  • $\begingroup$ So as far as I was calculating, this will give us simple (for not such smart prisoners), logical and understandable strategy with slight (5% basically) difference. $\endgroup$ – Cockabondy Sep 25 '17 at 16:35
-2
$\begingroup$

A reach

Cut to the center and instruct everyone to make the same cut. No one gets a slice and all live.

Realistic

Halving the biggest is the optimal algorithm. Don't understand why OP has dismissed it. A protractor can be used to half a distance.

$\endgroup$
  • $\begingroup$ I think you'll find that the Warden will consider that as "one person gets a huge slice, everyone else gets none, most unfair distribution; everyone executed" $\endgroup$ – Jonathan Allan Sep 23 '17 at 15:07
  • $\begingroup$ @JonathanAllan OP has said halving largest is not correct so I see no other option. $\endgroup$ – paparazzo Sep 23 '17 at 15:11
  • 1
    $\begingroup$ @Paparazzi Everyone has to get one slice; this is the level of outside-the-box thinking I promise is not necessary. $\endgroup$ – Taylor Brandstetter Sep 24 '17 at 4:06
  • $\begingroup$ @TaylorBrandstetter I am not buying you can do better than halving. $\endgroup$ – paparazzo Sep 24 '17 at 18:33
  • 1
    $\begingroup$ @BenMillwood "Unfortunately no longer unambiguous" is worthy of a puzzle alone. $\endgroup$ – paparazzo Sep 26 '17 at 2:37
-4
$\begingroup$

Perhaps,

Depending on the precision of the protractor, we can divide the large pizza into 360 × 60 × 60 = 1,296,000 parts or its multiples ( this number is arrived based on degrees, minutes possible in a degree and seconds possible in a minute) and put the same in the page (kind of instructions for the other inmates to follow).

This said,

Write instructions to fellow inmates such that they should cut one piece at a time such that each remaining part can be cut into 359 further smaller equal pieces.

$\endgroup$
  • $\begingroup$ One cut per prisoner $\endgroup$ – Ben Aveling Sep 23 '17 at 9:16
  • $\begingroup$ What if there's two million prisoners? Just because a second is the smallest unit we divide a circle into doesn't mean it can't be further subdivided. $\endgroup$ – Bobson Sep 24 '17 at 11:48

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.