Problem A. 839. (December 2022)

A. 839. We are given a finite, simple, non-directed graph. Ann writes positive real numbers on each edge of the graph such that for all vertices the following is true: the sum of the numbers written on the edges incident to a given vertex is less than one. Bob wants to write non-negative real numbers on the vertices in the following way: if the number written at vertex \(\displaystyle v\) is \(\displaystyle v_0\), and Ann's numbers on the edges incident to \(\displaystyle v\) are \(\displaystyle e_1,e_2, \dots, e_k\), and the numbers on the other endpoints of these edges are \(\displaystyle v_1, v_2, \dots, v_k\), then \(\displaystyle v_0=\sum\limits_{i=1}^{k}e_iv_i+2022\). Prove that Bob can always number the vertices in this way regardless of the graph and the numbers chosen by Ann.

Proposed by Boldizsár Varga, Verőce

(7 pont)

Deadline expired on January 10, 2023.

Extend the graph by adding a new vertex \(\displaystyle v'\) for each vertex \(\displaystyle v\) and inserting the \(\displaystyle vv'\) edge. Write on this edge the positive real number \(\displaystyle e_v\) such that the sum of the numbers on the edges starting from vertex \(\displaystyle v\) is exactly \(\displaystyle 1\). Furthermore, we assign to the vertex \(\displaystyle v'\) the value \(\displaystyle c_{v'}=\frac{2022}{e_v}\). Denote the set of original vertices by \(\displaystyle V\) and the set of newly added vertices by \(\displaystyle V'\).

Take an arbitrary vertex \(\displaystyle v \in V\) and consider the following random walk. Initially we start from vertex \(\displaystyle v\), and at each step if we are at a vertex in \(\displaystyle V'\) then the walk ends, otherwise we move to a neighboring vertex according to the probabilities on the incident edges. This is meaningful in the augmented graph, since for all \(\displaystyle u \in V\) the sum of the numbers on the incident edges is 1. At the end of the random walk, we obtain the value \(\displaystyle c_{u'}\) assigned to the terminating vertex \(\displaystyle u' \in V'\). Let \(\displaystyle x_v\) denote the expected value of the quantity obtained at the end of the random walk started at vertex \(\displaystyle v\). We claim that if Balázs writes the value \(\displaystyle x_v\) to each vertex, he gets a proper assignment for the problem.

First, let us consider that this definition is meaningful and that the expected values \(\displaystyle x_v\) really exist. (This is not evident, for example, if the walk does not end with positive probability in finitely many steps, then the definition is not meaningful.) Let us fix the initial vertex \(\displaystyle v \in V\). Let \(\displaystyle a\) be the minimum value of \(\displaystyle e_u\) (\(\displaystyle u \in V\)). By the condition of the problem, \(\displaystyle e_u\) is positive for all \(\displaystyle u \in V\), so \(\displaystyle a>0\). After each step of the random walk it ends with probability at least \(\displaystyle a\), so the probability that it takes more than \(\displaystyle k\) steps is at most \(\displaystyle (1-a)^k\). This goes to 0 as \(\displaystyle k\) goes to \(\displaystyle \infty\), so the random walk ends after a finite number of steps with probability 1. Thus we can determine the probability that the walk ends in \(\displaystyle u'\) for all \(\displaystyle u' \in V'\), so the expected value \(\displaystyle x_v\) is really meaningful.

Let \(\displaystyle v_1\), \(\displaystyle v_2,\ldots\), \(\displaystyle v_l\) be the neighbours of vertex \(\displaystyle v\) in \(\displaystyle V\), and let \(\displaystyle e_1\), \(\displaystyle e_2,\ldots\), \(\displaystyle e_l\) be the values of the edges connecting \(\displaystyle v\) with them, respectively. Examine the expected value \(\displaystyle x_v\) after one step. With probability \(\displaystyle e_v\) we step into \(\displaystyle v'\), then we get \(\displaystyle c_{v'}\). If we step into one of the vertices \(\displaystyle v_i\) (\(\displaystyle 1 \leq i \leq l\)), which has probability \(\displaystyle e_i\), then the expexted value is \(\displaystyle x_{v_i}\). Hence

\(\displaystyle x_v=e_vc_{v'}+e_1x_1+e_2x_2+\ldots+e_lv_l=2022+\sum_{i=1}^{l}e_ix_i,\)

and this is what we wanted to prove.

Statistics:

14 students sent a solution.
7 points:	Diaconescu Tashi, Lovas Márton, Móricz Benjámin, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Sida Li, Simon László Bence, Szakács Ábel, Sztranyák Gabriella, Varga Boldizsár, Wiener Anna.
6 points:	Molnár-Szabó Vilmos.
4 points:	1 student.

Problems in Mathematics of KöMaL, December 2022