Контрольные задания > 7 20 телефонов соединены проводами так, что каждый провод соединяет два телефона, каждая пара телефонов со- единена не более чем одним проводом и от каждого телефо- на отходит не более двух проводов. Нужно раскрасить про- вода (каждый провод целиком одной краской) так, чтобы от каждого телефона отходили провода разных цветов. Какого наименьшего числа красок достаточно для такой раскраски?
Вопрос:

7 20 телефонов соединены проводами так, что каждый провод соединяет два телефона, каждая пара телефонов со- единена не более чем одним проводом и от каждого телефо- на отходит не более двух проводов. Нужно раскрасить про- вода (каждый провод целиком одной краской) так, чтобы от каждого телефона отходили провода разных цветов. Какого наименьшего числа красок достаточно для такой раскраски?

Смотреть решения всех заданий с листа

Ответ:

Ответ: 2

Краткое пояснение: Для раскраски проводов достаточно двух цветов, так как от каждого телефона отходит не более двух проводов.

Пошаговое решение:

  • Представим себе телефонную сеть, где 20 телефонов соединены проводами. Каждый провод соединяет два телефона, и от каждого телефона отходит не более двух проводов.

  • Чтобы провода, отходящие от каждого телефона, были разных цветов, нам нужно минимум два цвета. Первый провод можно покрасить в один цвет, а второй - в другой.

  • Если от какого-то телефона отходит только один провод, то для него достаточно одного цвета.

  • Но если от телефона отходят два провода, то они должны быть разного цвета. Следовательно, нам нужно два цвета.

Ответ: 2

ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие