IMO 2006 Shortlisted Problems

Denote the polyhedron by $\Gamma$; let its vertices, edges and faces be $V_1,V_2,\dots ,V_n$, $E_1,E_2,\dots ,E_m$ and $F_1,F_2,\dots ,F_{\ell }$, respectively. Denote by $Q_i$ the midpoint of edge $E_i$. Let $S$ be the unit sphere, the set of all unit vectors in three-dimensional space. Map the boundary elements of $\Gamma$ to some objects on $S$ as follows. For a face $F_i$, let $S^{+}\left(F_i\right)$ and $S^{-}\left(F_i\right)$ be the unit normal vectors of face $F_i$, pointing outwards from $\Gamma$ and inwards to $\Gamma$, respectively. These points are diametrically opposite. For an edge $E_j$, with neighbouring faces $F_{i_1}$ and $F_{i_2}$, take all support planes of $\Gamma$ (planes which have a common point with $\Gamma$ but do not intersect it) containing edge $E_j$, and let $S^{+}\left(E_j\right)$ be the set of their outward normal vectors. The set $S^{+}\left(E_j\right)$ is an arc of a great circle on $S$. $\mathrm{Arc}{S}^{+}\left(E_j\right)$ is perpendicular to edge $E_j$ and it connects points $S^{+}\left(F_{i_1}\right)$ and $S^{+}\left(F_{i_2}\right)$. Define also the set of inward normal vectors $S^{-}\left(E_i\right)$ which is the reflection of $S^{+}\left(E_i\right)$ across the origin. For a vertex $V_k$, which is the common endpoint of edges $E_{j_1},\dots ,E_{j_h}$ and shared by faces $F_{i_1},\dots ,F_{i_h}$, take all support planes of $\Gamma$ through point $V_k$ and let $S^{+}\left(V_k\right)$ be the set of their outward normal vectors. This is a region on $S$, a spherical polygon with vertices $S^{+}\left(F_{i_1}\right),\dots ,S^{+}\left(F_{i_h}\right)$ bounded by arcs $S^{+}\left(E_{j_1}\right),\dots ,S^{+}\left(E_{j_h}\right)$. Let $S^{-}\left(V_k\right)$ be the reflection of $S^{+}\left(V_k\right)$, the set of inward normal vectors. Note that region $S^{+}\left(V_k\right)$ is convex in the sense that it is the intersection of several half spheres. Now translate the conditions on $\Gamma$ to the language of these objects.

a. Polyhedron $\Gamma$ has no parallel edges - the great circles of $\mathrm{arcs}{S}^{+}\left(E_i\right)$ and $S^{-}\left(E_j\right)$ are different for all $i\ne j$.

b. If an edge $E_i$ does not belong to a face $F_j$ then they are not parallel - the great circle which contains arcs $S^{+}\left(E_i\right)$ and $S^{-}\left(E_i\right)$ does not pass through points $S^{+}\left(F_j\right)$ and $S^{-}\left(F_j\right)$.

c. Polyhedron $\Gamma$ has no parallel faces - points $S^{+}\left(F_i\right)$ and $S^{-}\left(F_j\right)$ are pairwise distinct.

The regions $S^{+}\left(V_k\right)$, arcs $S^{+}\left(E_j\right)$ and points $S^{+}\left(F_i\right)$ provide a decomposition of the surface of the sphere. Regions $S^{-}\left(V_k\right)$, arcs $S^{-}\left(E_j\right)$ and points $S^{-}\left(F_i\right)$ provide the reflection of this decomposition. These decompositions are closely related to the problem.

Lemma 1. For any $1\le i,j\le n$, regions $S^{-}\left(V_i\right)$ and $S^{+}\left(V_j\right)$ overlap if and only if vertices $V_i$ and $V_j$ are antipodal.

Lemma 2. For any $1\le i,j\le m,\mathrm{arcs}{S}^{-}\left(E_i\right)$ and $S^{+}\left(E_j\right)$ intersect if and only if the midpoints $Q_i$ and $Q_j$ of edges $E_i$ and $E_j$ are antipodal.

