ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98603
Темы:    [ Теория алгоритмов (прочее) ]
[ Связность и разложение на связные компоненты ]
[ Внутренность и внешность. Лемма Жордана ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

а) Электрическая схема имеет вид решётки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от любого узла к любому. За какое наименьшее число измерений всегда можно в этом удостовериться?

б) Тот же вопрос для схемы, которая имеет вид решётки 7×7 (всего 64 узла).


Решение

  а) См. задачу 98596 а).

  б) То, что 31 измерения недостаточно доказано в решении задачи 98596.
  Укажем два способа, при которых достаточно 32 измерений.

  Первый способ. Последовательность из 32 измерений строится аналогично решению задачи 98596 б), но требуется уже пять шагов. Узлы, проверяемые в одном измерении, обозначены одинаковыми буквами.
  На пятом шаге проверяем пары оставшихся узлов, симметричные относительно горизонтальной средней линии.
  На первом шаге все проверенные узлы принадлежат одной компоненте благодаря теореме о пересечении ломаных. На следующих трёх шагах линия тока обязана пройти через один из узлов, принадлежащих компоненте, поскольку один из проверяемых узлов оказывается окруженным ранее проверенными узлами.

  Второй способ. "Линия тока"  A–A  соединяет боковые стороны "доски" и по теореме о пересечении ломаных пересекается с линиями  B–B,  C–C,  ...,  H–H.  Таким образом, все узлы, помеченные буквами от A до H, принадлежат одной компоненте.

  Остальные пары проверяемых узлов расположим, как во второй горизонтали: расстояние между узлами одной пары равно 4 (половине ширины доски). Докажем, что все эти узлы (например K) также принадлежат этой компоненте. "Линия тока"  K–K  содержит единичный отрезок, пересекающий вертикальную ось симметрии доски (см. рис.). Если этот отрезок лежит на верхней или нижней горизонтали, то все доказано. В противном случае пусть концы этого отрезка – узлы X и Y. "Парные" к ним узлы находятся на левой и правой сторонах доски. Согласно той же теореме "линия тока"  Y–Y–X–X  (соединяющая боковые стороны доски) пересекает линию  A–A  (которая соединяет вернюю сторону с нижней).


Ответ

а) За 8 измерений;  б) за 32 измерения.

Замечания

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

2. Баллы: 4 + 5.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 7

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .