Задача 3.
На рисунке изображён план системы дорог некоторого города. В этом городе 8 прямых улиц, а 11 перекрёстков названы латинскими буквами 𝐴, 𝐵, 𝐶, …, 𝐽, 𝐾.
На некоторые три перекрёстка надо поставить по полицейскому так, чтобы на каждой из 8 улиц стоял хотя бы один полицейский. На какие именно три перекрёстка надо поставить полицейских? Достаточно указать хотя бы один подходящий вариант расположения.
Комментарий: Все улицы направлены вдоль прямых линий. Всего 8 улиц:
- Горизонтальные улицы: 𝐴-𝐵-𝐶-𝐷, 𝐸-𝐹-𝐺, 𝐻-𝐼-𝐽-𝐾.
- Вертикальные улицы: 𝐴-𝐸-𝐻, 𝐵-𝐹-𝐼, 𝐷-𝐺-𝐽.
- Наклонные улицы: 𝐻-𝐹-𝐶, 𝐶-𝐺-𝐾.
Ответ на Задачу 3.
Ответ: 𝐵, 𝐺, 𝐻.
Решение:
Подойдёт вариант, если поставить полицейских на перекрёстках 𝐵, 𝐺, 𝐻. Можно показать, что это единственный возможный вариант.
Поскольку вертикальных улиц всего три, и на каждой из них должно быть по полицейскому, то на перекрёстках 𝐶 и 𝐾 полицейских точно нет. Поэтому на перекрёстке 𝐺 точно должен быть полицейский. Тогда на улице 𝐸-𝐹-𝐺 полицейских больше нет (поскольку на улицах 𝐴-𝐵-𝐶-𝐷 и 𝐻-𝐼-𝐽-𝐾 есть хотя бы по одному полицейскому). На улице 𝐶-𝐹-𝐻 должен быть полицейский, и его можно поставить только на перекрёстке 𝐻. Незакрытой остаются улицы 𝐴-𝐵-𝐶-𝐷 и 𝐵-𝐹-𝐼, поэтому третьего полицейского нужно поставить на перекрёстке 𝐵.
