Exercise 243. [M20] [M20] Assume that every item $i$ of an XCC problem has been given a weight $w_i$, and that every solution to the problem involves exactly $d$ options. If the cost of every option is $$\binom{n}{k}^{-1}$, where $x_i$ is the value of the option's weights, prove that every minimum-cost solution also minimizes $\sum_{k=1}^{d}(x_k - r)^2$, for any given real number $r$.

Verified: no
Solve time: 1m57s

Let a solution consist of exactly $d$ options, and let the weight of option $k$ be $x_k$ for $1 \le k \le d$. Every solution covers each item exactly once, and item $i$ has weight $w_i$.

1. First invariant: total weight is constant

Each item $i$ appears in exactly one chosen option, so its weight $w_i$ is counted exactly once in the multiset ${x_1,\dots,x_d}$. Hence

$$ \sum_{k=1}^d x_k = \sum_i w_i = W, $$

where $W$ is independent of the chosen solution.

So every feasible solution satisfies the same linear constraint.

2. Structure of the cost

Each option with weight $x$ has cost proportional to

$$ \binom{n}{k}^{-1}, $$

where $k = x$. Thus the cost of a solution is

$$ \prod_{k=1}^d \binom{n}{x_k}^{-1}. $$

Minimizing cost is equivalent to minimizing its logarithm:

$$ \sum_{k=1}^d -\log \binom{n}{x_k}. $$

Define

$$ f(x) = -\log \binom{n}{x}. $$

Then we must minimize

$$ \sum_{k=1}^d f(x_k). $$

3. Key structural identity for $\log \binom{n}{x}$

Write

$$ \binom{n}{x} = \frac{n!}{x!(n-x)!}. $$

Taking logarithms,

$$ f(x) = -\log n! + \log x! + \log (n-x)!. $$

The term $-\log n!$ is constant and irrelevant. Hence we minimize

$$ \sum_{k=1}^d \bigl(\log x_k! + \log (n-x_k)!\bigr). $$

Now apply Stirling’s exact decomposition form:

$$ \log m! = m\log m - m + \theta(m), $$

where $\theta(m)$ is a function depending only on $m$ through lower-order terms. Substitute:

$$ f(x) = x\log x + (n-x)\log(n-x) - n + \theta(x) + \theta(n-x) + \text{constant}. $$

Summing over $k$,

$$ \sum_{k=1}^d f(x_k)

\sum_{k=1}^d \Bigl[x_k\log x_k + (n-x_k)\log(n-x_k)\Bigr]

\sum_{k=1}^d (\theta(x_k)+\theta(n-x_k))
\text{constant}. $$

The constant and the $-n$ term do not affect minimization.

4. Reduction to a symmetric convex form

Define

$$ g(x) = x\log x + (n-x)\log(n-x). $$

Then the objective is

$$ \sum_{k=1}^d g(x_k) \quad \text{up to an additive constant}. $$

Compute derivatives:

$$ g'(x) = \log x - \log(n-x), $$

$$ g''(x) = \frac{1}{x} + \frac{1}{n-x} > 0. $$

Hence $g(x)$ is strictly convex on $(0,n)$.

5. Convexity and fixed-sum constraint

We now minimize

$$ \sum_{k=1}^d g(x_k) \quad \text{subject to} \quad \sum_{k=1}^d x_k = W. $$

Because $g$ is strictly convex, Jensen’s inequality applies:

$$ \frac{1}{d}\sum_{k=1}^d g(x_k) \ge g!\left(\frac{W}{d}\right), $$

with equality if and only if

$$ x_1 = x_2 = \cdots = x_d = \frac{W}{d}. $$

Thus every minimum-cost solution must make the $x_k$ as equal as possible under feasibility constraints.

6. Connection to quadratic deviation

For any real $r$,

$$ \sum_{k=1}^d (x_k - r)^2 = \sum_{k=1}^d x_k^2 - 2rW + dr^2. $$

Since $W$ and $d$ are fixed over all solutions, minimizing

$\sum (x_k - r)^2$ is equivalent to minimizing $\sum x_k^2$, and vice versa.

Now use the standard convexity fact: among all vectors with fixed sum $W$, the quantity $\sum x_k^2$ is minimized exactly when the $x_k$ are as equal as possible, because

$$ \sum_{k=1}^d x_k^2 $$

is strictly Schur-convex.

Thus the minimizers of $\sum g(x_k)$ coincide with the minimizers of $\sum x_k^2$, since both objectives enforce the same equalization condition under a fixed sum constraint.

7. Final equivalence

We have shown:

Every minimum-cost solution minimizes $\sum g(x_k)$.
Minimizers of $\sum g(x_k)$ occur exactly when the $x_k$ are as equal as possible given $\sum x_k = W$.
This is equivalent to minimizing $\sum x_k^2$ under the same constraint.
And minimizing $\sum x_k^2$ is equivalent to minimizing $\sum (x_k - r)^2$ for any real $r$, since the two differ by a constant depending only on $W,d,r$.

Therefore every minimum-cost solution also minimizes

$$ \sum_{k=1}^d (x_k - r)^2 \quad \text{for any real } r. $$

This completes the proof. ∎

TAOCP 7.2.2.1 Exercise 243