С. Армия одного государства вторглась на остров, заселённый аборигенами. Известно, что остров имеет форму таблицы (2k + 1) × (2k + 1). Может ли эта армия захватить некоторые клетки острова таким образом, чтобы каждая клетка имела ровно две захваченных, соседних с ней по стороне?

Эта задача относится к области математики, конкретно к теории графов и комбинаторике.

Анализ задачи:

• У нас есть квадратное поле размером (2k + 1) × (2k + 1). Общее количество клеток равно (2k + 1)² , что является нечетным числом.
• Каждая захваченная клетка должна иметь ровно две захваченные соседние клетки (по стороне).

Рассмотрим раскраску поля:

Представим поле в виде шахматной доски. Каждая клетка будет либо черной, либо белой. Соседние клетки всегда имеют разный цвет.

Пусть $$N$$ — общее количество клеток. В нашем случае $$N = (2k+1)^2$$.

Количество черных клеток равно количеству белых клеток плюс одна (или минус одна, в зависимости от того, какая клетка в углу). То есть, количество клеток одного цвета будет $$\frac{N+1}{2}$$, а другого — $$\frac{N-1}{2}$$.

Рассуждение:

Если мы захватываем клетки, то каждая захваченная клетка имеет ровно двух захваченных соседей. Давайте посчитаем общее количество «границ» между захваченными клетками.

Пусть $$C$$ — множество захваченных клеток. Для каждой клетки $$c \in C$$, количество ее соседей, также принадлежащих $$C$$, равно 2.

Если мы просуммируем количество соседей для каждой клетки в $$C$$, мы получим $$2 \times |C|$$. При этом каждая внутренняя граница между двумя захваченными клетками будет посчитана дважды (один раз для каждой клетки).

Рассмотрим общее количество клеток, которое является нечетным.

Представим, что мы захватываем клетки. Каждая захваченная клетка «связана» с двумя другими захваченными клетками. Это похоже на построение пути или цикла.

Если мы раскрасим доску в два цвета (черный и белый), как шахматную доску, то:

• Каждая черная клетка граничит с белыми.
• Каждая белая клетка граничит с черными.

Предположим, мы захватили $$x$$ черных клеток и $$y$$ белых клеток. Общее число захваченных клеток $$x+y$$.

Рассмотрим любую захваченную клетку. У нее ровно два захваченных соседа. Эти два соседа обязательно должны быть другого цвета. Например, если клетка черная, ее соседи — белые.

Если мы захватываем клетки, то «границы» между захваченными клетками образуют некий граф. Каждая вершина (захваченная клетка) имеет степень 2.

Граф, где каждая вершина имеет степень 2, является объединением непересекающихся циклов.

Теперь вернемся к раскраске.

Пусть $$N_{черн}$$ — количество черных клеток, $$N_{бел}$$ — количество белых клеток. $$N_{черн} + N_{бел} = (2k+1)^2$$.

Так как $$(2k+1)^2$$ — нечетное число, то $$N_{черн}
eq N_{бел}$$. Например, $$N_{черн} = (2k+1)^2$$ и $$N_{бел} = 0$$, или $$N_{черн} = \frac{(2k+1)^2+1}{2}$$ и $$N_{бел} = \frac{(2k+1)^2-1}{2}$$.

Рассмотрим каждую захваченную черную клетку. Ее два захваченных соседа должны быть белыми.

Рассмотрим каждую захваченную белую клетку. Ее два захваченных соседа должны быть черными.

Пусть $$C_{черн}$$ — число захваченных черных клеток, $$C_{бел}$$ — число захваченных белых клеток. Общее число захваченных клеток $$|C| = C_{черн} + C_{бел}$$.

Количество «границ» между захваченными черными и белыми клетками:

• Каждая из $$C_{черн}$$ клеток имеет 2 захваченных соседа, которые являются белыми. Суммарно это $$2 \times C_{черн}$$ «связей» от черных к белым.
• Каждая из $$C_{бел}$$ клеток имеет 2 захваченных соседа, которые являются черными. Суммарно это $$2 \times C_{бел}$$ «связей» от белых к черным.

Общее количество границ между захваченными черными и белыми клетками, если считать с одной стороны, равно $$2 \times C_{черн}$$ (с точки зрения черных) и $$2 \times C_{бел}$$ (с точки зрения белых). Эти числа должны быть равны, так как каждая граница соединяет одну черную и одну белую клетку.

Следовательно, $$2 \times C_{черн} = 2 \times C_{бел}$$, что означает $$C_{черн} = C_{бел}$$.

Однако, общее количество клеток на доске $$(2k+1)^2$$ нечетно. Это означает, что количество черных и белых клеток на доске различается на 1. Например, если $$(2k+1)^2 = 9$$, то черных может быть 5, а белых 4.

Если $$C_{черн} = C_{бел}$$, то общее количество захваченных клеток $$C_{черн} + C_{бел} = 2 \times C_{черн}$$ является четным числом.

Это противоречит условию, что мы можем захватить клетки таким образом, чтобы каждое захваченное поле имело ровно двух захваченных соседей.

Вывод:

Нет, армия не может захватить клетки таким образом.

Объяснение:

Если мы представим захваченные клетки как вершины графа, а соседние захваченные клетки — как ребра, то каждая вершина должна иметь степень 2. Такой граф состоит из одной или нескольких непересекающихся циклов.

