Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/iii/paper-15/2/i/solution

The uniform cover inequality states that for a positive-volume body and a multiset in which each coordinate occurs exactly times, , where is its coordinate projection and volumes use the corresponding dimensions.
To deduce the box theorem, maximize subject to for every nonempty . This linear program is feasible and bounded above by the full-set constraint. Its dual minimizes over nonnegative weights with . For rational weights, clearing denominators gives an exact uniform cover, so the uniform cover inequality bounds that dual objective below by . The same holds for all feasible weights by density of rational points in the rational constraint polyhedron. Strong duality makes the primal optimum at least , while the full-set constraint makes it at most that value. An optimal solution therefore gives with
The axis-aligned box with these side lengths has the required volume and projection volumes.

New to topics? Read the docs here!