146. a) Two players are playing a game. The first player writes down two rows of 10 numbers each, such that the following rule is satisfied: if the number $b$ is written under the number $a$, and the number $d$ is written under the number $c$, then $a+d=b+c$. The second player, knowing this rule, wants to determine all the written numbers. He is allowed to ask the first player questions of the type "What number is in the first row in the third position?" or "What number is in the second row in the ninth position?" and so on. What is the minimum number of such questions the second player needs to ask to find out all the numbers?

b) In an $m \times n$ table, numbers are written such that for any two rows and any two columns, the sum of the numbers in the two opposite corners of the formed rectangle is equal to the sum of the numbers in the other two corners. Some of the numbers have been erased, but the remaining numbers can be used to restore the erased ones. Prove that at least $m+n-1$ numbers remain.
146. a) Answer: 11 questions. Knowing all 10 numbers in one row and one in another, it is easy to restore all the other numbers. If, however, only 10 questions are asked, it is impossible to uniquely restore the numbers; on the one hand, in each column, at least one number must be known—otherwise, an arbitrary number $x$ can be added to both numbers in that column, preserving the required property of the table; on the other hand, in at least one column, both numbers must be known—otherwise, an arbitrary number $y$ can be taken as the difference between the numbers in each column and the table can be constructed from the available data.

b) The proof can be conducted by induction. We will assume that $n \geqslant m$, and perform induction on $m+n$. If in one of the $n$ columns no number is known, then, obviously, the numbers

6 N. E. Vasilyev, A. A. Egorov 101
cannot be uniquely restored. If, however, in each of the $n$ columns there are known numbers, then (since the total number of $m+n-2$ known numbers is no more than $2 n-2$) there will be a column where only one number is known, and the remaining table $(n-1) \times m$ contains only $m+(n-1)-2$ known numbers and, by the induction hypothesis, cannot be uniquely restored.

$\checkmark$ The estimate in this problem is exact: a table of the form

$$
\begin{array}{lll}
x_{1}, & x_{2}, & \ldots x_{n} \\
x_{1}+y_{1}, & x_{2}+y_{1}, & \ldots x_{n}+y_{1} \\
\cdot \cdots \cdot \\
x_{1}+y_{m-1}, & x_{2}+y_{m-1}, \ldots x_{n}+y_{m-1}
\end{array}
$$

can be restored from $m+n-1$ numbers in the first row and the first column.

The answer to the more subtle question—what specific sets $\Gamma$ of numbers in the $m \times n$ table are suitable for this—can be formulated in the language of graph theory (P.).

Consider a "bipartite graph" $\Gamma$ with $m+n$ vertices $A_{1}, \ldots, A_{m}$ and $B_{1}, \ldots, B_{n}$, in which some vertices $A_{g}$ are connected to some $B_{\text {l }}$; this specifies some set $\tilde{\Gamma}$ of pairs $(i, j)$—elements of the $m \times n$ table $(i=1,2, \ldots, \ldots m ; j=1,2, \ldots n)$. For such a set $\widetilde{\Gamma}$ of pairs of numbers to uniquely restore the entire table, it is necessary and sufficient that the graph $\Gamma$ be connected. In a tree with $m+n$ vertices, according to problem 8, there will be exactly $m+n-1$ edges; if $\Gamma$ is a tree, then any set of $m+n-1$ numbers occupying cells $(i, j) \in \widetilde{\Gamma}$ can be completed so that the resulting table has the required form.