Незнайка связал 6 кукол своей подруги Кнопочки лентами красного и синего цвета так, что от каждой куклы к каждой другой кукле ведет ровно 1 лента. Докажите, что найдутся 3 куклы, связанные лентами одного цвета.

Предыдущий
вопрос Следующий
вопрос

Давайте предположим, что все куклы связаны лентами по кругу, и ни у одной из них нет двух лент одного цвета. Пусть каждая кукла имеет по одной ленте каждого цвета. Рассмотрим, например, куклу А. У нее есть две ленты – красная и синяя. Пусть лента АB красная, тогда лента АС синяя. Если лента ВС синяя, то ленты ВА и СА красные, что противоречит нашему условию. Если лента ВС красная, то ленты ВА и СА синие, что также противоречит условию. Следовательно, все куклы не могут быть связаны таким образом.

Из этого следует, что найдутся три куклы, связанные лентами одного цвета.