12
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ A variation, where each of $m$ people are supposed to receive an equal share, but all that is known about $m$ is that it belongs to some given, finite range, has received some attention here and on math.stackexchange and elsewhere. $\endgroup$ Aug 22, 2019 at 0:44
  • 1
    $\begingroup$ If I understand correctly, you are studying the poset of integer partitions of $L$ ordered by refinement, and you're looking for a partition that refines all elements with (at most? exactly?) $m$ parts. You could try computing the minimum number of pieces for all small $L$ and $m$ and seeing if it's in the OEIS. $\endgroup$ Aug 22, 2019 at 3:37
  • 3
    $\begingroup$ For $m=3$, the number of partitions accomplishing this is given by the OEIS sequences A236970 which includes links to the analogous sequences for $m=4,5$. You want the number of parts in the minimal length partition that's count. There's a link to Haskell code that might be helpful. For $m=2$, you found the length of the smallest complete partition A126796 $\endgroup$ Aug 22, 2019 at 19:32
  • $\begingroup$ In a similar manner, something like $(m-1)\lceil (L/(m-1)+1)\rceil$ suffices for any $m$. If $m$ is small, then this may be close to sharp. (For $L=19$ and $m=3$, the algorithm I see produces $1,1,2,2,4,4,5$ which also has $7$ elements... $\endgroup$ Sep 10, 2019 at 12:52
  • 1
    $\begingroup$ It seems a bit similar to the notion of Golomb ruler: en.wikipedia.org/wiki/Golomb_ruler $\endgroup$ Nov 14, 2019 at 8:10

1 Answer 1

4
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Step 3 is completely rewritten, in order to get a sharper estimate. $\endgroup$ Nov 14, 2019 at 21: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.