David Johnson 1973 maximum sum of subdivisions of 1

Question

On "Johnson, D. S. (1973). Near-optimal bin packing algorithms (Doctoral dissertation, Massachusetts Institute of Technology)", David Johson argues on page 65 that, given positive integers $x_{1},\dots,x_{n}$ where $n\geq3$ , such that $\sum_{i=1}^{n}{1/x_{i}}=1$ (which he calls a "subdivision of 1"), then the maximum value of $\sum_{i=1}^{n}{1/(x_{i}-1)}$ is 17/10.

He shows that this bound is achieved with $n=3$ , $x_1=2,x_2=3,x_3=6$, fair enough. But omits the general proof that no other set of integers can do better, saying only that it is "easily derived". How can we prove this ?

Answer 1

Looking back, I could agree that it is "simple", but it took me some weeks to finally reach this conclusion:

Let us order the sequence of integers so that $x_1\leq x_2\leq \dots \leq x_n$ . Notice that $x_1 > 1$ .

1. If $x_1=2$ , $x_2$ cannot be 2, otherwise $1/x_1+1/x_2=1$ and there could not be other integers $x_3,\dots x_n$ .

1.1) If $x_2=3$ , then $\sum_{i=3}^{n}{1/x_i}=1/6$ , therefore $x_i\geq 6$ for all $i\geq3$ . But notice that $$ \begin{align} \sum_{i=3}^{n}{\frac{1}{(x_i-1)}} & = \sum_{i=3}^{n}{\frac{1}{x_i}} + \sum_{i=3}^{n}{\frac{1}{x_i(x_i-1)}} \\ & = \frac{1}{6} + \sum_{i=3}^{n}{\frac{1}{x_i(x_i-1)}} \\ & \leq \frac{1}{6} + \frac{1}{6}\sum_{i=3}^{n}{\frac{1}{(x_i-1)}} \\ \implies \sum_{i=3}^{n}{\frac{1}{(x_i-1)}} \leq \frac{1}{5} \end{align} $$

So $\sum_{i=1}^{n}{1/(x_i-1)} \leq 1 + 1/2 + 1/5 = 17/10$ .

1.2) If $x_2 \geq 4$ , then $x_i\geq4$ for all $i\geq3$ and, similarly:

$$ \begin{align} \sum_{i=2}^{n}{\frac{1}{(x_i-1)}} & = \sum_{i=2}^{n}{\frac{1}{x_i}} + \sum_{i=2}^{n}{\frac{1}{x_i(x_i-1)}} \\ & = \frac{1}{2} + \sum_{i=2}^{n}{\frac{1}{x_i(x_i-1)}} \\ & \leq \frac{1}{2} + \frac{1}{4}\sum_{i=2}^{n}{\frac{1}{(x_i-1)}} \\ \implies \sum_{i=2}^{n}{\frac{1}{(x_i-1)}} \leq \frac{2}{3} \end{align} $$

So $\sum_{i=1}^{n}{1/(x_i-1)} \leq 1 + 2/3 < 17/10$ .

2. If $x_1\geq3$ , then $x_i\geq3$ for all $i\geq2$ , thus:

$$ \begin{align} \sum_{i=1}^{n}{\frac{1}{(x_i-1)}} & = \sum_{i=1}^{n}{\frac{1}{x_i}} + \sum_{i=1}^{n}{\frac{1}{x_i(x_i-1)}} \\ & = 1 + \sum_{i=1}^{n}{\frac{1}{x_i(x_i-1)}} \\ & \leq 1 + \frac{1}{3}\sum_{i=1}^{n}{\frac{1}{(x_i-1)}} \\ \implies \sum_{i=1}^{n}{\frac{1}{(x_i-1)}} \leq \frac{3}{2} < 17/10 \end{align} $$

Thus the claim is proved.