In the space, there is a convex polyhedron $D$ such that for every vertex of $D$, there are an even number of edges passing through that vertex. We choose a face $F$ of $D$. Then we assign each edge of $D$ a positive integer such that for all faces of $D$ different from $F$, 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 $F$ is also a positive integer divisible by $2024$.
Problem
Source: 2024 Vietnam National Olympiad - Problem 7
Tags: number theory, combinatorics
Davsch
06.01.2024 21:38
I'm not sure I understood the problem correctly. I am convinced that the claim holds if the polyhedron has "no holes" and I have a proof which uses concepts like "inside" and "outside". However, consider the attached picture (I know that it is hard to see, but it is basically a pentagon rotated around to obtain something like a torus). If we assing a value of $2024$ to all black edges, a value of $506$ to all red edges and a value of $1518$ to all blue edges, we find that the sum is $0\pmod{2024}$ for all faces except one. Did I miss something?
Attachments:
rtyu852
07.01.2024 08:00
Davsch wrote: I'm not sure I understood the problem correctly. I am convinced that the claim holds if the polyhedron has "no holes" and I have a proof which uses concepts like "inside" and "outside". However, consider the attached picture (I know that it is hard to see, but it is basically a pentagon rotated around to obtain something like a torus). If we assing a value of $2024$ to all black edges, a value of $506$ to all red edges and a value of $1518$ to all blue edges, we find that the sum is $0\pmod{2024}$ for all faces except one. Did I miss something? Your concern is correct, and in fact, the statement missed one crucial assumption is that $D$ is a convex polyhedron. A mistake I saw a lot on the Vietnamese forum is that people overlook this condition and treat this polyhedron as a normal graph, while in fact, convexity constitutes a crucial property for this problem to hold: planarity. Thank you for giving one counterexample. For this one, essentially we want to prove that the polyhedron is 2-face-colorable, i.e. you can color the faces with two colors red and blue, so that any two adjacent faces, or faces that share an edge, have different colors. To show this, take the dual graph of this polyhedron, where vertices are faces, and an edge is formed between two vertices if the corresponding two faces share an edge. Due to the convexity of $D$, you can then project this dual graph into a planar graph, where every smallest cycle, or region, has an even number of edges. From this, you can show that any cycle in this planar graph is even, since any cycle in this planar graph encloses a region that can be decomposed into smaller regions with even edges, and a simple counting argument shows that the cycle is even. A graph with only even cycles is essentially bipartite, so the vertices are 2-colorable, as desired. Once you know $D$ is 2-face-colorable, then the sum of the weights of the red faces and the sum of the weights of the blue faces must be the same. The fact that the sum of weights for $F$ is divisible by $2024$ should follow naturally.
wassupevery1
07.01.2024 15:57
Davsch wrote: I'm not sure I understood the problem correctly. I am convinced that the claim holds if the polyhedron has "no holes" and I have a proof which uses concepts like "inside" and "outside". However, consider the attached picture (I know that it is hard to see, but it is basically a pentagon rotated around to obtain something like a torus). If we assing a value of $2024$ to all black edges, a value of $506$ to all red edges and a value of $1518$ to all blue edges, we find that the sum is $0\pmod{2024}$ for all faces except one. Did I miss something? Oh yeah, the statement did say the polyhedron is, convex. Oopsie.
phungthienphuoc
08.01.2024 01:23
Here is one approach for this problem. Edit: After reading post #3, I find that I use the same idea as @rtyu852, so I will let this post as a more detail version.
Because the polyhedron $D$ is convex, it can be considered as a planar graph $G$ where the vectices of graph are corresponding to the vertices of $D$, and two vertices in $G$ are connected if and only if two corresponding vertices in $D$ are connected.
Let $G'$ be the dual graph of $G$. Apparently, each vertex of $G$ is corresponding to a face of $G'$, and each face of $G$ is corresponding to a vertex in $G'$. Because for every vertex of $G$, there are an even number of edges passing through it, each face of $G'$ surrounded by an even number of edges. In other words, each face of $G'$ is formed by an even cycle.
Suppose that there exists an odd cycle $C=v_{1}v_{2}\ldots v_{k}v_1$ in $G'$. WLOG, suppose that the area of the interior region of $C$ is minimal. From the claim above, $C$ can not form a face in $G'$, so there exists to vertex $v_{i},v_{j}\in C$ and a path $P$ connecting $v_{i}$ and $v_{j}$ which does not share any edge with $C$ and lies inside $C$.
Because $C$ is an odd cycle, the lengths of two paths $P_1=v_{i}v_{i+1}\ldots v_{j}$ and $P_2=v_{j}v_{j+1}...v_{i}$ in $C$ have different parities.
Because $P$ does not share any edge with $C$, or, in other words, $P_1$ and $P_2$, the pairs $(P,P_1)$ and $(P,P_2)$ make two new cycles $C_1$ and $C_2$ respectively. The lengths of $P_1$ and $P_2$ have the different parities, and so do $C_1$ and $C_2$. Without loss of generality, assume that $C_1$ is an odd cycle.
However, the area the interior region of $C_1$ is apparently smaller than $C$'s, which contradicts our assumption about $C$.
Thus, there is no odd cycle in $G'$, which implies that $G'$ is a bipartite graph. Let $A$ and $B$ be two part of the graph $G'$. We color all the vertices of $A$ and $B$ by red and green respectively.
Now, we color all the face of $G$: a face is red if it is corresponding to a red vertex of $G'$, and vice versa. Without loss of generality, assume that $F$ is red. Since then, we choose all the green faces of $G$.
Because every edge in $G$ belongs to one red face and one green face, it must be chosen exactly once. Therefore, if we take the sum of all numbers assigned to all the chosen edges, we will obtain the sum of numbers assigned to all edges of $G$. We denote that sum by $s$. Additionally, according to the hypothesis, the sum of all the edges of a face other than $F$ is divisible by $2024$, so $s$ is divisible by $2024$.
Notice that if the take the sum of all edges assign to each face, and take the sum of all obtained values, we will get $2s$, which is divisible by $2024$. Hence, the sum of all numbers assigned to the edges of $F$ is divisible by $2024$.