Задача:
Ева хочет дать Адаму k сладких яблок. Но, кроме них, у неё есть не более 2012 кислых яблок, которые она даёт Адаму до сладких. Каждое яблоко, которое получает Адам, он может съесть или выкинуть. То, что сначала идут кислые яблоки, а потом сладкие, а также то, что кислых яблок не более 2012, а сладких ровно k, Адаму известно. Найдите наименьшее k, при котором Адам гарантированно может съесть больше сладких яблок, чем кислых.
Решение: Поскольку Адаму известно, что сначала идут кислые яблоки, а потом сладкие, то, вкусив впервые сладкое яблоко, все последующие он будет съедать. Тогда для каждого i обозначим через fi номер яблока, который Адам собирается съесть, если все ранее съеденные были кислые. Также положим f0 = 0. Для того, чтобы Адаму удалось съесть больше сладких яблок, чем кислых, после fi+1, если оно оказывается сладким, должны идти еще как минимум i сладких яблок. Откуда fi+1–fi ≤ k–i (поскольку сладкие яблоки могли начаться сразу c fi+1 яблока). Складывая неравенства для всех i от 0 до k, получаем, что fk = (fk–fk-1)+…+(f1–f0) ≤ 1+…+k = k(k+1)/2. Заметим, что fk должно быть не менее 2012, откуда 2012 ≤ k(k+1)/2. Минимальное такое k равно 63. Стратегия Адама может быть получена заменой всех неравенств на равенства.
