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$
