<p>We can show there's an upper bound based only on B.</p>

<p>Fix B, then i and j. Let the tuple <span class="math-container">$(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k}$</span> denote the packing where we have <span class="math-container">$x_{t}$</span> bins of type <span class="math-container">$t$</span>, where the type of a bin is just the numbers that are packed in it. We have the trivial upper bound <span class="math-container">$k \leq 2^{B-1}$</span>.</p>

<p>Let <span class="math-container">$f(x_{1}, \dots, x_{k}) : \mathbb{N}_{\geq 0}^{k} \mapsto \mathbb{N}_{\geq 0} \cup \infty$</span> be a function mapping any packing into the minimum number of bins we have to touch, with <span class="math-container">$f = \infty$</span> if there exists no repacking. Clearly <span class="math-container">$f(y_{1}, \dots, y_{k}) \geq f(x_{1}, \dots, x_{k})$</span> when <span class="math-container">$y_{t} \leq x_{t}$</span> for all <span class="math-container">$t$</span>, since any repacking we can do with <span class="math-container">$Y$</span> we can also do with <span class="math-container">$X$</span>.</p>

<p>Now define <span class="math-container">$S = \{(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k} \mid f(x_{1}, \dots, x_{k}) &lt; \infty\}$</span>. This is a set of <span class="math-container">$k$</span>-tuples of nonnegative integers, therefore by <a href="https://en.wikipedia.org/wiki/Dickson%27s_lemma" rel="noreferrer">Dickson's lemma</a> it has only finitely many minimal elements, where an element <span class="math-container">$X = (x_{1}, \dots, x_{k}) \in S$</span> is minimal if there exists no other element <span class="math-container">$Y = (y_{1}, \dots, y_{k}) \in S$</span> such that <span class="math-container">$y_{t} \leq x_{t}$</span> for all <span class="math-container">$t$</span>. Let <span class="math-container">$H_{i, j}$</span> be the maximum value of <span class="math-container">$f$</span> over the minimal elements. As the maximum of a finite number of finite elements, it is finite.</p>

<p>Now for any <span class="math-container">$X = (x_{1}, \dots, x_{k}) \in S$</span> there exists minimal <span class="math-container">$Y = (y_{1}, \dots, y_{k}) \in S$</span> such that <span class="math-container">$y_{t} \leq x_{t}$</span> for all <span class="math-container">$t$</span>, but then <span class="math-container">$f(x_{1}, \dots, x_{k}) \leq f(y_{1}, \dots, y_{k}) \leq H_{i, j}$</span>. Therefore if <span class="math-container">$f$</span> is finite it is at most <span class="math-container">$H_{i, j}$</span>.</p>

<p>Therefore <span class="math-container">$\max_{i, j} H_{i, j}$</span> is an upper bound on the number of bins we need to touch, and it depends only on <span class="math-container">$B$</span>. As the maximum of a finite number of finite elements, it is finite.</p>

CC BY-SA 4.0
2019-10-11T13:53:35.283Z
Thanks for the interesting argument. It is not convincing though. The objective is to show that $f$ does not grow with $N$ and it depends only on $B$. The weaker version that you considered is also interesting: $f$ is finite when $N \to \infty$. At the beginning you assume $f$ is finite whenever there exists a packing. You conclude, if $f$ is finite then it is a function of $B$. Isn't this conclusion trivial when you already assumed $f$ is finite? We want to show $f$ is always finite even with infinite number of bins.
Parham
CC BY-SA 4.0
2019-10-12T23:04:53.267Z
So the question was not to prove an upper bound based only on B, but to show that the exact worst case amount we have to touch is based only on B? Clearly N has to affect the exact amount, since for $N = B$ we touch one, for $N = 2B$ we might need to touch two. The former was proven here though, if repacking is possible we always need to touch at most $\max_{i, j} H_{i, j}$ bins to do it, which is a finite value depending only on $B$, not on $N$. Furthermore it is an upper bound even if we allow $N = \infty$, just replace $\mathbb{N}_{\geq 0}^{k}$ with $(\mathbb{N}_{\geq 0} \cup \infty)^{k}$.
Antti Röyskö
CC BY-SA 4.0
2019-10-28T22:01:31.280Z
@Antti I don't get the last sentence. In the finite case, we know that if there is a packing, there is also a finite repacking (pack everything out, then back). But for infinitely many bins this might not hold.
domotorp
CC BY-SA 4.0
2019-10-28T22:19:06.350Z
Indeed, suppose that B=3 and our numbers are 1's and 2's, such that in each bin we have a 1 and a 2. If two 1's are merged, then an infinite repacking is needed. Of course, this question is quite unrelated to the original problem.
domotorp
CC BY-SA 4.0
2019-10-29T12:37:46.610Z
@domotorp An infinite repacking is undefined and a repacking is always a finite process. So when we assume infinite number of bins, any worst case repacking is trivially finite. In the case of your example, a repacking simply doesn't exist.
Parham
CC BY-SA 4.0
2019-10-10T22:34:10.077Z
2019-10-10T22:34:10.077Z
Antti Röyskö
<p>We are given a constant <span class="math-container">$B \geq 3$</span>, a set of positive integers <span class="math-container">$I$</span>  s.t. <span class="math-container">$\forall i \in I, i \leq B$</span> and <span class="math-container">$\sum_{i \in I} = N$</span>,
and 2) a packing of these numbers into <span class="math-container">$N/B &gt; 1$</span> bins of size <span class="math-container">$B$</span>.</p>

<p>An adversary replaces two numbers with their addition so that a packing exists. I.e.,
for some <span class="math-container">$i,j \in I, i+j \leq B$</span>, the set
<span class="math-container">$I' = (I \setminus \{i,j\}) \cup \{i+j\}$</span> admits a packing into <span class="math-container">$N/B$</span> bins.</p>

