Матрицы... Комбинаторика...

[Alexos]

Дана прямоугольная матрица вещественных чисел, условимся, что элементы неотрицательные (хотя это необязательно для решения задачи). Суммы элементов каждой строки и столбца - целые числа. Нужно округлить каждый элемент матрицы до целого числа сверху или снизу так, чтобы суммы строк и столбцов не изменялись. Докажите существование решения и опишите алгоритм.

[Крипто]

Решение не простое, и алгорит сложный и длинный с поправками "или" и "если".

Обьясню:
Например мтарица 2х2(для простоты)
2,3 4,7
8,7 5,3
суммы строк 7 и 14
столбцов 11 и 10
округляем:
2 5
9 5
суммы строк 7 и 14
столбцов 11 и 10
Тут все сходится, и все просто.

Ннапример 4х4 (для простоты все числа на 2)
2,2 2,3 2,3 2,2
2,3 2,2 2,2 2,3
2,3 2,2 2,2 2,3
2,2 2,3 2,3 2,2
суммы строк и столбцов 9
округляем:
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
суммы строк и столбцов 8
Тут нескладуха. Тут в зависимости от суммы строк, столбцов - после запятой нужно округлить в большую или меньшую сторону, не по математических законах. Тогда решение есть. Если руководствоваться мат. - решения нет!

И еще. Берем частный случай где есть 5 после запятой.
Пример матрица 4х4(тоже для простоты и наглядности)
3,4 6,5 8,5 2,6
3,5 6,2 4,8 4,5
5,5 2,8 3,2 1,5
1,6 2,5 3,5 0,4
с. строк 21; 19; 13; 8
столбцев 14; 18; 20 ; 9
Округляем (числа с 5 после запятой округляются в большую сторону) получаем:
3 7 9 3
4 6 5 5
6 3 3 2
2 3 4 0
строк 22; 20; 14; 9
столбцев 15; 19; 21 ; 10
Нескладуха опять!
А вот тут одну 0,5 надо округлять в 1 а вторую в 0. Если так поступать то решение есть(тут тоже игнорим мат. законы). А если обе округлить в 1, то решения нет для данного случая!

Теоретически можно придумать алгоритм с кучей поправок, но описывать его лично мне лень. Правда программа базируется на логике, а не на математике...

[moonlight]

Пусть задана матрица m x n.

Элементы матрицы Aⁱ_j, i=1..m-1, j=1..n-1 округляем до ближайшего целого прибавляя к каждому некоторое b. Столько же прибавляем к Aⁱ⁺¹_j+1 и отнимаем от Aⁱ_j+1 и Aⁱ⁺¹_j. Элементы Aⁱ_n, A^m_j при этом также станут целыми.
Получим матрицу у которой все суммы будут такими же как и у заданной матрицы, но некоторые элементы могут отличаться более чем на 1. Пусть это A^k_l. B k-й строке ищем элемент который наиболее отличается в противоположную сторону: A^k_p, в p-м столбце ищем элемент который наиболее отличается так же как и A^k_l: A^q_p. К A^k_l и A^q_p прибавляем(+1 или -1), от A^k_p и A^q_l отнимаем(+1 или -1). За некоторое конечное число таких корректировок сделаем матрицу такой как надо. 

[Alexos]

спасибо за проявленный интерес, алгоритм вроде рабочий. Но нужно доказать конечность алгоритма, т.е. что кол-во итераций не бесконечно. Для этого достаточно доказать, что A^q_l отличается в другую сторону неже ли A^k_l. И что такие элементы для A^k_l существуют (т.е. A^k_p A^q_p A^q_l) с неправильными значениями.
Так то у меня тоже есть алгоритм попроще на уме, но не могу доказать. Если интересно, могу поделиться.

[Крипто]

Если интересно, могу поделиться.

Интересно, делимся)

[Alexos]

Интересно, делимся)

Отнимаем от всех элементов матрицы А целые числа, так, чтобы перевести их в диапазон [0,1), соответственно из сумм строк и столбцов отнимаем суммы отнятых чисел. Получается эквивалентная задача, то есть расстановка округлений в данной задаче совпадает с расстановкой в искомой. Полученную матрицу обозначим Б.
 Теперь нужно понять, где в матрице нужно поставить округления сверху, но на нулях их ставить нельзя. Решение дадим в виде матрицы Х таких же размеров, где ижитый элемент равняется единице, если тот же элемент был округлён сверху в матрице Б.
 Получается, что в матрице Х нужно расставить в каждых строках и столбцах соответствующее число единиц, причем некоторые клетки недопустимые. Помню, что данная задача решена, и есть алгоритм, но не помню какой.