|
|
 |
Условие
а) Электрическая схема имеет вид решетки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от каждого узла к любому другому. За какое наименьшее число измерений всегда можно в этом удостовериться?
б) Тот же вопрос для решётки 5×5 (всего 36 узлов).
Решение
Нетрудно убедиться в том, что если перегорели только провода, выходящие из фиксированного узла, то между любыми двумя другими узлами ток проходит. Поэтому каждый узел должен быть задействован в процессе измерений, то есть число измерений не может быть меньше половины числа узлов (8 в случае а) и 18 в случае б)).
Покажем, что этого числа проверок достаточно. Для этого определенным образом разобьём все узлы на пары (узлы в паре пометим одинаковыми буквами) и для каждой проверим, что ток проходит между узлами этой пары.
а) "Линия тока" A–A (B–B) очевидно пересекается с линиями C–C и D–D (см. шаг 1). Таким образом, все узлы, помеченные буквами от A до D, связаны проводами (принадлежат одной компоненте). Остальные узлы также принадлежат этой компоненте – например линия тока E–E проходит либо через A, либо через C (см. шаг 2).
б) Здесь потребуется три шага (см. рис.).
Замечания
1. Баллы: 5 + 5.
2. Ср. с задачей 98603.
