8. Раскраска

Пусть все клетки доски 100 х 100 покрашены в красный и зелёный цвета. Клетка называется гармоничной, если у неё равное количество красных и зелёных соседей. Каково максимально возможное количество гармоничных клеток? (Клетки считаются соседями, если у них имеется общая сторона. В ответе запиши только число без пробелов.) Решение: Клетка имеет максимум 4 соседа (сверху, снизу, слева, справа). Чтобы клетка была гармоничной, у нее должно быть одинаковое количество красных и зеленых соседей. Это возможно, если у клетки 0 красных и 0 зеленых соседей (то есть клетка не имеет соседей), или 1 красный и 1 зеленый, или 2 красных и 2 зеленых. Однако, клетки, находящиеся на краю доски, имеют только 3 соседа, а клетки в углах имеют только 2 соседа. Гармоничными могут быть только клетки, имеющие четное количество соседей. Чтобы максимизировать количество гармоничных клеток, нужно раскрасить доску таким образом, чтобы как можно больше клеток имели четное количество соседей обоих цветов. Это достигается, если раскрасить доску в шахматном порядке. Тогда каждая клетка будет иметь двух соседей одного цвета и двух другого цвета. Рассмотрим доску 2x2. Все 4 клетки гармоничны. Теперь рассмотрим доску 4x4, где клетки чередуются в шахматном порядке. Все клетки гармоничны. Распространим этот принцип на доску 100x100. Если мы раскрасим ее в шахматном порядке, то каждая клетка будет иметь ровно двух соседей каждого цвета. Следовательно, все клетки будут гармоничными. Таким образом, максимальное количество гармоничных клеток равно общему количеству клеток на доске, то есть 100 * 100 = 10000. Ответ: 10000