Optimal strategy for cutting a sausage?

You are a student, assigned to work in the cafeteria today, and it is your duty to divide the available food between all students. The food today is a sausage of 1m length, and you need to cut it into as many pieces as students come for lunch, including yourself.

The problem is, the knife is operated by the rotating door through which the students enter, so every time a student comes in, the knife comes down and you place the cut. There is no way for you to know if more students will come or not, so after each cut, the sausage should be cut into pieces of approximately equal length.

So here the question – is it possible to place the cuts in a manner to ensure the ratio of the largest and the smallest piece is always below 2?

And if so, what is the smallest possible ratio?

Example 1 (unit is cm):

  • 1st cut: 50 : 50 ratio: 1
  • 2nd cut: 50 : 25 : 25 ratio: 2 – bad

Example 2

  • 1st cut: 40 : 60 ratio: 1.5
  • 2nd cut: 40 : 30 : 30 ratio: 1.33
  • 3rd cut: 20 : 20 : 30 : 30 ratio: 1.5
  • 4th cut: 20 : 20 : 30 : 15 : 15 ratio: 2 – bad

Sorry for the awful analogy, I think this is a math problem but I have no real idea how to formulate this in a proper mathematical way.

Answer

TLDR: an=log2(1+1/n) works, and is the only smooth solution.

This problem hints at a deeper mathematical question, as follows. As has been observed by Pongrácz, there is a great deal of possible variation in solutions to this problem. I would like to find a “best” solution, where the sequence of pieces is somehow as evenly distributed as possible, given the constraints.

Let us fix the following strategy: at stage n there are n pieces, of lengths an,,a2n1, ordered in decreasing length. You cut an into two pieces, forming a2n and a2n+1. We have the following constraints:

a1=1an=a2n+a2n+1anan+1an<2a2n1

I would like to find a nice function f(x) that interpolates all these ans (and possibly generalizes the relation an=a2n+a2n+1 as well).

First, it is clear that the only degree of freedom is in the choice of cut, which is to say if we take any sequence bn(1/2,1) then we can define a2n=anbn and a2n+1=an(1bn), and this will completely define the sequence an.

Now we should expect that an is asymptotic to 1/n, since it drops by a factor of 2 every time n doubles. Thus one regularity condition we can impose is that nan converges. If we consider the "baseline solution" where every cut is at 1/2, producing the sequence

1,12,12,14,14,14,14,18,18,18,18,18,18,18,18,
(which is not technically a solution because of the strict inequality, but is on the boundary of solutions), then we see that nan in fact does not tend to a limit - it varies between 1 and 2.

If we average this exponentially, by considering the function g(x)=2xa2x, then we get a function which gets closer and closer to being periodic with period 1. That is, there is a function h(x):[0,1]R such that g(x+n)h(x), and we need this function to be constant if we want g(x) itself to have a limit.

There is a very direct relation between h(x) and the bns. If we increase b1 while leaving everything else the same, then h(x) will be scaled up on [0,log2(3/2)] and scaled down on [log2(3/2),1]. None of the other bi's control this left-right balance - they make h(x) larger in some subregion of one or the other of these intervals only, but preserving log2(3/2)0h(x)dx and 1log2(3/2)h(x)dx.

Thus, to keep these balanced we should let b1=log2(3/2). More generally, each bn controls the balance of h on the intervals [log2(2n),log2(2n+1)] and [log2(2n+1),log2(2n+2)] (reducedmod1), so we must set them to
b_n=\frac{\log_2(2n+1)-\log_2(2n)}{\log_2(2n+2)-\log_2(2n)}=\frac{\log(1+1/2n)}{\log(1+1/n)}.

When we do this, a miracle occurs, and a_n=\log_2(1+1/n) becomes analytically solvable:
\begin{align}
a_1&=\log_2(1+1/1)=1\\
a_{2n}+a_{2n+1}&=\log_2\Big(1+\frac1{2n}\Big)+\log_2\Big(1+\frac1{2n+1}\Big)\\
&=\log_2\left[\Big(1+\frac1{2n}\Big)\Big(1+\frac1{2n+1}\Big)\right]\\
&=\log_2\left[1+\frac{2n+(2n+1)+1}{2n(2n+1)}\right]\\
&=\log_2\left[1+\frac1n\right]=a_n.
\end{align}

As a bonus, we obviously have that the a_n sequence is decreasing, and if m<2n, then
\begin{align}
2a_m&=2\log_2\Big(1+\frac1m\Big)=\log_2\Big(1+\frac1m\Big)^2=\log_2\Big(1+\frac2m+\frac1{m^2}\Big)\\
&\ge\log_2\Big(1+\frac2m\Big)>\log_2\Big(1+\frac2{2n}\Big)=a_n,
\end{align}

so this is indeed a proper solution, and we have also attained our smoothness goal — na_n converges, to \frac 1{\log 2}=\log_2e. It is also worth noting that the difference between the largest and smallest piece has limit exactly 2, which validates Henning Makholm's observation that you can't do better than 2 in the limit.

It looks like this (rounded to the nearest hundred, so the numbers may not add to 100 exactly):

  • 58:42, ratio = 1.41
  • 42:32:26, ratio = 1.58
  • 32:26:22:19, ratio = 1.67
  • 26:22:19:17:15, ratio = 1.73
  • 22:19:17:15:14:13, ratio = 1.77

If you are working with a sequence of points treated\bmod 1, where the intervals between the points are the "sausages", then this sequence of segments is generated by p_n=\log_2(2n+1)\bmod 1. The result is beautifully uniform but with a noticeable sweep edge:

                                  sausages

A more concrete optimality condition that picks this solution uniquely is the following: we require that for any fraction 0\le x\le 1, the sausage at the x position (give or take a sausage) in the list, sorted in decreasing order, should be at most c(x) times smaller than the largest at all times. This solution achieves c(x)=x+1 for all 0\le x\le 1, and no solution can do better than that (in the limit) for any x.

Attribution
Source : Link , Question Author : Stenzel , Answer Author : Mario Carneiro

Leave a Comment