Proof of lemma 1. First note that by properties (a,b,c) above, the two regions cannot share only a single point or an arc. They are either disjoint or they overlap. Assume that the two regions have a common interior point $u$. Let $P_1$ and $P_2$ be two parallel support planes of $\Gamma$ through points $V_i$ and $V_j$, respectively, with normal vector $u$. By the definition of regions $S^{-}\left(V_i\right)$ and $S^{+}\left(V_j\right),u$ is the inward normal vector of $P_1$ and the outward normal vector of $P_2$. Therefore polyhedron $\Gamma$ lies between the two planes; vertices $V_i$ and $V_j$ are antipodal. To prove the opposite direction, assume that $V_i$ and $V_j$ are antipodal. Then there exist two parallel support planes $P_1$ and $P_2$ through $V_i$ and $V_j$, respectively, such that $\Gamma$ is between them. Let $u$ be the inward normal vector of $P_1$; then $u$ is the outward normal vector of $P_2$, therefore $u\in S^{-}\left(V_i\right)\cap S^{+}\left(V_j\right)$. The two regions have a common point, so they overlap.

Proof of lemma 2. Again, by properties (a, b) above, the endpoints of $\mathrm{arc}{S}^{-}\left(E_i\right)$ cannot belong to $S^{+}\left(E_j\right)$ and vice versa. The two arcs are either disjoint or intersecting. Assume that arcs $S^{-}\left(E_i\right)$ and $S^{+}\left(E_j\right)$ intersect at point $u$. Let $P_1$ and $P_2$ be the two support planes through edges $E_i$ and $E_j$, respectively, with normal vector $u$. By the definition of $\mathrm{arcs}{S}^{-}\left(E_i\right)$ and $S^{+}\left(E_j\right)$, vector $u$ points inwards from $P_1$ and outwards from $P_2$. Therefore $\Gamma$ is between the planes. Since planes $P_1$ and $P_2$ pass through $Q_i$ and $Q_j$, these points are antipodal. For the opposite direction, assume that points $Q_i$ and $Q_j$ are antipodal. Let $P_1$ and $P_2$ be two support planes through these points, respectively. An edge cannot intersect a support plane, therefore $E_i$ and $E_j$ lie in the planes $P_1$ and $P_2$, respectively. Let $u$ be the inward normal vector of $P_1$, which is also the outward normal vector of $P_2$. Then $u\in S^{-}\left(E_i\right)\cap S^{+}\left(E_j\right)$. So the two arcs are not disjoint; they therefore intersect.

Now create a new decomposition of sphere $S$. Draw all $\mathrm{arcs}{S}^{+}\left(E_i\right)$ and $S^{-}\left(E_j\right)$ on sphere $S$ and put a knot at each point where two arcs meet. We have $\ell$ knots at points $S^{+}\left(F_i\right)$ and another $\ell$ knots at points $S^{-}\left(F_i\right)$, corresponding to the faces of $\Gamma$; by property (c) they are different. We also have some pairs $1\le i,j\le m$ where arcs $S^{-}\left(E_i\right)$ and $S^{+}\left(E_j\right)$ intersect. By Lemma 2, each antipodal pair ( $Q_i,Q_j$ ) gives rise to two such intersections; hence, the number of all intersections is $2B$ and we have $2\ell +2B$ knots in all. Each intersection knot splits two arcs, increasing the number of arcs by 2. Since we started with $2m$ arcs, corresponding the edges of $\Gamma$, the number of the resulting curve segments is $2m+4B$. The network of these curve segments divides the sphere into some "new" regions. Each new region is the intersection of some overlapping sets $S^{-}\left(V_i\right)$ and $S^{+}\left(V_j\right)$. Due to the convexity, the intersection of two overlapping regions is convex and thus contiguous. By Lemma 1, each pair of overlapping regions corresponds to an antipodal vertex pair and each antipodal vertex pair gives rise to two different overlaps, which are symmetric with respect to the origin. So the number of new regions is $2A$. The result now follows from Euler's polyhedron theorem. We have $n+\ell =m+2$ and $$(2\ell +2B)+2A=(2m+4B)+2,$$ therefore $$A-B=m-\ell +1=n-1.$$ Therefore $A-B$ is by one less than the number of vertices of $\Gamma$.

---

Alternative solution.

Use the same notations for the polyhedron and its vertices, edges and faces as in Solution 1. We regard points as vectors starting from the origin. Polyhedron $\Gamma$ is regarded as a closed convex set, including its interior. In some cases the edges and faces of $\Gamma$ are also regarded as sets of points. The symbol $\partial$ denotes the boundary of the certain set; e.g. $\partial \Gamma$ is the surface of $\Gamma$. Let $\Delta =\Gamma -\Gamma =\{U-V:U,V\in \Gamma \}$ be the set of vectors between arbitrary points of $\Gamma$. Then $\Delta$, being the sum of two bounded convex sets, is also a bounded convex set and, by construction, it is also centrally symmetric with respect to the origin. We will prove that $\Delta$ is also a polyhedron and express the numbers of its faces, edges and vertices in terms $n,m,\ell ,A$ and $B$.

