|
|
 |
Условие
Каждые два из n блоков ЭВМ соединены проводом. Можно ли каждый из этих проводов покрасить в один из n – 1 цветов так, чтобы от каждого блока отходил n – 1 провод разного цвета, если а) n = 6; б) n = 13?
Решение
а) См. задачу 79450.
б) Пусть было использовано m проводов какого-то одного цвета. Тогда число блоков равно 2m: столько концов у всех этих проводов, а каждый конец подсоединен ровно к одному блоку. Но 13 – нечётное число.
Ответ
а) Можно; б) нельзя.
Замечания
Эта задача фактически является задачей о составлении расписания кругового турнира – проводам одного цвета отвечает разбиение участников турнира на пары для одного тура. Как видно из п. б) при нечётных n эта задача неразрешима. Алгоритм составления расписания для чётного n хорошо известен любителям спорта.
