|
|
 |
Условие
Петя и Вася по очереди пишут на доску дроби вида $1/n$, где $n$ — натуральное, начинает Петя. Петя за ход пишет только одну дробь, а Вася за первый ход — одну, за второй ход — две, и так каждым следующим ходом на одну дробь больше. Вася хочет, чтобы после какого-то хода сумма всех дробей на доске была натуральным числом. Сможет ли Петя помешать ему?Решение
Лемма. Любое число $a$ можно представить в виде суммы $k$ дробей вида $\frac{1}{n}$ конечным числом способов (если вообще можно представить).Доказательство леммы. Будем доказывать индукцией по $k$. Для $k = 1$ утверждение очевидно. Пусть утверждение верно для $k = l - 1$. Докажем для $k = l$. Посмотрим на наибольшую дробь в разложении, она не может быть меньше, чем $\frac{a}{k}$, иначе сумма всех дробей точно меньше $а$. Значит, знаменатель этой дроби точно не больше, чем $\frac{k}{a}$, то есть у нас существует конечное количество значений наибольшей дроби. Далее для каждого отдельного значения этой наибольшей дроби мы получаем, что сумма оставшихся $l - 1$ дробей должна быть каким-то фиксированным числом. По предположению индукции мы знаем, что таких $l-1$ дробей для каждого отдельного значения наибольшей дроби конечно, а, значит, и всего представлений $a$ в виде суммы $k$ дробей конечно.
Теперь покажем, как Петя может ходить так, чтобы Вася после своего хода никогда не сделал сумму целой. Пусть перед ходом Пети сумма чисел на доске равна $S$, а Вася после его хода будет выписывать $k$ дробей. Заметим, что после хода Васи сумма чисел точно не станет больше, чем $S + k + 1$, то есть он точно не получит натуральное число, большее $S + k + 1$. Для каждой из оставшихся потенциальных натуральных сумм (а их осталось конечное количество) посчитаем, на сколько надо увеличить текущую сумму, чтобы она стала такой. Для каждого такого числа существует лишь конечное количество представлений его в виде суммы $k + 1$ дроби вида $\frac{1}{n}$ по следствию из леммы. Значит, всего во всех представлениях задействовано конечное число дробей вида $\frac{1}{n}$.
Пусть Петя тогда запишет на доску ту дробь, которая не задействована ни в
одном из представлений. Тогда Вася точно не сможет написать $k$ дробей так, чтобы сумма стала натуральной.
