4. На шахматной доске стоят несколько королей. Докажите, что их можно раскрасить в 4 цвета так, чтобы короли одинакового цвета друг друга не били.

Разобьём клетки на четыре группы по чётности номера строки и номера столбца. Каждой группе назначим свой цвет.

Король бьёт клетки, отличающиеся от его клетки на одну строку и/или один столбец. При таком переходе меняется чётность строки или столбца (а при ходе по диагонали — обеих). Значит, король не бьёт клетку того же цвета.

Ответ: достаточно четырёх цветов.