Problem 1558

To prove that for all integers $n \geq 3$, there exists a face of the polyhedron with a number of sides not divisible by $n$, we will proceed as follows:

1. Assumption and Simplification:
Assume that all faces of the polyhedron are triangular. This assumption simplifies the problem because if we can prove the statement for triangular faces, we can extend the argument to more complex faces by triangulating them.

2. Orientation of Edges:
Consider orienting the edges of the polyhedron such that all triangles, except possibly one, are oriented either clockwise or counterclockwise. This means that for each triangle, we assign a direction to each edge and ensure that the sum of the directions around the triangle is zero. Specifically, if we traverse an edge in the direction of its orientation, we assign it a $+1$, and if we traverse it against its orientation, we assign it a $-1$.

3. Contradiction Argument:
If we can orient all but one triangle, the last triangle must also be oriented because the sum of the cycles of the other triangles is zero. This implies that the last triangle must also have a sum of zero, which is a contradiction if we assume that one triangle cannot be oriented.

4. Deletion of the Common Edge:
Consider the polyhedron obtained by deleting the common edge of the two vertices with an odd number of edges. This results in a polyhedron where all vertices have an even number of edges. Such a polyhedron can be colored in a chessboard style (i.e., two-colorable), where each face can be oriented consistently.

5. Chessboard Coloring and Orientation:
Color the polyhedron in a chessboard style, where each black face is oriented clockwise and each white face is oriented counterclockwise. When we reintroduce the "bad" edge (the edge between the two vertices with an odd number of edges), we can orient it arbitrarily. This results in exactly one triangle not being oriented, which is a contradiction.

6. Triangulation of Faces:
For a convex polygon with $3k$ vertices, it is possible to triangulate it such that each vertex lies on an even number of edges in the triangulation. This ensures that the argument holds for more complex faces by breaking them down into triangles.

By following these steps, we have shown that there must exist a face of the polyhedron with a number of sides not divisible by $n$.

$\blacksquare$