Maths Olympiad Prep

Library / /6 of 6

Algebra Difficulty 9.0 Shortlist Prove it Vietnam

Given a convex polyhedron with 2022 faces. In 3 arbitrary faces, there are already numbers 26, 4 and 2022 (each face contains one number). One wants to fill in each other face a real number which is the arithmetic mean of every number in faces that share a common edge with that face. Prove that there is exactly one way to fill all the numbers in that polyhedron.

Solution

First, we will prove the following lemma:

Lemma. Given a positive integer nn. Prove that the system of linear equations with nn variables (x1,x2,,xn)(x_1, x_2, \dots, x_n)
{a11x1++a1nxn=b1,an1x1++annxn=bn(4.1) \left\{ \begin{array}{l} a_{11}x_1 + \cdots + a_{1n}x_n = b_1, \\ \cdots \\ a_{n1}x_1 + \cdots + a_{nn}x_n = b_n \end{array} \right. \qquad (4.1)
has exactly one solution if the associated homogeneous system (which means b1==bn=0b_1 = \cdots = b_n = 0) has only one solution x1==xn=0x_1 = \cdots = x_n = 0.

Proof. Assume that both of (x1,,xn)(x_1, \dots, x_n) and (y1,,yn)(y_1, \dots, y_n) are the solutions of this system, we have
{a11(x1y1)++a1n(xnyn)=0,an1(x1y1)++ann(xnyn)=0 \left\{ \begin{aligned} & a_{11}(x_1 - y_1) + \cdots + a_{1n}(x_n - y_n) = 0, \\ & \cdots \\ & a_{n1}(x_1 - y_1) + \cdots + a_{nn}(x_n - y_n) = 0 \end{aligned} \right.
hence by the given condition, we obtain that x1y1=x2y2==xnyn=0x_1 - y_1 = x_2 - y_2 = \dots = x_n - y_n = 0, which means the system has at most one solution.

We will prove this system always has a solution by induction for nn. It is obvious for n=1n = 1. Assume that the lemma is proved for n1n-1. It is clear that if aij=0a_{ij} = 0 for all pairs (i,j)(i, j) then the associated homogeneous system has infinite solutions, hence there must exist aij0a_{ij} \neq 0. Without loss of generality, assume that ann0a_{nn} \neq 0. The system can be rewritten as follows
{i=1n1(a1iania1nann)xi=b1bna1nann,i=1n1(a2iania2nann)xi=b2bna2nann,i=1n1(an1,ianian1,nann)xi=bn1bnan1,nann,i=1nanixi=bn \left\{ \begin{aligned} & \sum_{i=1}^{n-1} \left( a_{1i} - a_{ni} \frac{a_{1n}}{a_{nn}} \right) x_i = b_1 - b_n \frac{a_{1n}}{a_{nn}}, \\ & \sum_{i=1}^{n-1} \left( a_{2i} - a_{ni} \frac{a_{2n}}{a_{nn}} \right) x_i = b_2 - b_n \frac{a_{2n}}{a_{nn}}, \\ & \cdots \\ & \sum_{i=1}^{n-1} \left( a_{n-1,i} - a_{ni} \frac{a_{n-1,n}}{a_{nn}} \right) x_i = b_{n-1} - b_n \frac{a_{n-1,n}}{a_{nn}}, \\ & \sum_{i=1}^{n} a_{ni} x_i = b_n \end{aligned} \right.
Clearly, if the system
{i=1n1(a1iania1nann)xi=0,i=1n1(a2iania2nann)xi=0,i=1n1(an1,ianian1,nann)xi=0 \left\{ \begin{aligned} & \sum_{i=1}^{n-1} \left( a_{1i} - a_{ni} \frac{a_{1n}}{a_{nn}} \right) x_i = 0, \\ & \sum_{i=1}^{n-1} \left( a_{2i} - a_{ni} \frac{a_{2n}}{a_{nn}} \right) x_i = 0, \\ & \cdots \\ & \sum_{i=1}^{n-1} \left( a_{n-1,i} - a_{ni} \frac{a_{n-1,n}}{a_{nn}} \right) x_i = 0 \end{aligned} \right.
has a solution (y1,y2,,yn1)(0,0,,0)(y_1, y_2, \dots, y_{n-1}) \neq (0, 0, \dots, 0) then the homogeneous system with nn variables (x1,x2,,xn)(x_1, x_2, \dots, x_n)
{i=1n1(a1iania1nann)xi=0,i=1n1(a2iania2nann)xi=0,i=1n1(an1,ianian1,nann)xi=0,i=1nanixi=0 \left\{ \begin{array}{l} \displaystyle \sum_{i=1}^{n-1} \left( a_{1i} - a_{ni} \frac{a_{1n}}{a_{nn}} \right) x_i = 0, \\ \displaystyle \sum_{i=1}^{n-1} \left( a_{2i} - a_{ni} \frac{a_{2n}}{a_{nn}} \right) x_i = 0, \\ \vdots \\ \displaystyle \sum_{i=1}^{n-1} \left( a_{n-1,i} - a_{ni} \frac{a_{n-1,n}}{a_{nn}} \right) x_i = 0, \\ \displaystyle \sum_{i=1}^{n} a_{ni} x_i = 0 \end{array} \right.
has a root (y1,y2,,yn1,0)(y_1, y_2, \dots, y_{n-1}, 0), which is a contradiction. Thus, applying the assumption for n1n-1, the system
{i=1n1(a1iania1nann)xi=b1bna1nann,i=1n1(a2iania2nann)xi=b2bna2nann,i=1n1(an1,ianian1,nann)xi=bn1bnan1,nann \left\{ \begin{array}{l} \displaystyle \sum_{i=1}^{n-1} \left( a_{1i} - a_{ni} \frac{a_{1n}}{a_{nn}} \right) x_i = b_1 - b_n \frac{a_{1n}}{a_{nn}}, \\ \displaystyle \sum_{i=1}^{n-1} \left( a_{2i} - a_{ni} \frac{a_{2n}}{a_{nn}} \right) x_i = b_2 - b_n \frac{a_{2n}}{a_{nn}}, \\ \vdots \\ \displaystyle \sum_{i=1}^{n-1} \left( a_{n-1,i} - a_{ni} \frac{a_{n-1,n}}{a_{nn}} \right) x_i = b_{n-1} - b_n \frac{a_{n-1,n}}{a_{nn}} \end{array} \right.
has exactly one solution (z1,,zn1)(z_1, \dots, z_{n-1}) and note that
xn=bni=1n1anibiann, x_n = \frac{b_n - \sum_{i=1}^{n-1} a_{ni} b_i}{a_{nn}},
which implies that the lemma is also true for nn. \square

Back to our problem, let a1,a2,,a2019a_1, a_2, \dots, a_{2019} be the remaining numbers on 2019 faces and denote a2020=4,a2021=26,a2022=2022a_{2020} = 4, a_{2021} = 26, a_{2022} = 2022. Next, we write bi,j=1b_{i,j} = 1 if the face containing aia_i has a common edge with the face containing aja_j, otherwise we write bi,j=0b_{i,j} = 0. Denote
bii=j=1,jinbij. b_{ii} = - \sum_{j=1, j \neq i}^{n} b_{ij}.
By the given conditions, we have the following system
{j=12019b1,jaj=4b1,202026b1,20212022b1,2022,j=12019b2,jaj=4b2,202026b2,20212022b2,2022,j=12019b2019,jaj=4b2019,202026b2019,20212022b2019,2022. \left\{ \begin{array}{l} \displaystyle \sum_{j=1}^{2019} b_{1,j}a_j = -4b_{1,2020} - 26b_{1,2021} - 2022b_{1,2022}, \\ \\ \displaystyle \sum_{j=1}^{2019} b_{2,j}a_j = -4b_{2,2020} - 26b_{2,2021} - 2022b_{2,2022}, \\ \\ \vdots \\ \\ \displaystyle \sum_{j=1}^{2019} b_{2019,j}a_j = -4b_{2019,2020} - 26b_{2019,2021} - 2022b_{2019,2022}. \end{array} \right.
Applying the lemma, it is clear that we only need to prove the system
{j=12019b1,jaj=0,j=12019b2,jaj=0,j=12019b2019,jaj=0, \left\{ \begin{array}{l} \displaystyle \sum_{j=1}^{2019} b_{1,j}a_j = 0, \\ \\ \displaystyle \sum_{j=1}^{2019} b_{2,j}a_j = 0, \\ \\ \vdots \\ \\ \displaystyle \sum_{j=1}^{2019} b_{2019,j}a_j = 0, \end{array} \right.
has exactly one solution a1=a2==a2019=0a_1 = a_2 = \dots = a_{2019} = 0. Assume that this system has another solution, which means there exists jj such that aj0a_j \neq 0. Without loss of generality, assume that
a1=max{ai:1i2019}>0. a_1 = \max\{a_i : 1 \leq i \leq 2019\} > 0.
We observe that
M(i=22019b1,i)i=22019b1,iai=a1(i=22022b1,i)M(i=22019b1,j), M \left( \sum_{i=2}^{2019} b_{1,i} \right) \geq \sum_{i=2}^{2019} b_{1,i} a_i = a_1 \left( \sum_{i=2}^{2022} b_{1,i} \right) \geq M \left( \sum_{i=2}^{2019} b_{1,j} \right),
which means all the equalities must attain, or ai=Ma_i = M if b1,i=1b_{1,i} = 1 and
b1,2020=b1,2021=b1,2022=0. b_{1,2020} = b_{1,2021} = b_{1,2022} = 0.
Similarly, we obtain that for every ai=Ma_i = M then all the faces that have a common edge with aia_i contain MM and the face that contains aia_i has no common edge with the faces that contain a2022,a2021a_{2022}, a_{2021} and a2020a_{2020}. Denote A={i2019:ai=M},B={1,2,,2022}AA = \{i \ge 2019 : a_i = M\}, B = \{1, 2, \dots, 2022\} \setminus A. Clearly, there exists iA,jBi \in A, j \in B such that the face containing aia_i has a common edge with the face containing aja_j, which is a contradiction. Hence, the assumption is wrong, which means there exists a1a_1 such that a1<0a_1 < 0. Consider the solution
(c1,c2,,c2019)=(a1,a2,,a2019), (c_1, c_2, \dots, c_{2019}) = (-a_1, -a_2, \dots, -a_{2019}),
we have a solution with the biggest number positive, which is a contradiction. Thus, ai=0a_i = 0 for all ii from 1 to 2019 is the only solution of that homogeneous system. Applying the lemma, the system has exactly one solution. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.