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
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:

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.
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.
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.