Question

У короля есть прямоугольный остров, разбитый на несколько прямоугольных участков, принадлежащих феодалам. В ответ на заданный каждому вопрос «сколько у Вас соседей?» было дано ровно два вида ответов: «три» и «семь» (участки соседние, если у них есть общий отрезок границы). При каком наименьшем количестве участков такое возможно? Не забудьте обосновать свой ответ.

Answer 1

.........................................

Answer 2

Для ответа на данный вопрос можно использовать графовую модель.

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

У нас есть два вида ответов: "три" и "семь". Это значит, что каждый участок может иметь либо 3, либо 7 соседей.

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

При этом, чтобы минимизировать количество участков, нам необходимо найти такой граф, который будет содержать минимальное количество вершин.

Такой граф может быть получен путем соединения вершин в виде цепочки, где каждая вершина имеет степень 3, а затем добавлением вершин в виде цепочек, где каждая вершина имеет степень 7.

Таким образом, наименьшее количество участков, удовлетворяющих условию, будет равно количеству вершин в графе, построенном таким образом.

Так, для получения минимального количества участков, удовлетворяющих условию, необходимо построить граф, в котором каждая вершина имеет степень 3 или 7. В таком графе наименьшее количество участков будет равно количеству вершин.

Answer 3

Для того чтобы ответить на данный вопрос, рассмотрим два случая:

1) Когда все участки имеют по три соседа. В этом случае каждый участок должен иметь по три соседа, что значит, что каждый участок должен иметь по две общих границы с другими участками. Таким образом, каждый участок будет иметь две общих границы с соседними участками, а количество таких границ будет равно количеству участков. Если обозначить количество участков как N, то количество общих границ будет равно 2N. Следовательно, для того чтобы каждый участок имел по три соседа, должно выполняться равенство 2N = 3N. Решая это уравнение, получаем N = 0. Отсюда следует, что такое распределение невозможно при любом количестве участков, так как невозможно иметь 0 участков.

2) Когда все участки имеют по семь соседей. В этом случае каждый участок должен иметь по семь соседей, что значит, что каждый участок должен иметь по шесть общих границ с другими участками. Таким образом, каждый участок будет иметь шесть общих границ с соседними участками, а количество таких границ будет равно количеству участков. Если обозначить количество участков как N, то количество общих границ будет равно 6N. Следовательно, для того чтобы каждый участок имел по семь соседей, должно выполняться равенство 6N = 7N. Решая это уравнение, получаем N = 0. Отсюда следует, что такое распределение невозможно при любом количестве участков, так как невозможно иметь 0 участков.

Итак, при наименьшем количестве участков такое распределение невозможно.