Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  2
2 года 11 месяца назад #

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

  1
2 года 11 месяца назад #

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

  0
2 года 11 месяца назад #

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

  2
1 года 9 месяца назад #

Ответ : 3 краски

Решение : Если будет нечетное кол-во телефонов, то кол-во проводов также будет нечетным. А если телефонов четно, тоти проводов четно. Представим что 2 это минимальное, а не 3.

Тогда когда будет нечетное кол-во, то 2 не будет выполняется, потому что с одного телефона выйдут провода одинаковой краски. А это противоречие. А если проверить 3, то оно везде рабочее. Значит 3 - минимаельное.

  0
1 года 1 месяца назад #

у меня есть контр пример

  0
1 года 1 месяца назад #

ответ 2

пример для 2: у нас есть 4 телефона и каждая имеет два выхода разных цветов

допустим 1, тогда так как n не меньше 3, из хотябы одного теелфона будет выходит два различных провода. Противоречие

  0
10 месяца 1 дней назад #

Ответ: 3. Если цветов меньше 3. Очевидно, что в 1 цвет покрасть не можем, т.к возможно найдется точка у которой степень вершины 2. Если 2 цвета, то контрпример это цикличный граф с нечетным количеством вершин. Как строется пример для 3. Ну допустим у нас есть 2 разновидности графа, то есть путь и цикл. Путь можно в любом случае раскрасить в 2 цвета и цикл с четным количеством вершин. Теперь осталось посмотреть случай, когда в цикле нечетное количество вершин. Тогда если красить в 2 цвета, то получим, что с какой-то вершины выйдут 2 одинаковых цвета. Просто берем и красим любое из этих 2 ребер в 3-тий цвет.