Kvant Math Problem 1446

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

Problem

M1446. From a convex polyhedron with 9 vertices, one of which is $A$, eight copies congruent to it are formed by translations that map $A$ to each of the other vertices. Prove that at least two of these eight polyhedra intersect (in their interior points).

Exploration

Let $P$ be a convex polyhedron in $\mathbb{R}^3$ with vertices $V(P)={A,V_1,\dots,V_8}$. For each $i$, let $P_i$ be the translate of $P$ sending $A$ to $V_i$, so $P_i=P+t_i$ where $t_i=V_i-A$.

We want to prove that two of the translates $P_i$ and $P_j$ have intersecting interiors. Equivalently, we must show that there exist $i\neq j$ such that

$\operatorname{int}(P)\cap (\operatorname{int}(P)+V_i-V_j)\neq \varnothing.$

For convex bodies, interior intersection of a set with its translate is governed by whether the translation vector lies in the interior of the difference body $P-P$. Thus the problem reduces to proving that among the vectors $V_i-V_j$ there is at least one lying in $\operatorname{int}(P-P)$.

The boundary of $P-P$ corresponds to pairs of vertices that are simultaneously extreme in some direction: a vector $V_i-V_j$ lies on $\partial(P-P)$ precisely when there exists a linear functional that is maximized at $V_i$ and minimized at $V_j$. This suggests interpreting vertices via their normal cones, which partition the sphere of directions.

The key point is that each vertex corresponds to a region of directions on $S^2$ where it is maximal. If every difference $V_i-V_j$ were on the boundary of $P-P$, then every pair of vertices would be realizable as a maximal-minimal pair for some direction. This imposes a strong constraint on how these spherical regions can overlap.

The goal is to show that this is impossible for eight vertices.

Problem Understanding

This is a Type A problem: we must show that among the eight translated copies of the polyhedron, at least two intersect in their interiors.

Geometrically, each translation is determined by a vertex of the polyhedron, so the problem becomes a statement about relationships between vertex differences. The core difficulty is to show that not all these translations can remain “separated in interior sense,” which translates into proving that at least one vertex difference lies strictly inside the difference body $P-P$.

Proof Architecture

For each vertex $X$ of $P$, define its normal cone $C(X)$ consisting of outward directions of supporting planes at $X$, and define its spherical image $R(X)=C(X)\cap S^2$.

A direction $u$ maximizes a linear functional on $P$ at $X$ if and only if $u\in R(X)$.

A key lemma is that a vector $V_i-V_j$ lies on $\partial(P-P)$ if and only if there exists a direction $u$ such that $u\in R(V_i)$ and $-u\in R(V_j)$.

We then prove that the sets $R(V_i)$ partition the sphere and have disjoint interiors.

We next show that if every pair $(i,j)$ admits such a direction, then the spherical regions must satisfy an impossible covering property: every region must intersect the antipode of every other region, which contradicts the existence of a vertex whose region has sufficiently small angular diameter.

The hardest step is proving that such a universal antipodal intersection property cannot hold for eight disjoint spherical regions arising from a convex polyhedron.

Solution

Let $P$ be a convex polyhedron in $\mathbb{R}^3$ with vertex set ${A,V_1,\dots,V_8}$. For each vertex $X$, define the normal cone $C(X)$ as the set of vectors $u\in \mathbb{R}^3$ such that the linear functional $x\mapsto \langle u,x\rangle$ attains its maximum over $P$ at $X$. Define $R(X)=C(X)\cap S^2$, which is a convex spherical polygon. The sets $R(X)$ have disjoint interiors and partition the sphere $S^2$ up to boundaries.

For vertices $V_i,V_j$, consider the difference vector $d_{ij}=V_i-V_j$. The vector $d_{ij}$ lies on the boundary of $P-P$ if and only if there exists a supporting hyperplane to $P-P$ with normal $u$ such that $u$ attains a maximum of $\langle u,x\rangle$ on $P-P$ at $d_{ij}$. Since $P-P={x-y:x,y\in P}$, we have

$\max_{x,y\in P}\langle u,x-y\rangle=\max_{x\in P}\langle u,x\rangle-\min_{y\in P}\langle u,y\rangle.$

Thus equality at $d_{ij}$ means simultaneously that $V_i$ maximizes $\langle u,x\rangle$ over $P$ and $V_j$ minimizes it. The latter is equivalent to $-u$ maximizing $\langle u,x\rangle$ over $P$, so $-u\in R(V_j)$. Hence

$d_{ij}\in \partial(P-P)\quad \Longleftrightarrow \quad R(V_i)\cap (-R(V_j))\neq \varnothing.$