Lemma 1. For points $U,V\in \Gamma$, point $W=U-V$ is a boundary point of $\Delta$ if and only if $U$ and $V$ are antipodal. Moreover, for each boundary point $W\in \partial \Delta$ there exists exactly one pair of points $U,V\in \Gamma$ such that $W=U-V$.

Proof. Assume first that $U$ and $V$ are antipodal points of $\Gamma$. Let parallel support planes $P_1$ and $P_2$ pass through them such that $\Gamma$ is in between. Consider plane $P=P_1-U=P_2-V$. This plane separates the interiors of $\Gamma -U$ and $\Gamma -V$. After reflecting one of the sets, e.g. $\Gamma -V$, the sets $\Gamma -U$ and $-\Gamma +V$ lie in the same half space bounded by $P$. Then $(\Gamma -U)+(-\Gamma +V)=\Delta -W$ lies in that half space, so $0\in P$ is a boundary point of the set $\Delta -W$. Translating by $W$ we obtain that $W$ is a boundary point of $\Delta$. To prove the opposite direction, let $W=U-V$ be a boundary point of $\Delta$, and let $\Psi =(\Gamma -U)\cap (\Gamma -V)$. We claim that $\Psi =\{0\}$. Clearly $\Psi$ is a bounded convex set and $0\in \Psi$. For any two points $X,Y\in \Psi$, we have $U+X,V+Y\in \Gamma$ and $W+(X-Y)=(U+X)-(V+Y)\in \Delta$. Since $W$ is a boundary point of $\Delta$, the vector $X-Y$ cannot have the same direction as $W$. This implies that the interior of $\Psi$ is empty. Now suppose that $\Psi$ contains a line segment $S$. Then $S+U$ and $S+V$ are subsets of some faces or edges of $\Gamma$ and these faces/edges are parallel to $S$. In all cases, we find two faces, two edges, or a face and an edge which are parallel, contradicting the conditions of the problem. Therefore, $\Psi =\{0\}$ indeed. Since $\Psi =(\Gamma -U)\cap (\Gamma -V)$ consists of a single point, the interiors of bodies $\Gamma -U$ and $\Gamma -V$ are disjoint and there exists a plane $P$ which separates them. Let $u$ be the normal vector of $P$ pointing into that half space bounded by $P$ which contains $\Gamma -U$. Consider the planes $P+U$ and $P+V$; they are support planes of $\Gamma$, passing through $U$ and $V$, respectively. From plane $P+U$, the vector $u$ points into that half space which contains $\Gamma$. From plane $P+V$, vector $u$ points into the opposite half space containing $\Gamma$. Therefore, we found two proper support through points $U$ and $V$ such that $\Gamma$ is in between. For the uniqueness part, assume that there exist points $U_1,V_1\in \Gamma$ such that $U_1-V_1=U-V$. The points $U_1-U$ and $V_1-V$ lie in the sets $\Gamma -U$ and $\Gamma -V$ separated by $P$. Since $U_1-U=V_1-V$, this can happen only if both are in $P$; but the only such point is 0. Therefore, $U_1-V_1=U-V$ implies $U_1=U$ and $V_1=V$. The lemma is complete. $\square$

Lemma 2. Let $U$ and $V$ be two antipodal points and assume that plane $P$, passing through 0, separates the interiors of $\Gamma -U$ and $\Gamma -V$. Let ${\Psi }_1=(\Gamma -U)\cap P$ and ${\Psi }_2=(\Gamma -V)\cap P$. Then $\Delta \cap (P+U-V)={\Psi }_1-{\Psi }_2+U-V$.

Proof. The sets $\Gamma -U$ and $-\Gamma +V$ lie in the same closed half space bounded by $P$. Therefore, for any points $X\in (\Gamma -U)$ and $Y\in (-\Gamma +V)$, we have $X+Y\in P$ if and only if $X,Y\in P$. Then $(\Delta -(U-V))\cap P=((\Gamma -U)+(-\Gamma +V))\cap P=((\Gamma -U)\cap P)+((-\Gamma +V)\cap P)={\Psi }_1-{\Psi }_2$. Now a translation by ( $U-V$ ) completes the lemma. $\square$

Now classify the boundary points $W=U-V$ of $\Delta$, according to the types of points $U$ and $V$. In all cases we choose a plane $P$ through 0 which separates the interiors of $\Gamma -U$ and $\Gamma -V$. We will use the notation ${\Psi }_1=(\Gamma -U)\cap P$ and ${\Psi }_2=(\Gamma -V)\cap P$ as well.

Case 1: Both $U$ and $V$ are vertices of $\Gamma$. Bodies $\Gamma -U$ and $\Gamma -V$ have a common vertex which is 0. Choose plane $P$ in such a way that ${\Psi }_1={\Psi }_2=\{0\}$. Then Lemma 2 yields $\Delta \cap (P+W)=\{W\}$. Therefore $P+W$ is a support plane of $\Delta$ such that they have only one common point so no line segment exists on $\partial \Delta$ which would contain $W$ in its interior. Since this case occurs for antipodal vertex pairs and each pair is counted twice, the number of such boundary points on $\Delta$ is $2A$.

Case 2: Point $U$ is an interior point of an edge $E_i$ and $V$ is a vertex of $\Gamma$. Choose plane $P$ such that ${\Psi }_1=E_i-U$ and ${\Psi }_2=\{0\}$. By Lemma 2, $\Delta \cap (P+W)=E_i-V$. Hence there exists a line segment in $\partial \Delta$ which contains $W$ in its interior, but there is no planar region in $\partial \Delta$ with the same property. We obtain a similar result if $V$ belongs to an edge of $\Gamma$ and $U$ is a vertex.

Case 3: Points $U$ and $V$ are interior points of edges $E_i$ and $E_j$, respectively. Let $P$ be the plane of $E_i-U$ and $E_j-V$. Then ${\Psi }_1=E_i-U,{\Psi }_2=E_j-V$ and $\Delta \cap (P+W)=E_i-E_j$. Therefore point $W$ belongs to a parallelogram face on $\partial \Delta$. The centre of the parallelogram is $Q_i-Q_j$, the vector between the midpoints. Therefore an edge pair ( $E_i,E_j$ ) occurs if and only if $Q_i$ and $Q_j$ are antipodal which happens $2B$ times.

Case 4: Point $U$ lies in the interior of a face $F_i$ and $V$ is a vertex of $\Gamma$. The only choice for $P$ is the plane of $F_i-U$. Then we have ${\Psi }_1=F_i-U,{\Psi }_2=\{0\}$ and $\Delta \cap (P+W)=F_i-V$. This is a planar face of $\partial \Delta$ which is congruent to $F_i$. For each face $F_i$, the only possible vertex $V$ is the farthest one from the plane of $F_i$. If $U$ is a vertex and $V$ belongs to face $F_i$ then we obtain the same way that $W$ belongs to a face $-F_i+U$ which is also congruent to $F_i$. Therefore, each face of $\Gamma$ has two copies on $\partial \Delta$, a translated and a reflected copy.

Case 5: Point $U$ belongs to a face $F_i$ of $\Gamma$ and point $V$ belongs to an edge or a face $G$. In this case objects $F_i$ and $G$ must be parallel which is not allowed. case 1 case 2 case 3 case 4

Now all points in $\partial \Delta$ belong to some planar polygons (cases 3 and 4), finitely many line segments (case 2) and points (case 1). Therefore $\Delta$ is indeed a polyhedron. Now compute the numbers of its vertices, edges and faces. The vertices are obtained in case 1, their number is $2A$. Faces are obtained in cases 3 and 4. Case 3 generates $2B$ parallelogram faces. Case 4 generates $2\ell$ faces. We compute the number of edges of $\Delta$ from the degrees (number of sides) of faces of $\Gamma$. Let $d_i$ be the the degree of face $F_i$. The sum of degrees is twice as much as the number of edges, so $d_1+d_2+\dots +d_l=2m$. The sum of degrees of faces of $\Delta$ is $2B\cdot 4+2\left(d_1+d_2+\cdots +d_l\right)=8B+4m$, so the number of edges on $\Delta$ is $4B+2m$. Applying Euler's polyhedron theorem on $\Gamma$ and $\Delta$, we have $n+\ell =m+2$ and $2A+(2B+2\ell )=(4B+2m)+2$. Then the conclusion follows: $$A-B=m-\ell +1=n-1.$$