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