Є лист паперу в клітинку і олівці 6 кольорів. Зафарбуйте найменше число клітин так, щоб для будь-яких двох кольорів знайшлося дві клітини цих кольорів, що граничать по стороні. Доведіть, що менше число клітин зафарбувати не мож...
Є лист паперу в клітинку і олівці 6 кольорів. Зафарбуйте найменше
число клітин так, щоб для будь-яких двох кольорів знайшлося дві
клітини цих кольорів, що граничать по стороні. Доведіть, що менше
число клітин зафарбувати не можна.
Гость
Ответ(ы) на вопрос:
ГостьРозв’язання. З умови випливає, що існують клітини кожного кольору. Якщо якогось кольору буде тільки одна клітина, то в неї має бути 5 різнокольорових сусідів, що неможливо. Отже, кожного кольору хоча б по дві клітини, а всього - не менше 12 клітин.
Не нашли ответ?
Похожие вопросы