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

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

Условие

Коля и Петя делят 2n + 1 орехов, n$ \ge$2, причём каждый хочет получать возможно больше. Предполагаются три способа дележа (каждый проходит в три этапа). 1-й этап: Петя делит все орехи на две части, в каждой не меньше двух орехов. 2-й этап: Коля делит каждую часть снова на две, в каждой не меньше одного ореха. 1-й и 2-й этапы общие для всех трёх способов. 3-й этап: При первом способе Коля берёт большую и меньшую части; При втором способе Коля берёт обе средние части; При третьем способе Коля берёт либо большую и меньшую части, либо обе средние части, но за право выбора отдаёт Пете один орех. Определить, какой способ самый выгодный для Коли и какой наименее выгоден для него.

Решение

Покажем, что первый способ для Коли – наиболее выгодный, а остальные 2 – наименее выгодные. Докажем, что при первом способе дележа Коля может гарантировать себе хотя бы n+1 орех, а Петя – хотя бы n орехов. Тем самым при наилучших действиях каждой из сторон Коля получит ровно n+1 орех. Стратегия Коли такова: разделить каждую из Петиных частей на две части, одна из которых содержит ровно 1 орех. В этом случае, на какие бы две части не разделил Петя исходное количество, Коля заведомо получит хотя бы n+1 орех. Стратегия Пети такова: разделить все орехи на части из n и из n+1 орехов. Легко проверить, что независимо от действий Коли Пете достанется не меньше n орехов. Действительно, пусть a - наибольшая часть. Тогда есть часть b, для которой a+b=n+1 или n. Но Коля получил заведомо не более a+b орехов, значит Пете остается не менее n. Докажем теперь, что при втором способе дележа Коля может гарантировать себе хотя бы n орехов, а Петя – хотя бы n+1 орех. Действительно, стратегия Пети такова: разделить все орехи на две части: из 2n-1 и из 2 орехов. Тогда Пете останется не менее n+1 ореха. Стратегия Коли: разделить обе Петины части примерно пополам, то есть так, чтобы число орехов в соответствующих частях либо совпадало, либо отличалось ровно на 1. Тогда Коля гарантирует себе n орехов. При третьем способе дележа Коля гарантирует себе n орехов, а Петя – n+1 орехов. Стратегии такие же, как в первом случае.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 24
Год 1961
вариант
1
Класс 9
Тур 2
задача
Номер 5

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

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