шедевры олимпиадной математики 1
Мне редко нравятся олимпиадные задачи по математике, но бывает что конкретно торкает. Эта среди моих самых фаворитов. Источник - забыл какая именно иранская студенческая олимпиада. Сколько раз где я её ни давал, ни разу ещё никто не решил. Сам тоже не решил в своё время.
На соревновании предложено n заданий и участвует несколько студентов. Каждое задание можно либо выполнить, либо не выполнить. Жюри определяет количество баллов, начисляемое за выполнение каждого задания, случайно выбирая его от 1 до 2n (все 2n возможностей равновероятны; баллы за разные задачи выбираются независимо). Никакие два студента не выполнили одного и того же множества заданий. Докажите, что с вероятностью не менее 1/2 в соревновании будет единственный победитель (участник с наибольшим числом набранных баллов).
Если победитель не один, то для одной из задач верно следующее: победитель среди решивших её вровень с победителем среди не решивших её. Вероятность этого события не больше 1/2n, даже если зафиксировать баллы за остальные задачи.
Некоторая проблема этого подхода в том, что если баллы выбираются, скажем, от 1 до n, то получаемая оценка вероятности не удовлетворительна. Ваня Митрофанов предлагает более тонкий аргумент.
Назовем распределение оценок предельным, если хотя бы одна из них равна максимально допустимой (в нашем случае 2n баллов). Рассмотрим некоторое распределение оценок. Пусть Вася --- один из победителей при таком распределении. Увеличим оценки за решенные Васей задачи на одну и ту же величину так, чтобы распределение стало предельным. Легко видеть, что теперь Вася единственный победитель. Кроме того, каждое предельное распределение может быть получено не более чем из одного распределения, в котором победитель не единственный. Значит, доля тех распределений, в которых он не единственный, не больше доли предельных распределений. Последняя равна 1-(1-1/2n)^n, эта величина стремится к 1-e^{-1/2}, что чуть меньше 40%.
При таком взгляде на события получается нетривиальная оценка при любом положительном отношении максимального балла к числу задач. Любопытно, насколько она точная.
На соревновании предложено n заданий и участвует несколько студентов. Каждое задание можно либо выполнить, либо не выполнить. Жюри определяет количество баллов, начисляемое за выполнение каждого задания, случайно выбирая его от 1 до 2n (все 2n возможностей равновероятны; баллы за разные задачи выбираются независимо). Никакие два студента не выполнили одного и того же множества заданий. Докажите, что с вероятностью не менее 1/2 в соревновании будет единственный победитель (участник с наибольшим числом набранных баллов).
Если победитель не один, то для одной из задач верно следующее: победитель среди решивших её вровень с победителем среди не решивших её. Вероятность этого события не больше 1/2n, даже если зафиксировать баллы за остальные задачи.
Некоторая проблема этого подхода в том, что если баллы выбираются, скажем, от 1 до n, то получаемая оценка вероятности не удовлетворительна. Ваня Митрофанов предлагает более тонкий аргумент.
Назовем распределение оценок предельным, если хотя бы одна из них равна максимально допустимой (в нашем случае 2n баллов). Рассмотрим некоторое распределение оценок. Пусть Вася --- один из победителей при таком распределении. Увеличим оценки за решенные Васей задачи на одну и ту же величину так, чтобы распределение стало предельным. Легко видеть, что теперь Вася единственный победитель. Кроме того, каждое предельное распределение может быть получено не более чем из одного распределения, в котором победитель не единственный. Значит, доля тех распределений, в которых он не единственный, не больше доли предельных распределений. Последняя равна 1-(1-1/2n)^n, эта величина стремится к 1-e^{-1/2}, что чуть меньше 40%.
При таком взгляде на события получается нетривиальная оценка при любом положительном отношении максимального балла к числу задач. Любопытно, насколько она точная.