Теперь рассмотрим раскраску поля в два цвета (черный и белый). Так как общее число клеток $$(2k+1)^2$$ нечетно, количество клеток одного цвета отличается от количества клеток другого цвета ровно на 1. Например, на поле $$3 \times 3$$ (9 клеток) будет 5 клеток одного цвета и 4 другого.

Если мы захватываем клетки, и каждая захваченная клетка имеет ровно двух захваченных соседей, то:

• Каждая захваченная черная клетка должна иметь ровно двух захваченных соседей, которые обязательно будут белыми.
• Каждая захваченная белая клетка должна иметь ровно двух захваченных соседей, которые обязательно будут черными.

Это означает, что общее число «границ» между захваченными черными и белыми клетками, посчитанное со стороны черных, равно $$2 \times (\text{количество захваченных черных клеток})$$.

Точно так же, посчитанное со стороны белых, оно равно $$2 \times (\text{количество захваченных белых клеток})$$.

Поскольку каждая такая граница соединяет одну черную и одну белую клетку, эти два числа должны быть равны. Следовательно, количество захваченных черных клеток должно быть равно количеству захваченных белых клеток.

Однако, общее количество захваченных клеток может быть как четным, так и нечетным. Но если количество захваченных черных и белых клеток равно, то их сумма (общее число захваченных клеток) будет четным.

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

Суммарное количество связей между захваченными клетками, посчитанное с каждой клетки, равно $$2 \times (\text{общее количество захваченных клеток})$$.

С другой стороны, рассмотрим количество ребер в графе захваченных клеток. Каждое ребро соединяет клетку одного цвета с клеткой другого цвета.

Если $$C_{черн}$$ — число захваченных черных клеток, и $$C_{бел}$$ — число захваченных белых клеток, и $$C_{черн} = C_{бел}$$. Тогда общее число захваченных клеток $$C_{черн} + C_{бел} = 2 \times C_{черн}$$ (четное число).

А так как на поле $$(2k+1)^2$$ нечетное количество клеток, то $$N_{черн}
eq N_{бел}$$.

Пусть $$X$$ — множество захваченных клеток. По условию, для каждого $$x \in X$$, $$|\text{соседи}(x) \cap X| = 2$$.

Рассмотрим сумму степеней вершин в графе $$(X, E)$$, где $$E$$ — ребра, соединяющие соседние клетки из $$X$$. По условию, все вершины имеют степень 2. Значит, $$|E| = \frac{1}{2} \times \text{сумма степеней} = \frac{1}{2} \times 2 \times |X| = |X|$$.

Это значит, что граф захваченных клеток является объединением циклов, причем длина каждого цикла равна количеству вершин в нем. Общее число вершин $$|X|$$ равно сумме длин этих циклов.

Теперь вернемся к раскраске. Пусть $$X_{черн} = X \cap \text{черные клетки}$$ и $$X_{бел} = X \cap \text{белые клетки}$$.

Ребро в графе $$(X, E)$$ всегда соединяет вершину из $$X_{черн}$$ с вершиной из $$X_{бел}$$.

Сумма степеней вершин из $$X_{черн}$$ равна $$2 \times |X_{черн}|$$. Все эти ребра ведут к вершинам из $$X_{бел}$$.

Сумма степеней вершин из $$X_{бел}$$ равна $$2 \times |X_{бел}|$$. Все эти ребра ведут к вершинам из $$X_{черн}$$.

Следовательно, число ребер, исходящих из $$X_{черн}$$ в $$X_{бел}$$, равно $$2 \times |X_{черн}|$$.

Число ребер, исходящих из $$X_{бел}$$ в $$X_{черн}$$, равно $$2 \times |X_{бел}|$$.

Поскольку это одни и те же ребра, то $$2 \times |X_{черн}| = 2 \times |X_{бел}|$$, что означает $$|X_{черн}| = |X_{бел}|$$.

Если $$|X_{черн}| = |X_{бел}|$$, то общее число захваченных клеток $$|X| = |X_{черн}| + |X_{бел}| = 2 \times |X_{черн}|$$. Это число всегда четное.

Однако, размер поля $$(2k+1) \times (2k+1)$$ нечетен. Если бы мы захватили ВСЕ клетки, то $$|X| = (2k+1)^2$$ (нечетное число), и мы бы получили $$|X_{черн}|
eq |X_{бел}|$$, что противоречит условию $$2 \times |X_{черн}| = 2 \times |X_{бел}|$$.

Даже если мы захватываем не все клетки, условие $$|X_{черн}| = |X_{бел}|$$ остается верным для любого подмножества клеток, удовлетворяющего условию задачи. Это означает, что общее количество захваченных клеток $$|X|$$ всегда должно быть четным.

Но поле имеет нечетное количество клеток. Если мы рассмотрим все клетки поля, то их общее количество нечетно, и количество клеток одного цвета на 1 больше, чем другого. Это делает невозможным выполнение условия $$|X_{черн}| = |X_{бел}|$$ для всего поля.

Если мы захватываем только часть клеток, то $$|X|$$ может быть нечетным, если $$|X_{черн}|
eq |X_{бел}|$$. Но наше рассуждение доказало, что $$|X_{черн}| = |X_{бел}|$$.

Значит, $$|X|$$ всегда четно.

Ответ: Нет