Dividing a chocolate bar into any proportions Suppose I have a chocolate bar of integer length $L$, and there are $m\leq L$ people that are going to share it.  We do not know ahead of time how much each person should receive, all we know is that they will receive an integer amount.  Our goal is to chop the bar into the smallest number of pieces possible, such that, no matter what the desired amounts are for each person, there exists a way of assembling the pieces together so that each person receives that amount.
It is easy to verify that if $m=2$, then it is possible to accomplish this with $ \lceil \log_{2}(L+1)\rceil $ pieces.  I also verified computationally, for example, that for $L=19$ and $m=3$, then one possible optimal solution is to divide the bar into the following $7$ pieces: $7,4,3,2,1,1,1$.  Is this a well-known problem?
 A: Thanks to Fedor Petrov for an advice how to simplify the estimates.
We present a simple algorithm which finds an optimal partition, and then find some estimates on the number of parts in it. Call a partition satisfying the requirements $m$-universal.
Step 1. Consider any partition of $L$. For every $k$, denote by $S_k$ the sum of all parts not exceeding $k$. We claim that a partition is $m$-universal if and only if $(*)$ $S_k\geq (m-1)k$ whenever $(m-1)k\leq L$.
The `only if' part is easy: if $m-1$ persons want to get $k$ units each, all of them should get a combination of pieces accounted for $S_k$.
For the `if' part, distribute the pieces to the people, starting from the largest ones. When we want to give to someone a piece of length $k$, the total length of non-distributed pieces is at least $S_{k-1}+k\geq (m-1)(k-1)+k=m(k-1)+1$, so there is a person who needs at least $k$; give them the piece and continue. The claim is proved.
Step 2. Now we present an algorithm which finds one of optimal $m$-universal partitions.
Define the sequence $a_1,a_2,\dots$ inductively as follows. On the $i$th step, when $a_1,\dots,a_i$ are already defined, find the minimal $k$ such that $\Sigma_i:=a_1+\dots+a_i<(m-1)k$ and set $a_{i+1}=k$ (thus, in partivular, $a_1=1$). In other words,
$$
  a_{i+1}=\left\lfloor\frac{\Sigma_i}{m-1}\right\rfloor+1.
$$
For any $i$ we have
$$
  (a_i-1)(m-1)\leq \Sigma_{i-1}<\Sigma_i<a_{i+1}(m-1),
$$
whence $a_i\leq a_{i+1}$. So the sequence is non-decreasing.
Now, cut from $L$ the pieces of lengths $a_1,a_2,\dots$ until the remainder does not exceed the next term of the sequence. This way, we obtain a partition $\mathcal P$ into pieces $a_1,\dots,a_{s-1},b$, where $0<b\leq a_s$. We claim that we obtain an optimal $m$-universal partition.
By the definition of $a_i$, the partition $\mathcal P$ satisfies $(*)$ (indeed, if the partition violates $(*)$ for some $k$, why did we set some term of $(a_i)$ to be larger than $k$?). Consider now any $m$-universal partition $\mathcal Q$ into parts $c_1\leq c_2\leq \dots$. We claim that $c_i\leq a_i$ for all $i\leq s-1$; this yields that $c_1+\dots+c_{s-1}<L$, so $\mathcal Q$ contains at least $s$ parts, and hence $\mathcal P$ is optimal.
Indeed, assume that $c_i>a_i$ for some (minimal) $i$. By the definition of $a_i$, we have $a_1+\dots+a_{i-1}<(m-1)a_i$ and hence $c_1+\dots+c_{i-1}<(m-1)a_i$ as well. But then in $\mathcal Q$ we have $S_{a_i}<(m-1)a_i$, so $\mathcal Q$ violates $(*)$.
Thus, our algorithm indeed provides an optimal partition.
Step 3. Notice that $\Sigma_n$ is the largest value of $L$ for which we can survive with $n$ pieces. Recall that $a_n=\lfloor \Sigma_{n-1}/(m-1)\rfloor+1$, so
$$
  \frac {m\Sigma_{n-1}+1}{m-1}\leq \Sigma_n\leq\frac m{m-1}\Sigma_{n-1}+1.
$$
This rewrites as
$$
  \frac m{m-1}(\Sigma_{n-1}+1)\leq \Sigma_n+1
\quad\text{and}\quad
  \Sigma_n+(m-1)\leq \frac m{m-1}\left(\Sigma_{n-1}+(m-1)\right).
$$
Therefore,
$$
 \left(\frac m{m-1}\right)^{n-t}(\Sigma_t+1)-1\leq \Sigma_n
  \leq \left(\frac m{m-1}\right)^{n-t}(\Sigma_t+(m-1))-(m-1).
$$
Now, we may choose an appropriate value of $t$. Setting $t=m$ (where $\Sigma_m=m+1$), we get
$$
  \left(\frac m{m-1}\right)^{n-m}(m+2)-1\leq \Sigma_n\leq
    2m\left(\frac m{m-1}\right)^{n-m}-(m-1).
$$
This, in view of $\Sigma_{s-1}<L\leq \Sigma_s$, yields the estimates
$$
  m+\log_{m/(m-1)}\frac{L+m-1}{2m}\leq s \leq m+1+\log_{m/(m-1)}\frac{L+1}{m+2}
$$
which differ only by $O(m)$ whenever $L\geq m$ (as expected).
Remark 1. One can see from Step 3 that there is another way of constructing an optimal partition. Namely, one may say that the largest block in the partition is $\lceil L/m\rceil$ (it cannot be larger!), set $L'=L-\lceil L/m\rceil$, and apply the procedure to $L'$. An argument similar to the `if' part of Step 1 shows that the obtained partition  is $m$-universal. Using the above inequalities, one can show it is optimal.
This example readily yields $s\leq \log_{m/(m-1)}L+1$.
Remark 2. One may try to improve the bound by a smarter choice of $t$. E.g., with some more effort (estimating the length of the piece containing each of the first $(m-1)^2$ cubes) one can obtain
$$
  \Sigma_{(m-1)\lfloor\ln m\rfloor}\leq (m-1)^2
    \leq \Sigma_{m+m\lceil\ln(m-2)\rceil},
$$
which implies
$$
  \left(\frac m{m-1}\right)^{n-m(2+\ln(m-2))}((m-1)^2+1)-1\leq \Sigma_n\leq
    \left(\frac m{m-1}\right)^{n-(m-1)(\ln m-1)}m(m-1)-(m-1).
$$
This yields more complicated estimates
$$
  \log_{m/(m-1)}\frac{L+(m-1)}{m(m-1)}+(m-1)\ln(m-1)\leq s<\log_{m/(m-1)}\frac{L+1}{m^2-2m+2}+1+m(2+\ln(m-2)),
$$
but the difference is still $O(m)$.
