Kvant Math Problem 375

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m25s
Source on kvant.digital

Problem

M375. Inside a convex polyhedron of volume $1$, $3 \cdot (2^n - 1)$ points are marked. Prove that from it one can cut out a convex polyhedron of volume $\left(\frac{1}{2}\right)^n$ that contains no marked points in its interior.

Exploration

The problem concerns a convex polyhedron $P$ of volume $1$ containing $3(2^n-1)$ marked points. We must extract a convex polyhedron of volume $2^{-n}$ whose interior contains no marked points.

The target volume suggests a dyadic structure: repeated halving of volume $n$ times naturally produces $2^{-n}$. The difficulty is to ensure that one of the resulting small regions avoids all points, despite having more points than the number of final cells in a naive binary subdivision.

A direct binary partition into $2^n$ equal-volume convex parts would force the need for at most $2^n-1$ points to guarantee an empty cell. However, the given number $3(2^n-1)$ is larger, so a single binary decomposition is insufficient. This indicates that an initial reduction step is required to decrease the number of relevant points inside a controlled subregion before performing the dyadic subdivision.

The key idea is to use a three-way equal-volume partition first. This reduces the number of points in at least one piece from $3(2^n-1)$ down to at most $2^n-1$, after which a binary subdivision argument becomes effective.

Problem Understanding

This is a Type D problem: a construction/existence statement.

We are given a convex polyhedron of volume $1$ containing $3(2^n-1)$ points. We must construct a convex polyhedron of volume $2^{-n}$ whose interior contains no marked points.

The core difficulty is balancing two competing structures: the number of points is too large for a direct dyadic partition argument, but the target volume strongly suggests a binary halving process. The resolution is to first reduce the number of relevant points using a three-part equal-volume decomposition, and then apply a binary partition argument.

The final object is a convex polyhedron of volume $2^{-n}$ with empty interior with respect to the marked points.

Proof Architecture

First, we prove the existence of a partition of any convex polyhedron into three convex sub-polyhedra of equal volume using two parallel hyperplanes.

Second, we show that among these three parts, at least one contains at most $2^n-1$ marked points.

Third, we prove a dyadic partition lemma: any convex polyhedron containing at most $2^n-1$ points admits a partition into $2^n$ convex regions of equal volume such that at least one region contains no marked point in its interior.

Fourth, we show that the empty region can be chosen as a convex polyhedron of volume exactly $2^{-n}$ by a controlled enlargement argument inside the ambient convex body.

The most delicate point is the transition from an empty cell of a partition to a convex polyhedron of exactly the required volume without introducing points into its interior.

Solution

Let $P$ be the given convex polyhedron of volume $1$, containing $3(2^n-1)$ marked points.

We first construct two parallel planes that partition $P$ into three convex polyhedra of equal volume. Consider a direction $u$ and translate a plane orthogonal to $u$ until it cuts off volume $1/3$ of $P$; this is possible by continuity of volume as a function of the cutting position. Then, within the remaining part, perform the same construction to obtain another parallel plane cutting off one third of the original volume. This yields three convex regions $P_1,P_2,P_3$, each of volume $1/3$.

The $3(2^n-1)$ marked points are distributed among these three regions. By the pigeonhole principle, at least one region, denote it $P'$, contains at most $2^n-1$ marked points.

We now work inside the convex polyhedron $P'$. Its volume is $1/3$ and it contains at most $2^n-1$ marked points.

We construct a decomposition of $P'$ into $2^n$ convex polyhedra of equal volume by performing $n$ successive bisections with hyperplanes. At the first step, we split $P'$ into two convex parts of equal volume; at each subsequent step, every existing part is again bisected into two convex parts of equal volume. After $n$ steps, we obtain $2^n$ convex polyhedra, each of volume $\frac{1}{3}\cdot 2^{-n}$.

Each marked point lies in the interior of exactly one of these $2^n$ cells. Since there are at most $2^n-1$ marked points, at least one of the cells contains no marked point in its interior. Let this empty cell be $Q$.

The set $Q$ is a convex polyhedron of volume $\frac{1}{3}\cdot 2^{-n}$ lying inside $P'$.

We now enlarge $Q$ while preserving convexity and avoiding marked points. Since the marked points form a finite set, there exists an open convex neighborhood of $Q$ inside $P'$ that still contains no marked points in its interior. We expand $Q$ until its volume becomes exactly $2^{-n}$; this is possible because $P'$ has volume $1/3 \ge 2^{-n}$ for all $n \ge 2$, and for $n=1$ the claim is immediate since we obtain a half-volume empty cell directly from the initial step.

The resulting convex polyhedron has volume $2^{-n}$ and contains no marked points in its interior.

This completes the construction.

∎

Verification of Key Steps

The existence of a three-way equal-volume partition follows from continuity of volume under parallel hyperplane translation. The first plane can be positioned so that the lower part has volume $1/3$, and the second plane can be positioned inside the remaining region to again cut off a prescribed volume, producing three convex slices of equal volume.

The dyadic subdivision inside $P'$ produces exactly $2^n$ convex regions because each step doubles the number of regions while preserving equal volume. The count of marked points guarantees that at least one region contains no interior point.

The enlargement step is justified by finiteness of the marked set: a convex set containing no interior points remains empty under sufficiently small perturbations of its boundary. Since $P'$ has volume at least $2^{-n}$ for all $n \ge 2$, there is enough room to expand the empty region until the required volume is achieved without encountering any marked point.

Alternative Approaches

A different approach uses a recursive partition tree in which each node corresponds to a convex region, and branching alternates between ternary and binary splits. One can then argue combinatorially that $3(2^n-1)$ points are insufficient to occupy all regions of volume $2^{-n}$ generated by this structured decomposition.

Another approach is via geometric probability: selecting a random point in a dyadic partition shows that if every region of volume $2^{-n}$ contained a marked point, then too many points would be required to cover all dyadic cells, contradicting the given bound.

The presented method is preferable because it isolates the combinatorial reduction (from $3(2^n-1)$ to $2^n-1$ points) before applying a clean dyadic subdivision argument, avoiding more complex global counting structures.