|
|
 |
Условие
Двое делят кусок сыра. Сначала первый режет сыр на два куска, потом второй – любой из кусков на два, и так далее, пока не получится пять кусков. Затем первый берёт себе один кусок, потом второй – один из оставшихся кусков, потом снова первый – и так, пока куски не закончатся. Для каждого игрока выяснить, какое наибольшее количество сыра он может себе гарантировать.
Решение
Пусть всего сыра 50 (фунтов). Играют A (первый) и B. Ясно, что при делёжке обоим выгоден жадный алгоритм (каждый раз выбирается самый большой кусок). При этом B получит второй и четвёртый по весу куски. Обозначим их суммарный вес через R.
Покажем, как A может гарантировать себе 30 фунтов.
Сначала A делит сыр на куски веса 30 и 20.
Пусть вес меньшего куска, отрезанного потом B, равен u. Если u ≤ 5, то А может получить набор L = {30 – u, 20 – u, u, u}, где 0 < u ≤ 5, в противном случае – набор M = {20, 20 – v, 10, v}, где 5 < v ≤ 10 (v = u либо v = 20 – u).
Оба набора имеют вид {a, 20 – d, c, d}, где a > 20 – d > c ≥ d.
Сумма R кусков на 2-м и 4-м местах сейчас 20. После разреза R сможет стать больше, только если хотя бы один из этих кусков уступит место бóльшему куску, сдвинувшись на место с бóльшим номером. Но кусок 20 – d "вправо" не сдвинешь: a нельзя разрезать на две части, бóльшие 20 – d, (в обоих случаях 20 – d > a/2). Кроме того, в случае L нельзя сдвинуть обе части d на 5-е место. А вот в случае M одна из двух бóльших частей может быть разрезана на два куска, бóльшие d. Разберём два подслучая.
1) Часть a = 20 разрезана на куски s, 20 – s, где d < s ≤ 10. Тогда 20 – s < 20 – d и R = (20 – s) + s = 20.
2) Часть b = 20 – d разрезана на два куска, бóльших d. Тогда оба эти куска меньше 10 (поскольку d > 5), то есть 2-я по весу часть равна 10. Значит, R < 20.
Теперь покажем, как B может гарантировать себе 20 фунтов (то есть обеспечить R ≥ 20).
Пусть после первого разреза получились куски x и y ≥ x. Назовём крупными куски веса не меньше 20.
При x ≤ 10 игрок B режет y пополам, а при x ≥ 20 отрезает от y кусок веса 20. В обоих случаях образуются два крупных куска a ≥ b ≥ 20. Если A их не режет, то B – тоже, и сможет один из них взять. Если A один из них разрежет, то B разрежет другой на пропорциональные части. Эти четыре части образуют две пары a1 ≥ b1 и a2 ≥ b2, где b1 + b2 = b. Меньшие куски из пар B гарантированы, поэтому R ≥ b ≥ 20.
При 10 ≤ x ≤ 20 B получает набор {20, x, y – 20}, где все куски не меньше 10.
Если далее A режет кусок 20, то B (отрезав 10 от одного из "старых кусков") получает набор {10 + a ≥ 10 + b ≥ 10 ≥ 10 – b ≥ 10 – a}, в котором R = 20.
Иначе перед B набор {20, a, b, с}, где a ≥ b ≥ c. Отрезав b от 20, он переходит к набору {a, b, b, 20 – b, с}.
Поскольку a + b + с = 30, то b + с ≤ 20, a + b ≥ 20, значит, c ≤ 20 – b ≤ a и R = b + (20 – b) = 20.
Ответ
Первый – 0,6, второй – 0,4 всего куска.
Замечания
8-9 кл. – 8 баллов, 10-11 кл. – 6 баллов.
