|
Но шахматной доске 8х8 расставили ладей так, что в каждом столбце и в каждой строке ровно 3 ладьи. Докажите, что можно выбрать 8 ладей так, что никакие две из них не бьют друг друга. задан 10 Ноя '21 13:49 
Faminoz |
|
Это стандартное следствие классической теоремы Ф.Холла о паросочетаниях. Рассмотрим двудольный граф: горизонтали -- "юноши", вертикали -- "девушки". Если на пересечении линий стоит ладья, то юноша и девушка знакомы. Для того, чтобы можно было построить совершенное паросочетание (биекцию между юношами и девушками, то есть составление 8 пар знакомых), необходимо и достаточно, чтобы любые k юношей из восьми были знакомы в совокупности не менее чем с k девушками. Последнее означает, что число девушек, знакомых хотя бы с одним из k юношей, не меньше k. Пусть у выбранных k юношей число в совокупности знакомых с ними девушек равно m. Рассмотрим двудольный граф типа (k,m). Число рёбер, исходящих из первой доли, равно 3k. Оно равно числу рёбер, входящих во вторую долю. Каждая девушка знакома ровно с тремя юношами среди восьми. Поэтому из вершины второй доли идёт не более трёх рёбер в вершины первой доли. Отсюда 3k<=3m, то есть m>=k. отвечен 10 Ноя '21 23:44 
falcao |