Question

На рисунке изображён план системы дорог некоторого города. В этом городе 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

Answer 1

Ответ:

Чтобы на каждой из 8 улиц стоял хотя бы один полицейский, их нужно ставить на перекрёстках C, K и Е.

Пошаговое объяснение:

Для начала определим, на каких перекрёстках выгоднее всего ставить полицейских.

Так как нам нужно, чтобы один полицейский стоял на как можно большем кол-ве улиц, записываем перекрёстки, через которые проходит одновременно три улицы. Это перекрёстки Е, В, К и F. Начинаем рассматривать различные варианты.

Поставим полицейского на перекрёстке F.

Теперь нам нужно ставить полицейского на перекрёстках D, G либо K, чтобы кто-то был на улице DK.  

1. На перекрёстке G делать это смысла нету, так как тогда на одной из улиц будет сразу два полицейских.
2. Если мы ставим полицейского на перекрёстке D, нам нужно поставить последнего полицейского так, чтобы он одновременно стоял на улицах НК, НВ и AI, а это невозможно, так как они не пересекаются в одной точке.
3. Если мы ставим полицейского на перекрёстке K, нам нужно поставить последнего полицейского так, чтобы он одновременно стоял на улицах НК, AD и AI, это невозможно, так как они не пересекаются в одной точке.

Мы пришли к тому, что на перекрёстке F полицейский стоять не может.

Поставим полицейского на перекрёстке B.

Теперь нам, опять же, нужно ставить полицейского на перекрёстках D, G либо K, чтобы кто-то был на улице DK.

1. На перекрёстке К либо D делать это смысла нету, так как тогда на одной из улиц будет сразу два полицейских.
2. Если мы ставим полицейского на перекрёстке G, последнего полицейского мы должны поставить так, чтобы он был на улицах AI, CJ и HK одновременно, это невозможно, потому что улицы AI и CJ не пересекаются.

Мы пришли к тому, что в на перекрёстке В полицейский стоять не может.

Поставим полицейского на перекрёстке Е.

Теперь нам нужно ставить полицейского на перекрёстках D, G либо K, чтобы кто-то был на улице DK.

1. На перекрёстке G делать это смысла нету, так как тогда на одной из улиц будет сразу два полицейских.
2. Если мы ставим полицейского на перекрёстке D, нам нужно поставить последнего полицейского так, чтобы он одновременно стоял на улицах ВК, CJ и НК. Это невозможно, т.к. они не пересекаются в одной точке.

Ставим полицейского на перекрёстке К. Теперь нам нужно поставить последнего полицейского так, чтобы он стоял одновременно на улицах AD и CJ. Эти улицы пересекаются в точке С, туда и ставим полицейского. Теперь 3 полицейских стоят на каждой из 8 улиц.

В прикреплённом файле наглядно изображено решение. Полицейский К стоит на улицах, подкрашенных красным цветом; полицейский Е - зелёным цветом; полицейский С - фиолетовым цветом. Соответственно, полицейских нужно ставить на перекрёстках C, K и Е.

#SPJ3