Назовем натуральное число "замечательным", если оно самое маленькое среди натуральных чисел с такой же, как у него, суммой цифр. Чему равна сумма цифр две тысячи первого замечательного числа?

   Решение

Темы:    [ Степень вершины ] [ Четность и нечетность ]

Сложность: 2+ Классы: 6,7

Прислать комментарий

Условие

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён ровно с пятью другими?

Решение

Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а рёбра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна 5. Подсчитаем количество рёбер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчёте каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число рёбер графа должно быть равно  15·5 : 2.  Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.

Источники и прецеденты использования