<p>An optimal update minimizes the number of touched bins during the re-packing for <span class="math-container">$I'$</span>.
We are interested in the maximum number of bins  an optimal update would touch.</p>

<p><strong>Questions</strong>:
How many bins (at most) an optimal update has to touch in a worst case?</p>

<p><strike>Does it depend on the number of bins or it is some function of only <span class="math-container">$B$</span>?</strike></p>

<co.combinatorics>
Re-packing of integers into fixed-size bins
Parham
# Re-packing of integers into fixed-size bins

(Asked by: username_0 on 2019-10-10)

We are given a constant $B \geq 3$, a set of positive integers $I$ s.t. $\forall i \in I, i \leq B$ and $\sum\_{i \in I} = N$,
and 2) a packing of these numbers into $N/B > 1$ bins of size $B$.

An adversary replaces two numbers with their addition so that a packing exists. I.e.,
for some $i,j \in I, i+j \leq B$, the set
$I' = (I \setminus \{i,j\}) \cup \{i+j\}$ admits a packing into $N/B$ bins.

An optimal update minimizes the number of touched bins during the re-packing for $I'$.
We are interested in the maximum number of bins an optimal update would touch.

**Questions**:
How many bins (at most) an optimal update has to touch in a worst case?

Does it depend on the number of bins or it is some function of only $B$?

**Tags:** co.combinatorics


---

## 1 answers

### Answer by username_1 on 2019-10-10. Score: 5 | Accepted answer

We can show there's an upper bound based only on B.

Fix B, then i and j. Let the tuple $(x\_{1}, \dots, x\_{k}) \in \mathbb{N}\_{\geq 0}^{k}$ denote the packing where we have $x\_{t}$ bins of type $t$, where the type of a bin is just the numbers that are packed in it. We have the trivial upper bound $k \leq 2^{B-1}$.

Let $f(x\_{1}, \dots, x\_{k}) : \mathbb{N}\_{\geq 0}^{k} \mapsto \mathbb{N}\_{\geq 0} \cup \infty$ be a function mapping any packing into the minimum number of bins we have to touch, with $f = \infty$ if there exists no repacking. Clearly $f(y\_{1}, \dots, y\_{k}) \geq f(x\_{1}, \dots, x\_{k})$ when $y\_{t} \leq x\_{t}$ for all $t$, since any repacking we can do with $Y$ we can also do with $X$.

Now define $S = \{(x\_{1}, \dots, x\_{k}) \in \mathbb{N}\_{\geq 0}^{k} \mid f(x\_{1}, \dots, x\_{k}) < \infty\}$. This is a set of $k$-tuples of nonnegative integers, therefore by [Dickson's lemma](https://en.wikipedia.org/wiki/Dickson%27s_lemma) it has only finitely many minimal elements, where an element $X = (x\_{1}, \dots, x\_{k}) \in S$ is minimal if there exists no other element $Y = (y\_{1}, \dots, y\_{k}) \in S$ such that $y\_{t} \leq x\_{t}$ for all $t$. Let $H\_{i, j}$ be the maximum value of $f$ over the minimal elements. As the maximum of a finite number of finite elements, it is finite.

Now for any $X = (x\_{1}, \dots, x\_{k}) \in S$ there exists minimal $Y = (y\_{1}, \dots, y\_{k}) \in S$ such that $y\_{t} \leq x\_{t}$ for all $t$, but then $f(x\_{1}, \dots, x\_{k}) \leq f(y\_{1}, \dots, y\_{k}) \leq H\_{i, j}$. Therefore if $f$ is finite it is at most $H\_{i, j}$.

Therefore $\max\_{i, j} H\_{i, j}$ is an upper bound on the number of bins we need to touch, and it depends only on $B$. As the maximum of a finite number of finite elements, it is finite.

> **Comments:**
> **username_0**: Thanks for the interesting argument. It is not convincing though. The objective is to show that $f$ does not grow with $N$ and it depends only on $B$. The weaker version that you considered is also interesting: $f$ is finite when $N \to \infty$. At the beginning you assume $f$ is finite whenever there exists a packing. You conclude, if $f$ is finite then it is a function of $B$. Isn't this conclusion trivial when you already assumed $f$ is finite? We want to show $f$ is always finite even with infinite number of bins.  
> **username_1**: So the question was not to prove an upper bound based only on B, but to show that the exact worst case amount we have to touch is based only on B? Clearly N has to affect the exact amount, since for $N = B$ we touch one, for $N = 2B$ we might need to touch two. The former was proven here though, if repacking is possible we always need to touch at most $\max_{i, j} H_{i, j}$ bins to do it, which is a finite value depending only on $B$, not on $N$. Furthermore it is an upper bound even if we allow $N = \infty$, just replace $\mathbb{N}_{\geq 0}^{k}$ with $(\mathbb{N}_{\geq 0} \cup \infty)^{k}$.  
> **username_2**: @Antti I don't get the last sentence. In the finite case, we know that if there is a packing, there is also a finite repacking (pack everything out, then back). But for infinitely many bins this might not hold.  
> **username_2**: Indeed, suppose that B=3 and our numbers are 1's and 2's, such that in each bin we have a 1 and a 2. If two 1's are merged, then an infinite repacking is needed. Of course, this question is quite unrelated to the original problem.  
> **username_0**: @username_2 An infinite repacking is undefined and a repacking is always a finite process. So when we assume infinite number of bins, any worst case repacking is trivially finite. In the case of your example, a repacking simply doesn't exist.  

---

