Назовём округлением нецелого числа $x$ замену его на одно из двух ближайших целых чисел ($[x]$ или $[x]+1$).
Докажите, что в любом равенстве
$$
x_1+x_2+\ldots+x_m=y_1+y_2+\ldots+y_n
$$
все нецелые слагаемые можно округлить так что равенство останется верным.
В таблице из $m$ строк и $n$ столбцов записаны некоторые числа, причём их суммы по строкам $a_1$, $a_2$, $\ldots$, $a_m$ и по столбцам $b_1$, $b_2$, $\ldots$, $b_n$ — целые числа. Докажите, что все нецелые числа в таблице можно округлить так, что суммы по строкам и столбцам не изменятся.
Пусть теперь суммы $a_1$, $a_2$, $\ldots$, $a_m$, $b_1$, $b_2$, $\ldots$, $b_n$ не обязательно целые. Докажите, что нецелые числа в таблице можно округлить так, что их суммы по строкам и столбцам будут округлением соответствующих сумм $a_1$, $a_2$, $\ldots$, $a_m$, $b_1$, $b_2$, $\ldots$, $b_n$.
а) Прежде всего, заметим, что утверждение задачи достаточно доказать для равенства вида
$$
x_1+\ldots+x_m=0.\tag{*}
$$
(Общий случай сведётся к этому, если перенести все слагаемые из правой части в левую и учесть, что округления числа $-y_i$ совпадают с округлениями $y_i$, взятыми со знаком минус, поскольку
$-[y_i]-1\le-y_i\le-[y_i]$.)
Будем округлять числа $x_i$ в равенстве (*) поочерёдно: одно из них будет округляться, а какое-то другое мы одновременно изменим на такую же величину в противоположном направлении — при этом данное равенство не нарушится. Надо только позаботиться, чтобы округления изменяемых чисел оставались прежними. После не более чем $m-1$ таких шагов мы округлим все числа в равенстве (*), причём оно останется верным.
Итак, пусть в равенстве (*) есть нецелые числа. Очевидно, их, по крайней мере, два, скажем, $x_i$ и $x_j$. Допустим, что расстояние $d$ от $x_i$ до ближайшего целого $x'_i$ не больше такого же расстояния для $x_j$. Заменим $x_i$ на $x'_i$, а $x_j$ на $x'_j=x_j+(x_i-x'_i)$. При этом число округлённых слагаемых увеличится, их сумма останется нулевой, а округления числа $x'_j$ будут такими же, как у $x_j$, так как $[x_j]\le x'_j\le[x_j]+1$.
б), в) Будем действовать по тому же плану, как в пункте a). Припишем к $i$-й строке число $-a_i$, $i=1$, $\ldots$, $m$, под $j$-м столбцом — число $-b_j$, $j=1$, $\ldots$, $n$, а в правом нижнем углу этой расширенной таблицы поставим сумму всех данных чисел $s=a_1+\ldots+a_m=b_1+\ldots+b_n$. Очевидно, достаточно доказать утверждение б) (или в)) для новой таблицы, т. е. при условии, что суммы чисел по всем строкам и столбцам равны нулю. Чтобы это условие сохранилось при округлении очередного числа, нам надо будет вместе с этим числом изменить целую цепочку чисел, причём их округления должны остаться прежними. Опишем построение такой цепочки.
Возьмём в таблице какое-нибудь нецелое число $x_1$; в одной строчке с ним обязательно есть ещё одно нецелое число $x_2$, в одном столбце с $x_2$ — нецелое $x_3$, в одной строчке с $x_3$ — нецелое $x_4$ и т. д. (см. рисунки 1, 2). В какой-то момент мы непременно придём к числу, которое стоит в одном ряду (строке или столбце) с числом, встречавшимся ранее. Пусть $x_k$ — первое такое число и пусть оно стоит, скажем, в одном столбце с $x_l$ ($l\lt k$).
Предположим, что $x_{l+1}$ стоит в одной строке с $x_l$ (рис. 1). Тогда рассмотрим цепочку чисел $x_l$, $x_{l+1}$, $\ldots$, $x_k$. Любые два последовательных числа в этой цепочке стоят в одном ряду (следующим за $x_k$ считаем $x_l$), причём на каждом шагу цепочка «поворачивает на $90^\circ$», поэтому в одной строке, а также в одном столбце с любым из них стоит ещё ровно одно, а общее количество чисел в цепочке чётно. Выберем то из них, которое стоит ближе всего к целому числу (если таких несколько, то любое из них), пусть это число $x_i$, а ближайшее целое число равно $x_i+d$. Заменим $x_i$ на его округление $x_i+d$ и, двигаясь по цепочке, будем к каждому следующему числу поочерёдно добавлять $-d$ или $d$ ($x_{i+1}$ заменим на $x_{i+1}-d$, $x_{i+2}$ — на $x_{i+2}+d$ и т. д.). Когда мы пройдём всю цепочку, получится новая таблица с нулевыми суммами по строкам и столбцам, округления всех нецелых чисел в ней будут такими же, как раньше, а количество целых чисел возрастёт.
Рис. 1Рис. 2
Если окажется, что $x_{l+1}$ стоит в одном столбце с $x_l$ (рис. 2), то точно такое же рассуждение надо провести с цепочкой $x_{l+1}$, $x_{l+2}$, $\ldots$, $x_k$.
После нескольких повторений этой операции все числа в таблице станут целыми.
Для задачи в) мы попутно доказали, что сумма построенных нами округлений чисел исходной таблицы является округлением их суммы.
