Али-Баба и 1/40

[Um_nik]

Он не умеет. Выкладывайте.

[fortpost]

Выкладываю.
Показать скрытый текст

Покажем, что Али-Баба может добиться, чтобы в 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₃⁽⁰⁾=y3 +3, x₄⁽⁰⁾=y4 +4, положив в кружки соответственно 1, 2, 3 и 4 монеты. После перестановки кружек получим новые кучки, состоящие из x₁⁽¹⁾=y₁+z₁, x₂⁽¹⁾=y₂+z₂, x₃⁽¹⁾=y₃ +z₃, x₄⁽¹⁾=y₄+z₄ монет, где z1, z2, z3 и z4—некоторая перестановка чисел 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 монет.