Задача 64372

Темы:    [ Теория графов (прочее) ] [ Принцип Дирихле (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4- Классы: 6,7

Условие

Автор: Калинин Д.А.

Найдите наибольшее число цветов, в которые можно покрасить рёбра куба (каждое ребро одним цветом) так, чтобы для каждой пары цветов нашлись два соседних ребра, покрашенные в эти цвета. Соседними считаются рёбра, имеющие общую вершину.

Решение

  Есть несколько способов раскрасить рёбра куба в шесть цветов с соблюдением условия задачи. Вот один из них:

  Покажем, что больше шести цветов быть не может.
  Предположим, что мы покрасили рёбра куба в семь или более цветов. Поскольку всего у куба 12 рёбер, то должен быть цвет, например, белый, в который покрашено только одно ребро. Для каждого ребра куба есть ровно четыре ребра, соседних с ним. Значит, с белым цветом в паре может быть не больше четырёх цветов, а значит, всего различных цветов не может быть больше пяти. Противоречие.

Ответ

6 цветов.

Источники и прецеденты использования

олимпиада
Название	Московская устная олимпиада для 6-7 классов
год/номер
Номер	6 (2008 год)
Дата	2008-03-16
класс
	1
Класс	6 класс
задача
Номер	6.6