Страница 53 номер 81, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
На клетчатом листе закрасили 25 клеток. Может ли каждая из них иметь нечётное число закрашенных соседних клеток?
Сопоставим каждой закрашенной клетке вершину; ребро соединяет две вершины, если соответствующие клетки соседние. В графе 25 вершин, и степень вершины равна числу закрашенных клеток, соседних с данной.
Предположим, что у каждой из 25 закрашенных клеток число закрашенных соседей нечётно. Тогда вершин нечётной степени в графе ровно 25.
Но число вершин нечётной степени в любом графе чётно: сумма степеней всех вершин равна удвоенному числу рёбер и потому чётна, вершины чётной степени дают в неё чётный вклад, значит, сумма степеней вершин нечётной степени тоже чётна, а сумма нечётных чисел чётна только при чётном числе слагаемых.
Число 25 нечётно — получилось противоречие.
Ответ: нет, не может: тогда в графе, где вершины отвечают закрашенным клеткам, а ребро соединяет соседние клетки, было бы 25 вершин нечётной степени, а их число всегда чётно.
На клетчатом листе закрасили 25 клеток. Может ли каждая из них иметь нечётное число закрашенных соседних клеток?
Сопоставим каждой закрашенной клетке вершину; ребро соединяет две вершины, если соответствующие клетки соседние. В этом графе 25 вершин, и степень каждой вершины равна числу закрашенных клеток, соседних с данной клеткой.
Предположим, что каждая из 25 закрашенных клеток имеет нечётное число закрашенных соседей. Тогда степень каждой из 25 вершин нечётна, то есть вершин нечётной степени в графе ровно 25.
Но число вершин нечётной степени в любом графе чётно. Действительно, сумма степеней всех вершин равна удвоенному числу рёбер и потому чётна. Вершины чётной степени дают в этой сумме чётный вклад, значит, сумма степеней вершин нечётной степени тоже чётна, а сумма нечётных чисел чётна только тогда, когда слагаемых чётное число.
Число 25 нечётно — получилось противоречие.
Ответ: нет, не может: тогда в графе, где вершины отвечают закрашенным клеткам, а ребро соединяет соседние клетки, было бы 25 вершин нечётной степени, а их число всегда чётно.
