Какое наибольшее число клеток доски 6 на 6 можно покрасить так, чтобы никакие две закрашенные клетки не соприкасались даже в одной точке?

 Разобьём доску на 16 квадратиков 2×2 и покрасим их в разные цвета. Докажем, что больше 16 цветов получить нельзя. Рассмотрим клетку любого цвета. Рядом с ней есть ещё две клетки того же цвета. Эти две клетки имеют только одну соседнюю клетку того же цвета (среди рассмотренных), поэтому есть ещё хотя бы одна клетка такого же цвета. Итак, каждого цвета не меньше четырёх клеток, а следовательно, цветов не больше 16.