Given a polyhedron $P$. Mikita claims that he can write one integer on each face of $P$ such that not all the written numbers are zeros, and for each vertex $V$ of $P$ the sum of numbers on faces containing $V$ is equals to 0. Matvei claims that he can write one integer in each vertex of $P$ such that not all the written numbers are zeros, and for each face $F$ of $P$ the sum of numbers in vertices belonging to $F$ is equals to 0. Show that if the number of edges of polyhedron $P$ is odd, then at least one of the boys is right.
Problem
Source: Belarusian-Iranian 3rd friendly competition
Tags: combinatorics
01.08.2024 16:16
fake solved
01.08.2024 19:01
sami1618 wrote: Mikta can alternately write $1$ and $-1$ on each of the adjacent faces and write $0$ on all other faces Why should it work? For example, if one of the adjacent faces is a quadraliteral, then in this quadraliteral the opposite vertex to the one with even number of edges is contained in faces with one non-zero number and other zeros, so the sum won't be zero.
01.08.2024 20:01
Does this work? Let $f_i$, $1\leq i\leq m$, and $v_j$, $1\leq j\leq n$, denote the faces and vertices of $P$. Let $t_{i,j}=1$ if $f_i$ and $v_j$ are adjacent and $0$ otherwise. As $V-E+F=2$ we have that $V\neq F$ so WLOG assume that $n<m$. Then let Mikita assign $x_i$ to each face $f_i$. We then have that $$t_{1,j} x_1+t_{2,j} x_2+\dots+t_{m,j}x_m=0$$for each $j$, $1\leq j \leq n$. So it suffices to show that this equation has a non-zero solution. We prove by induction that for $n$ variables and less then $n$ linear equations equal to $0$ there exists a non-trivial solution. To do this solve for one of the variables in the first equation and substitute it into all other equations, reducing the amount of variables and equations by one. Continue until you have found a non-trivial solution.
01.08.2024 22:08
It almost works, as the problem doesn't say $P$ is convex, so $V-E+F \vdots 2$, but not necessarily $2$
01.08.2024 22:28
Do you know the official solution?
01.08.2024 23:07
Yes. Same as your one except for what I have written in #5. Also, the fact that a homogenous linear system of equations where there are more variables than equations has a non-trivial solution goes without proof because it is quite well-known.
02.12.2024 13:50
Hey but what if one rights 1 on all faces or vertices? Then none of the boys is right and the question becomes self-contradictory
08.12.2024 14:44
Then the statement that the sum of the numbers on faces that contain a certain vertex does not hold.