Задача со сборов клетки

В клетки таблицы n×n записали неотрицательные действительные числа так, что сумма чисел в каждой строке и каждом столбце равна 1. Докажите, что можно выбрать n клеток доски так, что никакие две клетки не стоят ни в одном столбце, ни в одной строке, а все числа, записанные в этих клетках положительные.

Можете дать подсказку вместо полного решения?

2 симпатии

Попытайся перевести задачу в граф

4 симпатии

Можно без графов:

Найди метод посчитать количество таких правильных наборов n клеток и общую сумму сумм чисел в клетках этих наборов.

5 симпатий
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)