Problem A. 884. (September 2024)

A. 884. We fill in an \(\displaystyle n\times n\) table with real numbers such that the sum of the numbers in each row and each coloumn equals 1. For which values of \(\displaystyle K\) is the following statement true: if the sum of the absolute values of the negative entries in the table is at most \(\displaystyle K\), then it's always possible to choose \(\displaystyle n\) positive entries of the table such that each row and each coloumn contains exactly one of the chosen entries.

Proposed by Dávid Bencsik, Budapest

(7 pont)

Deadline expired on October 10, 2024.

Let us consider the following bipartite graph associated with the table: vertices \(\displaystyle r_1\), \(\displaystyle r_2\),..., \(\displaystyle r_n\) are corresponding to the rows of the table, vertices \(\displaystyle c_1\), \(\displaystyle c_2\),..., \(\displaystyle c_n\) are corresponding to the columns of the table, and we connect vertex \(\displaystyle r_i\) and \(\displaystyle c_j\) iff the value at the intersection of the \(\displaystyle i^{th}\) row and the \(\displaystyle j^{th}\) column is positive. Now the problem translates to being able to find a perfect matching in this bipartite graph, i.e. \(\displaystyle n\) edges covering all \(\displaystyle 2n\) vertices. According to König's theorem this is equivalent to not being able to find less than \(\displaystyle n\) vertices covering all edges of the graph. Now we show that if \(\displaystyle K<1\), this latter condition is true: suppose that we can cover all edges with less than \(\displaystyle n\) vertices. This translates back to the condition that it is possible to find less than \(\displaystyle n\) rows and columns that cover all positive values in the table. However, this means that the sum of the values in the table is at most the sum of the elements in these rows and columns minus those elements that were added twice in the intersection of these rows and columns, thus it's at most \(\displaystyle n-1+K<n\), which is a contradiction, since clearly the sum of all elements in the table is exactly \(\displaystyle n\), since the sum in each row is 1.

Now let's construct an example for \(\displaystyle n>2\) and \(\displaystyle K\ge 1\): the first row is filled out (from left to right) with \(\displaystyle n-2\) values of \(\displaystyle -1/(n-2)\) and two 1's, and the rest of the rows are filled out with \(\displaystyle n-2\) values of \(\displaystyle 1/(n-2)\) and two 0's. Now it's easy to check that the sum of the negative elements is -1, the sum of the elements in each row and each column is 1, and it's not possible to choose positive values according to the condition since all positive values can be covered with the first row and first \(\displaystyle n-2\) columns.

For \(\displaystyle n=1\) and \(\displaystyle n=2\) the conditions can always be satisfied.

Statistics:

25 students sent a solution.
7 points:	Bodor Mátyás, Czanik Pál, Forrai Boldizsár, Holló Martin, Prohászka Bulcsú, Szabó 721 Sámuel, Szakács Ábel, Varga Boldizsár, Vödrös Dániel László.
6 points:	Bui Thuy-Trang Nikolett, Kocsis 827 Péter, Sánta Gergely Péter, Tamás Gellért, Virág Tóbiás.
5 points:	2 students.
4 points:	3 students.
3 points:	2 students.
2 points:	2 students.
1 point:	1 student.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, September 2024