Разделы 
Дополнительно
Задача по математике - 3633
2019-06-13 
Город имеет в плане вид прямоугольника, разбитого на клетки: $n$ улиц параллельны друг другу, $m$ других пересекают их под прямым углом. На улицах города - но не на перекрестках - стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?
Решение:
.
Если милиционеры расставлены требуемым в условии образом, то вся сетка улиц распадается на какое-то число $k$ кусков, не содержащих замкнутых маршрутов (циклов), - иначе найдется цикл, по которому можно проехать, не будучи замеченным ни одним из милиционеров. Если оставшийся кусок сетка содержит $p$ перекрестков, то в нем содержится ровно $p - 1$ отрезков улиц. Так как перекрестков всего $m \cdot n$, то число отрезков, на которых нет милиционеров, равно $mn - к$. Общее число отрезков улиц равно $2mn - m - n$. Таким образом, число занятых отрезков равно
$mn - m - n + k \geq (m - 1) (n - 1)$.
Пример нужной расстановки $(m - 1 )(n - 1)$ милиционеров показан на рис.
Ответ: наименьшее число милиционеров равно $(m - 1) (n - 1)$.
Город имеет в плане вид прямоугольника, разбитого на клетки: $n$ улиц параллельны друг другу, $m$ других пересекают их под прямым углом. На улицах города - но не на перекрестках - стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?
Решение:
.
Если милиционеры расставлены требуемым в условии образом, то вся сетка улиц распадается на какое-то число $k$ кусков, не содержащих замкнутых маршрутов (циклов), - иначе найдется цикл, по которому можно проехать, не будучи замеченным ни одним из милиционеров. Если оставшийся кусок сетка содержит $p$ перекрестков, то в нем содержится ровно $p - 1$ отрезков улиц. Так как перекрестков всего $m \cdot n$, то число отрезков, на которых нет милиционеров, равно $mn - к$. Общее число отрезков улиц равно $2mn - m - n$. Таким образом, число занятых отрезков равно
$mn - m - n + k \geq (m - 1) (n - 1)$.
Пример нужной расстановки $(m - 1 )(n - 1)$ милиционеров показан на рис.
Ответ: наименьшее число милиционеров равно $(m - 1) (n - 1)$.
