Разделы 
Дополнительно
Задача по математике - 2013
2019-01-23 
В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырех цветов. Известно, что провода всех четырех цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?
Решение:
Построим граф, вершины которого соответствуют телефонам, а ребра - проводам. Рассмотрим наименьший набор вершин данного графа такой, что среди соединяющих эти вершины ребер присутствуют ребра всех четырех цветов. Удалим из этого набора произвольную вершину. Поскольку набор был наименьший, среди ребер, соединяющих оставшиеся вершины, присутствуют уже не все цвета. Если среди этих ребер присутствуют ребра ровно трех цветов, то искомый набор найден. В противном случае среди ребер, выходящих из удаленной вершины в другие вершины нашего набора, присутствуют как минимум два цвета, которые исчезнут после удаления этой вершины. Рассмотрим два ребра этих цветов, выходящие из удаленной вершины в другие вершины набора. Тогда ребро, соединяющее их концы, должно иметь цвет, отличный от цветов этих двух ребер. Таким образом, в графе нашелся треугольник, все ребра которого имеют попарно различные цвета. Это означает, что требуемый набор вершин можно выбрать всегда.
Ответ. Всегда.
В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырех цветов. Известно, что провода всех четырех цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?
Решение:
Построим граф, вершины которого соответствуют телефонам, а ребра - проводам. Рассмотрим наименьший набор вершин данного графа такой, что среди соединяющих эти вершины ребер присутствуют ребра всех четырех цветов. Удалим из этого набора произвольную вершину. Поскольку набор был наименьший, среди ребер, соединяющих оставшиеся вершины, присутствуют уже не все цвета. Если среди этих ребер присутствуют ребра ровно трех цветов, то искомый набор найден. В противном случае среди ребер, выходящих из удаленной вершины в другие вершины нашего набора, присутствуют как минимум два цвета, которые исчезнут после удаления этой вершины. Рассмотрим два ребра этих цветов, выходящие из удаленной вершины в другие вершины набора. Тогда ребро, соединяющее их концы, должно иметь цвет, отличный от цветов этих двух ребер. Таким образом, в графе нашелся треугольник, все ребра которого имеют попарно различные цвета. Это означает, что требуемый набор вершин можно выбрать всегда.
Ответ. Всегда.
