Consider a convex polyhedron $P$ in three-dimensional Euclidean space. Let $V$ be the set of vertices and $E$ be the set of edges of $P$.
I use the following ad-hoc definition of a mapping: A mapping on P is any function from $E$ to the set $\{-1, +1\}$.
An additional ad-hoc definition: given a polyhedron $P$ as above, with vertices $V$ and edges $E$, and a mapping $m$ (as just defined), for every vertex $v \in V$ let the product at $v$ be the product of the $-1$ and $+1$ values associated by $m$ to the edges that have $v$ as one of the endpoints.
With these definitions, prove the following:
- For every polyhedron $P$ with 2019 vertices, and for every mapping on $P$, there is always at least one vertex $v$ so that the product at $v$ is $+1$.
- For every polyhedron $P$ with 2020 vertices, there is at least one mapping on $P$ so that the product at $v$ is $-1$ for all vertices $v \in V$.
Of these, 1. is relatively easy (and relatively standard for an olympiad problem). The interesting problem, really, is 2.
Make sure you understand 2. correctly. It is not about finding one counterexample to 1. on some polyhedron with 2020 vertices; that's very easy. Rather, it is to show that 1. fails for all polyhedra with 2020 vertices, no matter what their (combinatorial) shape.
BACKGROUND: A very long time ago I created this problem and we used it in one of the examinations to select our national team for the IMO. There was no Internet then (at least, certainly, not in the East European country I'm from), so I doubt it very strongly that this problem has ever made it to the Internet. Obviously, I have a solution (my own!) but I am offering this as a fun challenge to math enthusiasts on SE. It will be fun to see what other solutions are being offered.
Best Answer
$$\prod_{v \in V} \text{product at } v = \prod_{v} \prod_{v \in e } P(e) = \prod_{e} P(e)^2 = 1.$$
Hence the number of vertices that have product of -1 is even, so an odd number (in particular, at least 1) of vertices have a product of 1.
2.
Claim: For any connected graph with an even number $n=2m$ of vertices, we can find a subset of edges such that the degree at each vertex is odd.
Proof: This is an olympiad problem, of which there are several (pretty distinct) solutions. The solution that I like takes the symmetric difference of $m$ paths, connecting distinct vertices. Adding a path changes the parity of the endpoints and nothing else, thus the resultant parity of each vertices degree is odd.
Corollary: Giving those edges $-1$ will lead to each vertex having a product of $-1$.
Note: