Given a convex polyhedron with 2022 faces. In 3 arbitary faces, there are already number $26; 4$ and $2022$ (each face contains 1 number). They want to fill in each other face a real number that is an arithmetic mean of every numbers in faces that have a common edge with that face. Prove that there is only one way to fill all the numbers in that polyhedron.
Problem
Source: Vietnam TST 2022 P2
Tags: polyhedron, combinatorics
21.05.2022 17:09
A solution without linear algebra. We use this lemma: Given $n^2$ real number $a_{i,j}, 1 \le i,j\le n$ satisfy $a_{i,i} > 0$ for all $1 \le i \le n$, $a_{i,j}\le 0$ for all $i \ne j$, $a_{i,1}+a_{i,2}+\dots +a_{i,n} \ge 0$ for all $1 \le i \le n$. Then for all $e_1,e_2,\dots e_n \in \mathbb{R}$, this set of functions with variables $x_1,x_2,\dots,x_n$ has only one root \begin{align} \begin{cases} a_{1,1}x_1+a_{1,2}x_2+\dots +a_{1,n}x_n=e_1 \\ a_{2,1}x_1+a_{2,2}x_2+\dots +a_{2,n}x_n=e_2 \\ ... \\ a_{n,1}x_1+a_{n,2}x_2+\dots +a_{n,n}x_n=e_n \end{cases} \end{align}$\quad$$\quad$$\quad$$\quad$ I prove this by induction on n. Its'obivious when $n=1$. Suppose this lemma is true for $n-1$. Consider $(1)$. Because $a_{n,n} >0, a_{n,i} \le 0$ for all $1\le i \le n-1$, $i \ne j$, $a_{n,1}+a_{n,2}+\dots +a_{n,n} \ge 0$, we have $a_{n,1}x_1+a_{n,2}x_2+\dots +a_{n,n}x_n=e_n \leftrightarrow x_n= b_1 x_1+b_2 x_2+\dots+b_{n-1}x_{n-1}+f$ satisfy $b_1,b_2,\dots,b_{n-1} \ge0, b_1+b_2+\dots+b_{n-1} \le 1$ $\quad$$\quad$Now, for all $1 \le i,j \le n-1$, Let $c_{i,j}=a_{i,j}+a_{i,n}b_i$; for all $1 \le i \le n-1$, let $d_i=e_i-fa_{i,n}$ Then the the remaining $n-1$ equations are equivalent to $\begin{cases} c_{1,1}x_1+c_{1,2}x_2+\dots +c_{1,n-1}x_{n-1}=d_1 \\ c_{2,1}x_1+c_{2,2}x_2+\dots +c_{2,n-1}x_{n-1}=d_2 \\ ... \\ c_{n-1,1}x_1+c_{n-1,2}x_2+\dots +c_{n-1,n-1}x_n=d_{n-1} \end{cases}$. $\quad$$\quad$Now, for all $1 \le i \le n$, because $b_1,b_2,\dots,b_{n-1} \ge0, b_1+b_2+\dots+b_{n-1} \le 1$ , $a_{i,i} > 0$ for all $1 \le i \le n$, $a_{i,j}\le 0$ for all $i \ne j$, $a_{i,1}+a_{i,2}+\dots +a_{i,n} \ge 0$, we easily get $c_{i,i} > 0$ for all $1 \le i \le n-1$, $c_{i,j}\le 0$ for all $i \ne j$, $c_{i,1}+c_{i,2}+\dots +c_{i,n-1} \ge 0$. By induction , this set of $n-1$ function has only one root, so (1) has only one root. Therefore, the lemma is proven, Q.E.D $\quad$$\quad$$\quad$$\quad$With this lemma, first let $x_1,x_2,...,x_{2019} $ be 2019 variables presented for 2019 empty faces. It easily follows that these 2019 variables must satisfy 2019 function, which has the form $ \begin{cases} a_{1,1}x_1+a_{1,2}x_2+\dots +a_{1,2019}x_{2019}=e_1 \\ a_{2,1}x_1+a_{2,2}x_2+\dots +a_{2,2019}x_{2019}=e_2 \\ ... \\ a_{2019,1}x_1+a_{2019,2}x_2+\dots +a_{2019,2019}x_{2019}=e_{2019} \end{cases}$ satisfy $a_{i,i}=4$ for all $1 \le i \le 2019$ $,a_{i,j} \in \{0,-1\}$ for all$ i \ne j$ and $a_{i,1}+a_{i,2}+\dots+a_{i,2019} \ge 0$ for all $1 \le i \le 2019$ $\quad$$\quad$It follows directly from the lemma that this set of function has only one root, which means there is only one way to fill all the numbers in that polyhedron Q.E.D
08.05.2024 08:01
If we turn this problem into linear equations system with $2019$ variables and $2019$ equations, we notice that the constant terms does not affect: $1$. The way we solve this system (by some manipulations like adding $2$ equations, minus $2$ equations, ...) $2$. and whether the solution set is unique or not Therefore, we just replace $26, 4, 2022$ with $0, 0, 0$ without changing the outcome. Now, we prove the way fill is unique by proving this: the number on every neighbor faces of a face contains $0$ are all $0$. Assume there exists a face with number $x < 0$ next to a face with $0$ As $x$ is not $0$, so $x$ is mean of numbers on neighbor faces. Let $x_1$ be the smallest number among numbers on neigbor faces. Then $x_1 < x < 0$. Similarly, let $x_2$ be the smallest number among numbers on neighbor faces of $x_1$, then $x_2 < x_1 < x < 0$. Keep doing so to get the negative and decreasing sequence $x_1, x_2, ...$. This means all $x_i$ are different so there are infinite numbers on the polyhedron, contradiction. Therefore, the number on every neighbor faces of a face contains $0$ are all $0$. This follows every faces contains $0$, which means the way to fill is unique.