Re-packing of integers into fixed-size bins 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 &gt; 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$?
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}) &lt; \infty\}$. This is a set of $k$-tuples of nonnegative integers, therefore by Dickson's 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.