|
|
 |
Условие
В английском клубе вечером собрались n его членов (n ≥ 3). По традициям клуба каждый принес с собой сок того вида, который он предпочитает, в том количестве, которое он планирует выпить в течение вечера. Согласно правилам клуба, в любой момент любые три его члена могут присесть за столик и выпить сока (каждый – своего) в любом количестве, но обязательно все трое поровну. Докажите, что для того, чтобы все члены могли в течение вечера полностью выпить принесенный с собой сок, необходимо и достаточно, чтобы доля сока, принесенного каждым членом клуба, не превосходила одной трети от общего количества.
Решение
Необходимость условия сразу следует из того, что доля выпитого любым членом клуба не превосходит одной трети от общего объёма выпитого и, значит, одной трети от общего объема принесённого сока (общий объём выпитого равен утроенному объёму выпитого этим членом клуба плюс объёму выпитого тройками членов клуба, в которые он не входил). Докажем достаточность.
Первый способ. Проведём индукцию по числу членов клуба. База. Если n = 3, то по условию задачи доля каждого из трёх членов клуба равна одной трети от общего количества, и они смогут выпить весь свой сок, присев за столик один раз.
Шаг индукции. Пусть n ≥ 4. Предположим, что максимальная доля сока была лишь у одного члена клуба. В этом случае за столик присаживаются член клуба с максимальной долей и два – с минимальной. Пока они пьют, доля каждого из них в общем объёме уменьшается, а доли всех оставшихся возрастают. Пусть они продолжают пить до тех пор, пока один из членов клуба с наименьшей долей не допьёт все до конца (тогда оставшиеся члены клуба смогут допить весь свой сок в соответствии с предположением индукции), либо наибольшая из долей членов клуба, не сидящих за столиком, не сравняется с максимальной (принадлежащей одному из сидящих за столиком). Таким образом, остаётся рассмотреть случай, когда не менее чем у двух членов клуба доля сока максимальна.
Предположим, что доля максимальна ровно у двух членов клуба. Тогда за столик присаживаются эти два члена, а также третий, обладающий минимальной долей. Пусть они продолжают пить до тех пор, пока член клуба с минимальной долей не допьёт весь свой сок до конца (тогда оставшиеся члены клуба смогут допить весь свой сок в соответствии с предположением индукции), либо наибольшая из долей членов клуба, не сидящих за столиком, не сравняется с максимальной
(принадлежащей двоим из сидящих за столиком). Таким образом, остаётся рассмотреть случай, когда не менее чем у трёх членов клуба доля сока максимальна.
Предположим, что доля максимальна у k ≥ 3 членов клуба. Опишем алгоритм, позволяющий всем членам клуба выпить весь принесённый сок. Пусть
Δ – разница в объеме сока между максимальной и следующей по величине долями. Члены клуба с максимальной долей поочередно пьют в тройках "по кругу" (сначала первый со вторым и третьим, затем второй с третьим и четвёртым и т.д., а в конце – k-й с первым и вторым), при этом каждая тройка выпивает по Δ/3. После этого количество членов клуба с максимальной долей увеличивается по крайней мере на одного. Так продолжаем до тех пор, пока доли всех членов клуба не станут одинаковыми. Далее все допивают остаток таким же способом – в тройках "по кругу".
Второй способ. Разобьём окружность единичной длины на n дуг, длины которых равны соответственно долям сока, принесённого каждым из n членов клуба. Расположим в круге тройник – фигуру из трёх радиусов, образующих попарно углы в 120° (см. рис.). Поскольку длина каждой дуги не превосходит 1/3, ни при каком положении тройника разные его концы не будут указывать на внутренние точки дуги, соответствующей одному члену клуба.
Несложно видеть, что поворот тройника на 120° обеспечит способ выпивания членами клуба всего сока, который они принесли с собой.
