2-я олимпиада им. Шалтая Смагулова, 7 класс, 2 тур, 2017 г.


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

Комментарий/решение:

  2
2022-05-05 18:12:50.0 #

2, так как максимум могло выйти от телефона 2 провода

  1
2022-05-07 13:51:16.0 #

и не имеет разницы, какого цвета провод соединит этот же телефон с другим

  0
2022-05-12 01:20:38.0 #

не, попробуй просто взять 3 телефона. в конце выйдет что у одного из них оба провода одного цвета