Какое наименьшее количество клеток нужно отметить на клетчатой доске 8x11, чтобы 1) среди отмеченных...

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

1. Подход с окрашиванием в два цвета: Рассмотрим клетчатую доску 8x11. Можно окрасить доску в два цвета (например, черный и белый) по принципу шахматной доски, где каждая клетка чередуется по цвету с соседними по стороне. В такой раскраске каждая клетка имеет восемь соседей: четыре по сторонам и четыре по углам. Все соседи каждой клетки будут другого цвета.

2. Расчет количества каждого цвета: На доске 8x11 всего 88 клеток. Так как раскраска альтернативная и начинается с любого цвета, клеток одного цвета будет 44, а другого – 44 (при условии, что доска начинается с клетки определённого цвета и заканчивается клеткой другого цвета по диагонали).

3. Выбор цвета для отметки: Выберем для отметки все клетки одного из цветов (например, черного). Тогда все 44 черные клетки будут отмечены. Это гарантирует, что никакие две отмеченные клетки не будут соседними, так как все соседи черных клеток – белые.

4. Проверка добавления новой клетки: Поскольку все клетки одного цвета уже отмечены, добавление любой новой клетки (которая будет белой) нарушит условие, так как у каждой белой клетки есть по крайней мере один черный сосед.

Таким образом, минимальное количество клеток, которое нужно отметить, чтобы выполнить оба условия задачи, равно 44. Это количество клеток одного цвета на доске 8x11, окрашенной по шахматному принципу.

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

Для доски 8x11 имеем 88 клеток. Посчитаем количество клеток в максимальном независимом множестве. Обозначим вершины графа как клетки доски:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

Максимальное независимое множество можно выбрать следующим образом: 1, 13, 25, 37, 49, 61, 73, 85, 2, 14, 26, 38, 50, 62, 74, 86, 3, 15, 27, 39, 51, 63, 75, 87, 4, 16, 28, 40, 52, 64, 76, 88.

Таким образом, наименьшее количество клеток, которое нужно отметить на клетчатой доске 8x11, чтобы среди отмеченных клеток не было соседних, равно 32. Добавление к этим клеткам любой одной клетки нарушит пункт 1, так как все клетки уже будут соседними с отмеченными.

Для выполнения условий задачи нужно отметить 20 клеток на доске 8x11.