Принцип крайнего

Для решения достаточно привести стратегию за первого, при которой он гарантированно объедает второго, а также стратегию за второго, при которой гарантированно первый если и объедает его, то не более, чем на граммов.

Начнём со стратегии для первого. Пусть он на каждом шаге берёт самое тяжёлое яблоко. Тогда если на м шаге первый взял яблоко с весом а второй — c весом то (на последнем шаге второму может не достаться яблока, если количество яблок нечётное, и в этом случае считаем, что Следовательно, первый однозначно объест второго.

Теперь приведём стратегию за второго. Стратегия будет аналогичной, второй на каждом шаге берёт самое тяжелое яблоко из имеющихся. Пусть первый взял на первом шаге яблоко с весом Теперь рассмотрим й и й шаги. Второй на м шаге взял яблоко с весом а первый на м — с весом Ясно, что Таким образом, если не учитывать первое яблоко, второй объел первого. А если его учесть, то первый если и смог объесть второго, то не более чем на граммов, потому что