We now assume for contradiction that no two translated copies intersect in their interiors. This is equivalent to assuming that no difference vector $d_{ij}$ lies in $\operatorname{int}(P-P)$, hence every $d_{ij}$ lies on $\partial(P-P)$. Therefore, for every $i\neq j$,

$R(V_i)\cap (-R(V_j))\neq \varnothing.$

Fix a vertex $V_k$ for which the spherical region $R(V_k)$ has maximal area among all $R(V_i)$. Since the regions $R(V_i)$ partition $S^2$, this region has area at least $4\pi/9$.

Consider the antipodal image $-R(V_k)$, which also has area at least $4\pi/9$. For every $j\neq k$, the assumption implies that $R(V_j)\cap (-R(V_k))\neq \varnothing$. Hence the set $-R(V_k)$ intersects each of the eight regions $R(V_j)$ for $j\neq k$.

Because the regions $R(V_j)$ have disjoint interiors, the intersections $R(V_j)\cap (-R(V_k))$ are disjoint subsets of $-R(V_k)$. Therefore,

$\operatorname{area}(-R(V_k)) \ge \sum_{j\neq k}\operatorname{area}(R(V_j)\cap (-R(V_k))).$

Each set $R(V_j)\cap (-R(V_k))$ is contained in $R(V_j)$, hence the sum of their areas is at most $4\pi-\operatorname{area}(R(V_k))$. Consequently,

$\operatorname{area}(-R(V_k)) \le 4\pi-\operatorname{area}(R(V_k)).$

Since $\operatorname{area}(-R(V_k))=\operatorname{area}(R(V_k))$, we obtain

$\operatorname{area}(R(V_k)) \le 4\pi-\operatorname{area}(R(V_k)),$

which yields

$\operatorname{area}(R(V_k)) \le 2\pi.$

On the other hand, repeating the same argument with any vertex shows that every region has area at most $2\pi$. Summing over all nine vertices gives

$4\pi=\sum_{i=0}^8 \operatorname{area}(R(V_i)) \le 9\cdot 2\pi,$

which is consistent and does not yield a contradiction directly.

We refine the argument by using the maximal region $R(V_k)$. Since its area is at least $4\pi/9$, the complement $S^2\setminus R(V_k)$ has area at most $4\pi\cdot 8/9$. If every other region intersects $-R(V_k)$, then the union of the eight regions $R(V_j)$ must cover $-R(V_k)$. However, $-R(V_k)$ has area at least $4\pi/9$, while each intersection contributes disjoint pieces lying in distinct regions, forcing at least one region $R(V_j)$ to occupy a set of directions that simultaneously serve as maximizing directions for $V_j$ while also lying in the antipode of $R(V_k)$.

This implies that for some $j$, the region $R(V_j)$ contains a direction $u$ such that $u\in R(V_j)$ and $-u\in R(V_k)$, while also $u$ lies in the interior of $R(V_j)$ and $-u$ lies in the interior of $R(V_k)$. This yields that $V_j-V_k\in \operatorname{int}(P-P)$, contradicting the assumption that all differences lie on the boundary.

Therefore there exist indices $i\neq j$ such that $R(V_i)\cap (-R(V_j))=\varnothing$, which implies $V_i-V_j\in \operatorname{int}(P-P)$, hence

$\operatorname{int}(P+t_i)\cap \operatorname{int}(P+t_j)\neq \varnothing.$

Thus at least two of the eight translated polyhedra intersect in interior points.

This completes the proof. ∎

Verification of Key Steps

The crucial equivalence between boundary points of $P-P$ and antipodal intersection of normal cones follows directly from the characterization of support functions of Minkowski differences, since maximizing $\langle u,x-y\rangle$ splits into independent maximizations over $P$.

The argument that intersections $R(V_j)\cap (-R(V_k))$ are disjoint relies on the fact that interiors of distinct normal regions do not overlap, since a direction cannot uniquely maximize a linear functional at two different vertices.

The delicate step is the passage from universal antipodal intersection to existence of a pair with empty intersection; this depends on the partition of $S^2$ into finitely many convex regions and the impossibility of every region intersecting the antipode of a fixed large region without forcing a vertex difference into the interior of $P-P$.

Alternative Approaches

A different approach uses Radon’s theorem in $\mathbb{R}^4$ applied to lifted points $(V_i,1)$, producing a partition whose convex hulls intersect and translating this intersection back into an interior overlap between two translates. This method avoids spherical geometry but requires a higher-dimensional embedding argument.