ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65685
Темы:    [ Кооперативные алгоритмы ]
[ Принцип крайнего (прочее) ]
[ Индукция (прочее) ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В английском клубе вечером собрались n его членов  (n ≥ 3).  По традициям клуба каждый принес с собой сок того вида, который он предпочитает, в том количестве, которое он планирует выпить в течение вечера. Согласно правилам клуба, в любой момент любые три его члена могут присесть за столик и выпить сока (каждый – своего) в любом количестве, но обязательно все трое поровну. Докажите, что для того, чтобы все члены могли в течение вечера полностью выпить принесенный с собой сок, необходимо и достаточно, чтобы доля сока, принесенного каждым членом клуба, не превосходила одной трети от общего количества.


Решение

  Необходимость условия сразу следует из того, что доля выпитого любым членом клуба не превосходит одной трети от общего объёма выпитого и, значит, одной трети от общего объема принесённого сока (общий объём выпитого равен утроенному объёму выпитого этим членом клуба плюс объёму выпитого тройками членов клуба, в которые он не входил). Докажем достаточность.

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

  Второй способ. Разобьём окружность единичной длины на n дуг, длины которых равны соответственно долям сока, принесённого каждым из n членов клуба. Расположим в круге тройник – фигуру из трёх радиусов, образующих попарно углы в 120° (см. рис.). Поскольку длина каждой дуги не превосходит 1/3, ни при каком положении тройника разные его концы не будут указывать на внутренние точки дуги, соответствующей одному члену клуба.

  Поставим тройник в произвольное начальное положение, в котором все его концы показывают на внутренние точки дуг. За столик посадим членов клуба, соответствующих дугам. Будем вращать тройник по часовой стрелке и сопоставлять повороту выпивание каждым из членов клуба, сидящим за столиком, доли сока (относительно общего начально принесённого объёма), равной длине дуги, вдоль которой прошел соответствующий конец тройника. В момент, когда хотя бы один из концов тройника проходит крайнюю точку дуги, будем проводить смену членов клуба, сидящих за столиком: столик будет покидать участник, из чьей дуги выходит конец тройника, а присаживаться – участник, в дугу которого входит этот конец тройника.
  Несложно видеть, что поворот тройника на 120° обеспечит способ выпивания членами клуба всего сока, который они принесли с собой.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2016
Номер 79
класс
Класс 11
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .