Дано:
- Замок имеет вид семиугольника.
- В каждой вершине находится сторожевая башня.
- Каждую из семи стен замка охраняют стражники в башнях, находящихся в концах этой стены.
- Каждая стена должна быть охраняема не менее чем семью стражниками.
Найти:
- Наименьшее количество стражников, которые нужно разместить в башнях, чтобы каждая стена была охраняема не менее чем семью стражниками.
Решение:
1. Обозначим количество стражников в вершинах семиугольника как a1, a2, a3, a4, a5, a6, a7.
- Вершины связаны следующими стенами: (a1, a2), (a2, a3), (a3, a4), (a4, a5), (a5, a6), (a6, a7), (a7, a1).
2. Для каждой стены сумма стражников в её концах должна быть не менее 7:
a1 + a2 ≥ 7
a2 + a3 ≥ 7
a3 + a4 ≥ 7
a4 + a5 ≥ 7
a5 + a6 ≥ 7
a6 + a7 ≥ 7
a7 + a1 ≥ 7
3. Сложим все эти неравенства:
(a1 + a2) + (a2 + a3) + (a3 + a4) + (a4 + a5) + (a5 + a6) + (a6 + a7) + (a7 + a1) ≥ 7 * 7
2(a1 + a2 + a3 + a4 + a5 + a6 + a7) ≥ 49
a1 + a2 + a3 + a4 + a5 + a6 + a7 ≥ 24.5
4. Поскольку количество стражников должно быть целым числом, минимальное возможное значение – 25.
5. Проверим, можно ли разместить 25 стражников так, чтобы все условия были выполнены:
Если каждый вершине назначить по 4 стражника, то
- a1 = 4
- a2 = 4
- a3 = 4
- a4 = 4
- a5 = 4
- a6 = 4
- a7 = 1
Проверим каждую стену:
- (a1, a2) = 4 + 4 = 8 ≥ 7
- (a2, a3) = 4 + 4 = 8 ≥ 7
- (a3, a4) = 4 + 4 = 8 ≥ 7
- (a4, a5) = 4 + 4 = 8 ≥ 7
- (a5, a6) = 4 + 4 = 8 ≥ 7
- (a6, a7) = 4 + 1 = 5 < 7 (такое распределение не подходит)
Нужно скорректировать распределение, чтобы сумма в каждой паре была не менее 7. Например, можно попробовать:
- a1 = 3
- a2 = 5
- a3 = 4
- a4 = 4
- a5 = 5
- a6 = 4
- a7 = 4
Тогда все условия выполняются:
- (a1, a2) = 3 + 5 = 8 ≥ 7
- (a2, a3) = 5 + 4 = 9 ≥ 7
- (a3, a4) = 4 + 4 = 8 ≥ 7
- (a4, a5) = 4 + 5 = 9 ≥ 7
- (a5, a6) = 5 + 4 = 9 ≥ 7
- (a6, a7) = 4 + 4 = 8 ≥ 7
- (a7, a1) = 4 + 3 = 7 ≥ 7
Ответ:
Наименьшее количество стражников, которое нужно разместить в башнях, чтобы каждая стена была охраняема не менее чем семью стражниками, равно 25.