Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-339/1/a/solution
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 339 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Suppose in the capped simplex has a coordinate strictly between zero and one. Since is an integer, it cannot have exactly one such coordinate: the other coordinates would contribute an integer sum. Hence there are distinct with .
Choose and set , where are standard basis vectors. Both perturbed vectors satisfy the coordinate bounds and have the same coordinate sum. They are distinct and , so is not an extreme point.
Conversely, every zero-one vector in this convex polytope is an extreme point. If it were a nontrivial convex combination of two feasible vectors, each coordinate equal to zero would force both corresponding coordinates to be zero, and each coordinate equal to one would force both to be one. Thus the two vectors would equal the original one. The extreme points are therefore exactly the indicators of -element subsets.
New to topics? Read the docs here!