Есть лист клетчатой бумаги и карандаши 6 цветов. Закрасьте наименьшее число клеток так, чтобы для любых двух цветов нашлись две клетки этих цветов, граничащие по стороне. Докажите, что меньшее число клеток закрасить нельзя.

Наименьшее число клеток — 19. Пример раскраски (цвета обозначены цифрами 1–6, пустые клетки не закрашены):

Доказательство, что меньшим числом клеток обойтись нельзя. Пусть закрашено \( N \) клеток. Разобьём их на чёрные и белые по шахматной раскраске. Каждый цвет обязан присутствовать и на чёрных, и на белых клетках (иначе два цвета, оказавшиеся только на клетках одного цвета, не смогут граничить). Поэтому чёрных клеток не менее 6, белых — не менее 6, и \( N \ge 12 \).

Предположим, \( N \le 18 \). Тогда на одной из сторон (чёрной или белой) не более 9 клеток. Если на этой стороне ровно 6 клеток, то каждая из них обязана граничить с клетками пяти других цветов на противоположной стороне, что требует степени не менее 5 — невозможно, так как у клетки не более четырёх соседей. Если на стороне 7, 8 или 9 клеток, то по принципу Дирихле хотя бы один цвет представлен на этой стороне ровно одной клеткой. Эта клетка должна соседствовать с клетками всех остальных пяти цветов на другой стороне, что опять требует пяти соседей. Противоречие. Следовательно, \( N \ge 19 \).

0 0 Пожаловаться