Є лист паперу в клітинку і олівці 6 кольорів. Зафарбуйте найменше 

число клітин так, щоб для будь-яких двох кольорів знайшлося дві 

клітини цих кольорів, що граничать по стороні. Доведіть, що менше 

число клітин зафарбувати не можна. 

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