Глава 4. Расстояние в «клетчатом» городе

   С понятием расстояния мы сталкиваемся ежедневно. «Каково расстояние от дома до школы?», «Сколько километров от Москвы до Петербурга?» - эти вопросы никого не удивят. Зная расстояние, мы можем прикинуть, долго ли добираться от одного места до другого. Все мы умеем вычислять расстояние между двумя точками на координатной прямой, с помощью теоремы Пифагора мы можем вычислить расстояние между двумя точками на координатной плоскости.

   А теперь возьмём хорошо знакомый нам листок клетчатой бумаги и представим себе, что это – город, линии сетки – улицы. Давайте прогуляемся по этому городу, ходя только по улицам (порядки в этом городе очень строгие). Длину клетки будем считать равной 1. Как нам быстрее всего попасть с перекрёстка А на перекрёсток Б (рис. 1)?

Можно, например, пройти из А в С, а потом – из С в В. Можно было идти через D, а можно – и более замысловатым путём. Что же мы теперь назовём расстоянием от А до В? Конечно, длину кратчайшего

      Рис. 1    пути: 4 + 3 = 7.

   А теперь представим себе, что у нас в запасе есть время проделать путь длиной 3. В каких узлах мы можем побывать, выйдя из А? (Или: из каких узлов можно добраться до А, пройдя путь не более 3?) Ответ на этот вопрос изображён на рисунке 2). Наверное, многие из вас сейчас вспомнили о круге на плоскости: ведь круг радиуса r с центром в точке А и есть множество всех точек плоскости, которые удалены от А не больше, чем на r. Но как не похож ромбик из точек с рисунка 2 на привычный круг!                Рис. 2

Познакомимся поближе с расстоянием в «клетчатом» городе с помощью нескольких задач.

Задача 1. [11] В «клетчатом» городе выделили район – квадрат 4´4. Какое

Наименьшее количество детских площадок нужно построить в этом районе, чтобы из любого узла этого района можно было попасть на одну из этих площадок, проделав путь не более 3?

Решение. Понятно, что двух площадок хватает (рис. 3). Ещё легче понять, что одной площадки будет мало (слишком далеко разбросаны узлы, находящиеся на границе квадрата!)

   Рис. 3

Решите такую же задачу с прямоугольником 6´3. А как решается подобная задача, если расстояние на плоскости измеряется обычным способом?

Задача 2. Какое наибольшее количество котов можно разместить в узлах сетки на территории квадрата 4´4, чтобы расстояние между любыми двумя из них было не менее 2 (иначе коты подерутся)?

Наверное, без особого труда сумеете поделить территорию квадрата между 13 котами (рис. 4). А вот                Рис. 4

14 котов мирно ужиться на этой территории уже не смогут. Докажем это. Поделим всю территорию, кроме центра квадрата, на 4 непересекающиеся зоны (рис. 5). Если даже одного из 14 котов поселить в центре квадрата, то остальных 13 придётся разместить по этим зонам. Значит, в какой-то зоне окажется хотя бы 4 кота. Перебирая различные варианты расселения 4 котов в

 Рис. 5         какой-нибудь из этих зон, легко увидеть, что это невозможно.

Подумайте, как решить эту задачу, если расстояние на плоскости измеряется, как обычно.

Итак, мы познакомились с расстоянием в «клетчатом» городе. Оно ни чуть не менее естественно, чем обычное расстояние «по прямой». Что их объединяет? Каковы общие свойства, которыми должно обладать расстояние?

Свойство 1. Расстояние между двумя точками неотрицательно, причём оно равно нулю, только если точки совпадают.

Ещё бы! Чтобы попасть из точки А в неё же, никуда идти не надо, а чтобы попасть в другую точку В, придётся проделать некий путь положительной длины.

Свойство 2. Расстояние от точки А до точки В равно расстоянию от точки В до точки А.

Недаром мы говорим обычно не о расстоянии от А до В, а о расстоянии между А и В, не различая расстояния от А до В и от В до А.

Свойство 3. Для точек А, В и С сумма расстояний от А до С и от С до В не меньше расстояния от А до В (неравенство треугольника).

Свойства 1, 2 и 3 в математике называются аксиомами расстояния. Как мы знаем, эти свойства есть у обычного расстояния на плоскости. Не трудно проверить, что есть они и у нового расстояния, введённого нами в «клетчатом» городе.