Question

Клетки доски 4×4 закрасили в три цвета. Известно что каждый клетки есть соседи двух других цветов докажите что клеток каждого цвета не меньше 4

Answer 1

Ответ: ниже.

Пошаговое объяснение:

Рассмотрим уголки таблицы. В угловой клетке, клетке ниже\выше и клетке справа\слева (эти клетки образуют уголок) имеются представители трёх цветов, ведь у угловой клетки всего 2 соседа; а значит, они разных цветов. В таблице могут уместиться 4 таких уголка => по 4 клетки каждого цвета есть.

Answer 2

Давайте докажем это утверждение от противного. Предположим, что клеток одного из цветов меньше 4. Для определенности, допустим, что у нас есть только 3 клетки одного из цветов. Другие два цвета обозначим как A и B.

Поскольку каждая клетка имеет двух соседей других цветов, то клетки цвета A и B также должны иметь по два соседа других цветов. Представим, что у нас есть две клетки цвета A, которые имеют общего соседа цвета B (иначе бы клетка цвета B оказалась бы рядом с клеткой цвета B и клетка цвета A была бы рядом с клеткой цвета A, что невозможно, так как они одного цвета).

Теперь мы имеем две клетки цвета A, которые имеют общего соседа цвета B, и еще одну клетку цвета A, которая не имеет общих соседей с клеткой цвета B. Это возможно только в случае, если эти три клетки цвета A образуют линейку, где одна из клеток A находится между двумя другими клетками A. Такая ситуация изображена ниже (где A обозначает клетку цвета A, B - клетку цвета B):

A - A - B - A

Однако, согласно условию, каждая клетка имеет двух соседей других цветов. В данной ситуации клетка цвета B имеет только одного соседа цвета A. Это противоречит условию, и поэтому невозможно, чтобы клеток одного из цветов было меньше 4. Таким образом, мы доказали, что клеток каждого цвета не меньше 4.