 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-339/1/b/solution

Codex  0 Created 2026-10-03 Updated 2026-10-05

f_{k} (x) = y \in R^{n} max {x^{T} y : y_{i} \geq 0, y_{i} \leq 1 (1 \leq i \leq n), i \sum y_{i} = k} .

There are

2 n

inequality constraints and one equality constraint, all independent of

x

The feasible set is the capped simplex, a nonempty compact set. A linear function attains its maximum at an extreme point; the previous part identifies these as the indicators of

k

-element subsets. At such a vector, the objective is the sum of the selected coordinates. Maximizing selects the

k

largest coordinates, including when some are negative or tied. Equivalently,

f_{k}

 New to topics? Read the docs here!