|
Докажите, что матрицу из $%\{0,1\}^{n×n}$%, в каждой строке и столбце которой ровно $%k$% единиц, можно представить в виде суммы $%k$% матриц, в каждой строке и столбце у которых в точности по одной единице. задан 12 Май '20 13:04 
Nakahika |
|
Это одно из стандартных следствий теоремы Холла о паросочетаниях. Введём более удобную терминологию. Строки -- "юноши", столбцы -- "девушки". Если на пересечении строки и столбца стоит 1, то юноша и девушка знакомы. Проверим выполнение условия теоремы. Берём любых s юношей (1<=s<=n). Смотрим, со сколькими девушками они знакомы с совокупности (то есть сколько девушек знает хотя бы одного из них). У каждого юноши ровно k знакомых девушек. Он даёт их список. В итоге имеем список из sk пунктов с повторениями. Одну и ту же девушку могли упомянуть не более k раз, так как это могли сделать только её знакомые, а их всего k, и среди взятых s юношей их не более k. Поэтому в списке длиной sk с повторениями упоминается не менее s различных девушек. Итак, условие теоремы выполнено. Значит, существует совершенное паросочетание: каждому юноше сопоставляем знакомую ему девушку, и разным юношам соответствуют разные девушки. В матрице получаем набор из n единиц, стоящих в разных строках и столбцах. Вычитаем такую матрицу, и получаем ту же задачу с числом k-1 вместо k. Далее -- индукция. В итоге получаем сумму k матриц нужного нам вида. отвечен 12 Май '20 19:49 
falcao |
Ой, мне тоже нужна будет эта задача. Когда вам ответят, отпишитесь пожалуйста, чтоб я не забыл
@rumotameru,