Задача 107808

Темы:    [ Теория игр (прочее) ] [ Полуинварианты ] [ Процессы и операции ]

Сложность: 5 Классы: 9,10,11

Условие

Автор: Канель-Белов А.Я.

Али-Баба и разбойник делят клад, состоящий из 100 золотых монет, разложенных в 10 кучек по 10 монет. Али-Баба выбирает 4 кучки, ставит около каждой из них по кружке, откладывает в каждую кружку по несколько монет (не менее одной, но не всю кучку). Разбойник должен как-то переставить кружки, изменив их первоначальное расположение, после чего монеты высыпаются из кружек в те кучки, около которых оказались кружки. Далее Али-Баба снова выбирает 4 кучки из 10, ставит около них кружки, и т. д. В любой момент Али-Баба может уйти, унеся с собой любые три кучки по выбору. Остальные монеты достаются разбойнику. Какое наибольшее число монет сможет унести Али-Баба, если разбойник тоже старается получить побольше монет?

Решение

  Покажем, что Али-Баба может добиться, чтобы в 7 кучках лежало не более, чем по 4 монеты, а разбойник может добиться, чтобы не было кучек, содержащих менее 4 монет. Следовательно, Али-Баба унесет 100 - 7 ^. 4 = 72 монеты.

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

Покажем теперь, что Али-Баба может добиться, чтобы в 7 кучках лежало не более, чем по 4 монеты.

Пусть имеются 4 кучки, в каждой из которых лежит более, чем 4 монеты, и x₁⁽⁰⁾x₂⁽⁰⁾x₃⁽⁰⁾x₄⁽⁰⁾5 — количества монет в этих кучках. Покажем, что Али-Баба может добиться, чтобы в одной из этих кучек стало меньше 4 монет, причем количество монет в каждой из оставшихся шести кучек не изменилось. Разложим эти кучки следующим образом:

x₁⁽⁰⁾ = y₁ + 1,    x₂⁽⁰⁾ = y₂ + 2,    x₃⁽⁰⁾ = y₃ + 3,    x₄⁽⁰⁾ = y₄ + 4,

положив в кружки соответственно 1, 2, 3 и 4 монеты. После перестановки кружек получим новые кучки, состоящие из

x₁⁽¹⁾ = y₁ + z₁,    x₂⁽¹⁾ = y₂ + z₂,    x₃⁽¹⁾ = y₃ + z₃,    x₄⁽¹⁾ = y₄ + z₄

монет, где z₁, z₂, z₃ и z₄ — некоторая перестановка чисел 1, 2, 3, 4. Далее процесс повторяется с заменой чисел x₁⁽⁰⁾, ..., x₄⁽⁰⁾ на расположенные в невозрастающем порядке числа x₁⁽¹⁾, ..., x₄⁽¹⁾.

Докажем, что на некотором шаге процесс оборвется, т. е. в одной из этих кучек станет меньше 5 монет. Имеет место одна из следующих трех возможностей:

1) x₁⁽¹⁾ > x₁⁽⁰⁾ (если первую кружку переставили);

2) x₁⁽¹⁾ = x₁⁽⁰⁾, x₂⁽¹⁾ > x₂⁽⁰⁾ (если первую кружку оставили на месте, а вторую переставили);

3) x₁⁽¹⁾ = x₁⁽⁰⁾, x₂⁽¹⁾ = x₂⁽⁰⁾, x₃⁽¹⁾ > x₃⁽⁰⁾ (если первые две кружки остались на месте).

На каждом шаге количество монет в первой кучке не уменьшается. Поэтому число шагов, при которых реализуется первая возможность, конечно. Суммарное число монет в первой и второй кучках тоже не уменьшается, поэтому число шагов, при которых реализуется вторая возможность, также конечно. Аналогично проверяется, что число шагов, реализующих третью возможность, тоже конечно. Следовательно, на некотором шаге процесс оборвется, что соответствует тому, что в некоторой кучке окажется не более 4 монет. При этом количество кучек с не более, чем 4 монетами увеличится. Повторяя этот процесс, в конце концов придем к тому, что останется не более трех кучек, содержащих больше 4 монет.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	59
Год	1996
вариант
Класс	9
задача
Номер	6