Всякий раз, когда большинство голосов было за очередное переселение, Джек оставался на новом Месте, а если большинство голосов было против, возвращался на старое. Наконец, он достиг точки, из которой нельзя было переместиться ни в одну сторону, чтобы девушки не проголосовали против. Там он и решил поселиться.

К его радости, квартирная плата в выбранном месте была ему по карману. Но через неделю Банни переехала на новую квартиру в 7 кварталах от своего прежнего дома.

Джек. Жаль, но придется переезжать на новую квартиру.

Но когда Джек достал план города, то, к своему удивлению, обнаружил, что может оставаться на месте.

Как это может быть?

Если Банни переедет на 7 кварталов к востоку от того места, где жила раньше, то ее переезд никак не скажется на выборе резиденции Джека. Более того, Банни могла бы переехать сколь угодно далеко на восток, и место, выбранное для своей квартиры Джеком, по-прежнему оставалось бы оптимальным.

Эффективность алгоритма с голосованием вы сможете лучше оценить, применив к более обширной территории с прямоугольной планировкой, на которой отмечено более трех точек. Вы обнаружите, что алгоритм Джека позволяет быстро находить положение точки x, сумма расстояний от которой до всех отмеченных точек минимально, если число отмеченных точек нечетно. Почему алгоритм перестает работать при четном числе точек? Причина довольно ясна: при четном числе отмеченных точек не исключен «ничейный» исход голосования, а как только голоса разбиваются поровну, алгоритм не срабатывает.

Попробуйте самостоятельно ответить на следующие вопросы:

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

2. При каких условиях перемещение одной или нескольких отмеченных точек не сказывается на положении точки x?

3. Изменится ли алгоритм с голосованием, если мы вздумаем учесть ширину улиц?

4. Изменится ли алгоритм, если точка x и отмеченные точки могут не располагаться на перекрестках?

5. Применим ли алгоритм с голосованием в том случае, если сеть улиц образована прямыми, идущими в самых разных, а не только в двух взаимно перпендикулярных направлениях?

6. Останется ли алгоритм в силе, если улицы будут кривыми или зигзагообразными?

Хотя алгоритм с голосованием применим к любым сетям, на «чистой» плоскости без выделенной сети он сразу утрачивает силу, и это понятно: по чистой плоскости мы можем перемещаться в любом направлении, не придерживаясь заданных маршрутов. Общая задача ставится так. На плоскости заданы n точек. Требуется найти такую точку x, чтобы сумма кратчайших расстояний от нее до заданных точек была минимальной. Рассмотрим, например, три города A, B и C. Где следовало бы построить аэропорт, чтобы суммарная протяженность воздушных маршрутов из него в эти города была минимальной? Ясно, что если бы речь шла о длине автомобильных маршрутов, связывающих некоторую точку на карте с городами A, B и C, то ответ был бы другой. Иначе говоря, идеальное место для аэропорта может не совпадать с идеальным местом для автобусной станции.

Ответ, основанный на довольно сложных геометрических соображениях, гласит: идеальным местом для строительства аэропорта была бы такая точка на карте, в которой лучи, проведенные к трем городам, образовывали бы между собой углы в 120°. Если бы число городов возросло до четырех, причем города располагались в вершинах выпуклого четырехугольника, то аэропорт выгоднее всего было бы построить в точке пересечения диагоналей. Доказать это утверждение совсем не трудно. Общая задача (найти точку x, сумма кратчайших расстояний от которой до n заданных точек плоскости минимальна) более трудная.

Может быть, вам удастся придумать простое механическое устройство (аналоговую вычислительную машину), позволяющее быстро находить положение точки x для трех заданных точек на плоскости? Пусть плоскость изображает плоскость стола. В каждой из заданных точек просверлим в крышке стола отверстие. Затем пропустим через эти отверстия по веревочке, верхние концы веревочек свяжем в один узел, а к нижним подвесим одинаковые грузики. Равные силы, действуя на веревочки, заставят их «проголосовать» за жителей трех населенных пунктов, и узел расположится в точке x. Наша аналоговая машина основана на использовании изоморфизма между математической структурой задачи и структурой физической модели.

Усложним теперь исходную задачу. Предположим теперь, что в точках A, B и C находятся не населенные пункты с одинаковым количеством жителей, а три дома, причем в доме A живут 20 школьников, в доме B — 30 школьников и в доме C — 40 школьников. Все дети ходят в одну школу. Где следует выстроить школу, чтобы свести до минимума сумму расстояний, проходимых всеми детьми?