Maths Olympiad Prep

Library / /4 of 7

Combinatorics Difficulty 6.9 National olympiad Prove it Vietnam

In the space, there is a convex polyhedron DD such that for every vertex of DD, there are an even number of edges passing through that vertex. We choose a face FF of DD. Then we assign each edge of DD a positive integer such that for all faces of DD different from FF, the sum of the numbers assigned on the edges of that face is a positive integer divisible by 2024. Prove that the sum of the numbers assigned on the edges of FF is also a positive integer divisible by 2024.

Solution

We have the following two observations.

Lemma 1. The surface of any convex polyhedron DD can be projected to a plane so that the faces of DD are in one-to-one correspondence with the faces of a planar graph GG and edges of the DD are in one-to-one correspondence with the edges of GG.

Proof. First, we choose a sufficiently small sphere HH within this convex polyhedron and project this polyhedron onto the spherical surface. Then choose a point PP on the sphere which is different from the projection images of the vertices of the polyhedron. An inversion in a sphere centered at PP turns the sphere HH into a plane.

Lemma 2. Suppose that all faces of a planar graph are bounded by a cycle of even length then every cycle is of even length.

Proof. Consider the cycle SS of the planar graph GG. Notice that we can subdivide the cycle SS into disjoint cycles S1,S2,,SnS_1, S_2, \dots, S_n, where each cycle SiS_i cannot be divided into smaller cycles. Consider any cycle SiS_i, the region bounded by SiS_i can be partitioned into disjoint union of faces of GG. This implies that each cycle SiS_i has even length since each face of GG has even length. Therefore the cycle SS has even length.

Let GG be the planar graph obtained from the polyhedron DD by using Lemma 1. We denote its dual graph by GG'. The vertices of GG' are the faces of GG, and two vertices are adjacent iff the corresponding two faces have a common edge in GG. This dual graph GG' is also a planar graph. The faces of the planar graph GG' correspond to the vertices of the graph GG. Because every vertex of GG has even degree, every face of GG' is bounded by even cycles. By Lemma 2, GG' has no odd cycles, it is bipartite. Therefore, the vertices of GG' can be colored in red and blue such that no two adjacent vertices have the same color. In other words, the faces of GG can be colored in red and blue such that no two faces which share a common edge are of the same color. Combining this with Lemma 1, we see that the faces of the convex polyhedron DD can be colored in red and blue such that two faces that share an edge have different colors. Without loss of generality, suppose that FF is colored blue.

We denote by SAS_A the sum of the numbers assigned on the edges of the face AA. We have
SF=A is a red faceSAA is a blue face, AFSA. S_F = \sum_{A \text{ is a red face}} S_A - \sum_{A \text{ is a blue face, } A \neq F} S_A.
By the hypothesis, SAS_A is divisible by 2024 for all the faces AFA \neq F. So each term on the right hand side of the above equality is divisible by 2024. We deduce that SFS_F is divisible by 2024.

\boxed{}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.