> The maximum number of queries required by the protocol is n^n^n^n^n^n
With 2 people taking 1 second per query you end up with 2^2^2^2^2^2 which is 2^(2^65536) seconds.
I guess if not only the cake has decomposed and the people involved have died, but the universe itself has lost all thermodynamic free energy, I guess technically we are in an envy free state.
n^n^n^n^n^n is an upper bound for general n, but the special case of only 2 people can be done with just 1 query.
the algorithm is just to have person A cut into two equal slices and then person B choose their favorite slice. it takes just 1 second, which is quite a speedup over the upper bound...
Couldn't you just
1. Draw an arbitrary line through the cake
2. Set each person's valuation of a point on the line equal to their valuation of the cross section throgh that point
3. Use the algorithm to cut the 1D pseudocake
4. Make the corresponding cross sectional cuts to the real cake
Actually for round cakes you could even make normal (wedge-shaped) pieces by re-parameterizing distance along the line as angle and cross sections as infinitesimal wedges.
Edit: And for the rectangular cake you could slice the cake up along one axis and line those pieces up end-to-end first so that the cross sections would have a reasonable width instead of having slices as wide as the whole cake
Making multiple cuts along a line doesn't seem optimal. Remember that these slices of 3D cake can be of any shape. You can imagine different people liking different fillings or different toppings on the cake.
10 comments
[ 4.7 ms ] story [ 36.6 ms ] threadI'm impressed that rendered correctly, never seen that before. Got a minimal version working:
code: https://pastebin.com/CqCzH8H7
what it looks like: https://imgur.com/a/v2PU1mH
With 2 people taking 1 second per query you end up with 2^2^2^2^2^2 which is 2^(2^65536) seconds.
I guess if not only the cake has decomposed and the people involved have died, but the universe itself has lost all thermodynamic free energy, I guess technically we are in an envy free state.
the algorithm is just to have person A cut into two equal slices and then person B choose their favorite slice. it takes just 1 second, which is quite a speedup over the upper bound...
Actually for round cakes you could even make normal (wedge-shaped) pieces by re-parameterizing distance along the line as angle and cross sections as infinitesimal wedges.
Edit: And for the rectangular cake you could slice the cake up along one axis and line those pieces up end-to-end first so that the cross sections would have a reasonable width instead of having slices as wide as the whole cake
Making multiple cuts along a line doesn't seem optimal. Remember that these slices of 3D cake can be of any shape. You can imagine different people liking different fillings or different toppings on the cake.