111 подписчиков
"Лемма о бензоколонках" (или Raney's lemma)
Лемму эту опубликовал George Raney в 1960 году в журнале Transactions of the American Mathematical Society
У нас утверждение больше известно благодаря публикации в задачнике журнала "Квант" в 1971 году под номером М82
Формулировка задачи такая:
На кольцевой автомобильной дороге стоят несколько одинаковых автомашин
Если бы весь бензин, имеющийся в этих автомашинах, слили в одну, то эта машина смогла бы проехать по всей кольцевой дороге и вернуться на прежнее место
Докажите, что хотя бы одна из этих машин может объехать всё кольцо, забирая по пути бензин у остальных машин
Ее несложно переформулировать с следующем более математическом виде (упражнение)
Даны числа x_1, x_2, ..., x_n с нулевой суммой
Тогда существует циклическая перестановка, для которой все частичные суммы неотрицательны
То есть существует такое k, что x_k⩾0, x_k+x_{k+1}⩾0, x_k+x_{k+1}+x_{k+2}⩾0,... x_k+x_{k+1}+...x_{k-1}⩾0
Одно из наиболее классических и простых доказательств этого утверждение проводится при помощи индукции
Если машина одна, то в ней достаточно бензина на полный круг
Пусть у нас есть n машин, то можно найти 2 соседние, такие, что из первой можно доехать до второй по часовой стрелке
Уберем вторую и отдадим весь ее бензин первой
По предположению индукции, среди оставшихся n-1 существует одна, из которой можно проехать полный круг по часовой стрелке — она же подойдет и для n в исходной конфигурации
Однако есть доказательство с выпукло-геометрическими мотивами
Рассмотрим n векторов, полученных из (1,-1,0,0,..,0) циклическими перестановками
Они все лежат в (n-1)-мерной гиперплоскости (сумма координат равна нулю) и являются вершинами симплекса, содержащего начало координат (центр его масс)
Луч из начала координат в точку (x_1,...,x_n) пересекает некоторую грань этого симплекса
Сделаем циклическую перестановку так, чтобы эта грань не содержала вершину (-1,0,0,...,0,1)
Но все точки (y_1,...,y_n) в этой грани имеют неотрицательные частичные суммы координат, поскольку этим свойством обладают все вершины этой грани, а значит и все выпуклые комбинации
1 минута
19 ноября 2023