В коробке 25 цветных карандашей. Известно, что среди любых пяти карандашей найдутся хотя бы 2 карандаша одного цвета. Докажите, что в коробке найдется 7 карандашей одного цвета.
В коробке 25 цветных карандашей. Известно, что среди любых пяти карандашей найдутся хотя бы 2 карандаша одного цвета. Докажите, что в коробке найдется 7 карандашей одного цвета.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Допустим противное, то есть в коробке нет 7 карандашей одного цвета. Это значит, что в коробке есть не менее 6 карандашей каждого из 25 цветов.
Посмотрим на количество карандашей в коробке, описываемое так называемым графом ребер, в котором вершины соответствуют карандашам, а ребра соединяют вершины, если соответствующие карандаши одного цвета. Мы знаем, что каждая вершина этого графа имеет степень не меньше 6, а также что в графе не может быть подграфа из 5 вершин, все степени которых равны 6. Однако такой граф невозможно построить без такого подграфа, так как количество вершин делится на 5. Получаем противоречие, исходное предположение было неверным. Значит, в коробке найдется 7 карандашей одного цвета.