На рисунке изображён план системы дорог некоторого города. В этом городе 8 прямых улиц, а 11 перекрёстков названы латинскими буквами A,B,C,…,J,K.

На некоторые три перекрёстка надо поставить по полицейскому так, чтобы на каждой из 8 улиц стоял хотя бы один полицейский. На какие именно три перекрёстка надо поставить полицейских? Достаточно указать хотя бы один подходящий вариант расположения.

Все улицы направлены вдоль прямых линий.

Горизонтальные улицы: A−B−C−D, E−F−G, H−I−J−K.

Вертикальные улицы: A−E−I, C−F−J, D−G−K.

Наклонные улицы: B−F−K, B−E−H.

Перекрёсток A
Перекрёсток B
Перекрёсток C
Перекрёсток D
Перекрёсток E
Перекрёсток F
Перекрёсток G
Перекрёсток H
Перекрёсток I
Перекрёсток J
Перекрёсток K

Один подходящий вариант: поставить полицейских на перекрёстках B, G, I.

Проверим, что каждая улица содержит хотя бы одного полицейского:

• A−B−C−D — есть полицейский на B;
• E−F−G — есть полицейский на G;
• H−I−J−K — есть полицейский на I;
• A−E−I — есть полицейский на I;
• C−F−J — здесь в варианте B, G, I полицейского нет.

Значит, этот вариант не подходит. Подходящий вариант: E, J, D тоже не покрывает наклонную улицу B−F−K.

Подходящий вариант расположения: E, F, K.

• A−B−C−D — эта улица не покрыта, значит вариант тоже не подходит.

Для данных улиц тремя перекрёстками покрыть все 8 улиц нельзя: чтобы покрыть три горизонтальные улицы, нужно взять хотя бы по одному перекрёстку с каждой из них. После этого ещё нужно покрыть три вертикальные и две наклонные улицы. При перечисленных пересечениях ни один набор из трёх точек не покрывает все 8 улиц.

0 0 Пожаловаться