Consider a convex polyhedron without parallel edges and without an edge parallel to any face other than the two faces adjacent to it. Call a pair of points of the polyhedron antipodal if there exist two parallel planes passing through these points and such that the polyhedron is contained between these planes. Let $A$ be the number of antipodal pairs of vertices, and let $B$ be the number of antipodal pairs of midpoint edges. Determine the difference $A-B$ in terms of the numbers of vertices, edges, and faces. Proposed by Kei Irei, Japan
Problem
Source: IMO Shortlist 2006, Combinatorics 7
Tags: geometry, 3D geometry, Euler, polyhedron, IMO Shortlist
03.07.2007 11:35
Here is a rather ugly and messy solution based on continuity. The idea is somewhat similar to one of the solutions of IMO 2006/6. We prove that $ A-B=V-1$ by induction on the number of vertices of the polygon $ P$. Firstly we note that slightly moving the vertices of the polyhedron does not change $ A$ and $ B$, so we may move the polyhedron such that no line connecting two vertices is parallel to a face. Pick up a vertex $ V$ of the polyhedron. Let's construct $ P'$ the unique convex polyhedron containing the vertices of the original polyhedron without $ V$. The faces not containing $ V$ of the original polyhedron will still be faces of $ P'$, but a couple of new faces and edges may appear. Now let's move $ V$ continuously inwards until it meets a face of $ P'$. The idea is to prove that $ A-B$ does not change while we move it. Let's analyze how $ A$ changes. Consider a pair of opposite vertices $ X,Y$. Let's seek the planes $ \pi$ such that $ X$ is the highest and $ Y$ is the lowest with respect to $ \pi$. To each plane $ \pi$ not parallel to $ XY$ we may assign the unique ray $ l$ perpendicular to it such that the projection of $ X$ is farther than the projection of $ Y$ on $ l$. Now let's assume that $ l$ is of form $ [OP$ where $ O$ is a fixed point in space and let's find the possible positions of $ P$. We must satisfy the conditions that $ X$ is above all its neighbors and $ Y$ below all its neighbors. Generally if we want to ensure that $ U$ is above $ V$ we must have $ P$ in the above halfplane determined a plane throug $ O$ perpendicular to $ UV$. So we get a set of regions and $ P$ exists if and only if these regions have non-empty intersection. The intersection of these regions always has the property that if a point $ K$ belongs to them then the whole ray $ [OK$ does. Thus they are in correspondence with plane regions: pick up a plane not passing through $ O$ and replace each region by the intersection of this region with it. What plane is taken actually matters, but what we need now is that we can apply Helly's theorem: all the regions intersect if and only if every three of them do. Calla plane $ \pi$ separating for $ S,T$ if all the other points are sandwitched between the planes parallel to $ \pi$ through $ S$ and $ T$. Let's investigate a limit case, i.e when the mobile vertex $ V$ passes through some point $ V_{1}$ and $ A$ changes. It means some pair of opposite points disappears or conversely is created. Say $ S,T$ is modified. It means that if we draw the regions for $ S,T$ as above, for $ V=V_{1}$ some three of them will have a degenerate intersection i.e. a line, and when $ V$ passes through $ V_{1}$, at one side of $ V_{1}$ the intersection will be empty and at other non-empty. As three regions have a common line, it means that three edges through $ S,T$ are coplanar (we mean their directions). Therefore, $ A$ may change only when an edge becomes parallel to a face. Let's turn to analyzing $ B$. The midpoints of edges $ KL$ and $ MN$ are opposite if and only if $ K,L$ and $ M,N$ are opposite with respect to the plane parallel to $ MN$ and $ KL$. If we pass to parallel lines, it means that corresponding ray $ l$ through $ O$ parallel to $ MN$ and $ KL$ is contained in the non-empty intersection of corresponding regions for $ K$ (or $ L$) and $ M$ (or $ N$). The limit case is when $ l$ falls on one of the planes $ \pi$ bounding the region. It means $ KL, MN$ and the edge perpendicular to that plane are coplanar. Say $ KL,KK',MN$ are coplanar. Again $ B$ changes if and only if an edge becomes parallel to a face. So we need to analyse the change in $ A$ and $ B$ when an edge $ ST$ becomes parallel to a face $ F=A_{1}A_{2}\ldots A_{n}$. It follows from the reasonings above that $ A$ and $ B$ change only when the plane parallel to the face $ A_{1}A_{2}\ldots A_{n}$ is separating for $ S$(or $ T$) and $ A_{i}$(at the limit point). By continuity it means that in the neighborhood of the limit point a plane close enogh to $ (A_{1}A_{2}\ldots A_{n})$ sandwiches all points except $ S,T,A_{1}, \ldots A_{n}$ between $ S,T$ and $ A_{i}$. So only the relationship between these points matters. We need to analyse two cases: when $ V$ comes close to the limit point $ V_{1}$ and when it passes through it. Let's analyse each of them. In the first case, assume that $ S$ was below $ T$ (we take distances from points to $ F$). Then it is clear for any $ A_{i}$ we can take a plane separating $ A_{i}$ and $ T$. However there are problems with $ S$. If we project the vector pointing from $ S$ to $ T$ on $ F$ then there exists a plane separating $ A_{i}$ and $ S$ if and only if the vector drawn from $ A_{i}$ does not point inwards the polygon. So if we have $ k$ consecutive points from where the vector points inwards the polygon and $ l$ onsecutive points from where the vector points outwards, then there are exactly $ l$ opposite pairs of form $ S,A_{i}$. Now if we pass to $ B$, we see that the pair $ ST, A_{i}A_{i+1}$ is separating if and only the same vectors points outwards drawn from both $ A_{i},A_{i+1}$. There are exactly $ l-1$ such edges. So the difference between $ A$ and $ B$ is $ n-1+C$ (where $ C$ is the difference between pairs of opposite vertices and edges except the ones counted here, as we know $ C$ is unchanged). It is rather clear by analogy that after passing through the limit point the difference will stiil be $ n-1+C$. (we could still have $ S$ below $ T$ and have exactly the same pairs or have $ T$ below $ S$ and now $ k$ would exchange with $ l$). We have thus established that moving $ V$ does not affect $ A-B$. It thus remains to see what happens when $ V$ gets close enough to a face $ F$. If we take $ U$ the vertex farthest from $ F$, clearly that $ U,V$ will be the only pair of opposite vertices containing $ V$. Now let's remove $ V$. We claim no pair of opposite vertices appears. Indeed let $ IJ$ be a "new" pair. Then there is a plane $ \pi$ such that all other vertices are between $ I$ and $ J$ according to the plane. Then taking $ V$ close enough to the face $ F$ will ensure that $ V$ is also between $ I$ and $ J$ so $ IJ$ is actually an "old" pair, contradiction. Also no pair of opposite vertices except $ UV$ disappears. Indeed if $ I,J$ was an "old" pair then all vertices were sandwiched between $ I,J$ and this condition holds by removing $ F$. Hence $ A$ decreases by $ 1$. We now show that $ B$ remains unchanged. If a pair of opposite edges disappears, it must be a pair $ VI, KL$. But this is impossible as $ V$ tends to a point strictly inside the face $ F$ so $ V$ must be below at least some vertex of the face. If a pair of opposite edges appears, then it must be a pair of form $ MN, KL$. Then all the vertices of the polygon must be between $ MN$ and $ KL$ wrt the plane parallel to $ MN$ and $ KL$, except $ V$. However $ V$ tends to be on the face $ F$, which implies that the plane parallel to $ MN$ and $ KL$ is parallel to the face $ F$. Therefore $ M,N,K,L$ are on the same face $ F$. But this is clearly impossible. So $ A-B$ has decreased by 1 for the new polyhedron $ P'$. If has one vertex less, so applying the induction hypothesis ensures the claim. (Note that for a tetrahedron the condition holds).
02.08.2007 14:47
Denote the number of faces, edges and vertices of our polyhedron $ P$ by $ F,E,V$. For any face $ \Phi_{i}$ ($ i=1,2,\dots,F$) of $ P$ consider the point $ A_{i}$ on a unit sphere such that $ OA_{i}$ is a vector of outer unit normal to the face $ \Phi_{i}$. For any edge $ e$ of $ P$, which is common to faces $ F_{i}$ and $ F_{j}$, draw an arc on a sphere, which joins points $ A_{i}$ and $ A_{j}$. This arc is the set of such points $ X$ on a sphere, that a plane with "outer" normal $ OX$, which passes through the edge $ e$, does not contain inner points of $ F$. We get a graph $ G$ on a sphere, which is dual to the graph of initial polyhedron $ P$. So, $ G$ has $ V$ faces, $ E$ edges and $ F$ vertices. Draw the graph $ -G$ on a sphere, which is symmetric to $ G$ with respect the origin. The union of edges of graphs $ G$ and $ -G$ is some graph on a sphere, we add the points, in which edges of $ G$ and $ -G$ intersect, to the set of vertices of this graph (call it $ G'$). Note that the number of added vertices equals to $ 2B$. The number of edges of $ G'$ equals $ 2E+4B$, the number of vertices equals $ 2F+2B$, the number of faces equals $ 2A$ (any face of $ G'$ is an intersection of faces of $ G$ and $ -G$. It corresponds to an antipodal pair of vertices). So, by Euler formula, $ 2A-2E-4B+2F+2B=2$, $ A-B=1+E-F=V-1$.
24.09.2011 07:09
02.07.2015 05:30
Thinking in 3D was hardest part for me! Rename A,B as X,Y for a vertex V I construct a planar graph where vertices are the vertices of the polygon that form antipodal pair with V and edges V1V2 are such that midpoint of V1V2 and V are antipodal. By continuity of the plane at V, is not hard to see that the faces of this graph are faces of the polyhedron such that their center is antipodal with V (except the exterior face of the graph). By Euler formula we get # vertices - # edges + # faces = 1 where #X refers to the number of elements X that are antipodal with V. Summing over all V, we get 2X - (V,A) + (V,C) = V where (V,A) and (V,C) refers to the number of pairs of vertices and edges, and vertices and faces, respectively, that are antipodal. Now construct such a graph for edges instead of vertices, use Euler's formula in that graph and sum over all edges. we get (V,A) - 2Y + 0 = A where V,A is number of vertices and edges, and 0 is because no face is antipodal to an edge (they are not parallel). Notice also (C,V) = C, number of faces in polyhedron, since for each face there is exactly one vertex antipodal to it. Finally, add the two equations. 2X-2Y+C = A+V, so 2X-2Y=A+V-C Using that V+C-2=A by Euler's formula on the whole graph, we get X-Y=V-1, which is the answer.
12.07.2020 22:57
We claim that the answer is $V-1$. First, choose an arbitrary vertex $v$, and draw a plane, $P$, which coincides with a face touching $v$. Now, there exists a unique vertex $u$ of the polyhedron such that $(u,v)$ form an antipodal pair and the corresponding plane can be parallel to $P$. Call the plane parallel to $P$ passing through $u$ $P'$. Now, consider the smooth transformation by which $P$ goes from its current face to a new one by pivoting along an edge incident to $v$. Then, it switches pivots to the other edge incident to $v$, and it continues moving until $P$ returns to its initial orientation. During this cycle, we adjust $u$ every time $P'$ coincides with an edge. Note that, when this happens, we get an antipodal pair of midpoint edges. In this way, when $P$ traces a cycle, $u$ will form a polygon $f(v)=u_1u_2\ldots u_k$. We call the region bounded by $f(v)$ which does not include $u$ the "domain" of $u$. From construction, the edges incident to $v$ are part of $k$ antipodal pairs of midpoint edges. Note that the domain of $u$ roughly corresponds to the reflection of the angle of space subtended by the faces incident to $v$. This means that, if we repeat this construction over all vertices of the polyhedron, all domains are disjoint (since the angles sweeped by all processes perfectly cover the sphere) and 2 domains share part of their border if and only if the vertices they correspond to have a common edge. Now, $A$ can be computed by $\sum_v V(f(v))$ where $V(f(v))$ counts the number of vertices in a domain, and $B$ is $\sum_v E(f(v))$ where $E(f(v))$ counts the number of edges in the boundary of a domain. To compute $A-B$, consider the graph $G$ formed by edges of the boundaries of domains. Let the set of vertices, faces, and edges of $G$ be $V',F',E'$. Also, for convenience, we will assume pairs in $A,B$ are ordered for now. When computing $A-B$ over vertices in $G$, we contribute $\sum_{f\in F'}V(f)=2|E'|$ to $A$ and $|E'|$ to $B$ for a net total of $|E'|$. However, we neglect to include domains which only have $1$ or $2$ boundary points. Each of these two edge cases contribute a net sum of $1$ to $A-B$, and recall that there are $V$ domains, so there are $V-|F'|$ such edge cases. Hence, $G$ contributes $|E'|+(V-|F'|)=V+|V'|-2$. On the other hand, vertices not part of $G$ contribute nothing to $B$, so they contribute $V-|V'|$ to $A-B$. Adding these two cases and dividing by $2$ because each pair was counted twice, our final answer is $\frac{V+|V'|-2+V-|V'|}{2}=V-1$, as desired.
11.02.2021 22:39
Let $\mathcal{P}$ denote the polyhedron. Let $V,E,F$ denote the number of vertices, edges, faces respectively of the polyhedron $\mathcal{P}$ and note that since it is convex, hence genus $0$, we have $V-E+F = 2$. Label the vertices of the polyhedron $\mathcal{P}$ with $1,2,\cdots, V$ and define a coloring on $\mathcal{S}^2$ as follows: A point $(a,b,c) \in \mathcal{S}^2$, which must satisfy $a^2+b^2+c^2=1$, will be colored with the color $i$ if the function $f(x,y,z) = ax+by+cz$ is maximized at vertex $i$. Note that points can be colored with multiple colors, but the set of such multi-colored points has measure zero on $\mathcal{S}^2$. This coloring defines a simple graph $S$ on $\mathcal{S}^2$ such that the face number $i$ of $S$ corresponds to the $i$-monochromatic domain of $\mathcal{S}^2$ (the set of all points which are colored with $i$), the edges of $S$ correspond to boundaries between monochromatic domains, and the vertices of $S$ correspond to intersections of three or more monochromatic domains. Note that $S$ is isomorphic to the dual graph of the graph of $\mathcal{P}$. Furthermore, the edges of $S$ are segments of great circles. If we let $V',E',F'$ denote the number of vertices, edges, faces respectively of $S$, we have $V' = F$, $E' = E$, and $F' = V$. Take the reflected graph $S'$ on $\mathcal{S}^2$, defined as reflection of $S$ about the origin $(0,0,0)$. Consider the new graph $T$ topologically-induced by $S \sqcup S'$; i.e. $T$ has not only the vertices of $S$ and the vertices of $S'$, but also new vertices formed by intersections of edges from $S$ with edges from $S'$, etc. The problem condition implies that edges from $S$ and edges from $S'$ do not intersect except in their interiors; they do not intersect at their endpoints. (This also implies that no vertex of $S$ coincides with a vertex of $S'$.) Let $k$ denote the number of intersections of an edge from $S$ with an edge from $S'$. Note that antipodal pairs of vertices of $\mathcal{P}$ correspond to antipodal faces of $T$, and antipodal midpoints of edges of $\mathcal{P}$ correspond to antipodal pairs of intersections of edges from $S$ with edges from $S'$. This means that $2B = k$. Furthermore, letting $V'', E'', F''$ denote the number of vertices, edges, and faces respectively of $T$, we see that $2A = F''$. It's time to calculate $V'', E'', F''$ in terms of $V', E', F'$. Note that \[V'' = 2V' + k\]because $T$ contains the vertices of $S$, the vertices of $S'$, and new vertices formed by intersections of edges from $S$ with edges from $S'$. Furthermore, \[E'' = 2(E'+k)\]because each intersection increases $E''$ by 2 (it splits two edges in half). Because $V'' - E'' + F'' = 2$, we calculate \[F'' = 2F' + k - 2.\]Thus \[A - B = \frac{1}{2}(2A-2B) = \frac{1}{2}(F'' - k) = \frac{1}{2}(2F' - 2) = F' - 1 = \boxed{V - 1}.\]$\blacksquare$