Алгебраические текстовые задачи на Иннополисе

Подсказка 1

Давайте подумаем, какому условию должна удовлетворять стратегия Васи, иначе говоря, когда он ну точно не получит наибольшее вероятное количество фунтиков?

Подсказка 2

Если он 3 раза назовет число, большее N, то весь фонд уйдёт Пете. Можем сначала подобрать стратегию для Васи, а потом попробовать доказать, что она гарантирует наибольшее возможное количество фунтиков. Давайте рассматривать стратегии Васи с определёнными количествами "провалов" (когда Вася называет число k > N).

Подсказка 3

Давайте рассмотрим наименьшее число n, при котором n(n + 1)/2 ≥ M, и подумаем, какие шаги оптимально делать Васе до первого "провала".

Подсказка 4

Пусть Вася будет называть числа k₁ = n, k₂ = n + (n - 1), ... , kₘ₊₁ = n + (n - 1) + ... + (n - m), пока не угадает число N или не превзойдет его. Попробуйте придумать стратегию, при которой Вася будет совершать не более одного "провала".

Подсказка 5

Если Вася попадает в число N, то игра заканчивается. Иначе после провала он перейдет к угадыванию. Вася будет называть последовательные числа от kₘ₊₁ до N (в случае провала, N будет меньше kₘ₊₁). Сколько тогда фунтиков обеспечит себе Вася?

Подсказка 6

До kₘ₊₁ - (m + 1) раунд, до угадывания — не более (m +1) раунда, тогда Вася сыграет (m + 1) + (n - (m + 1)) раундов и получит (2M/3 - n) фунтиков. Надо теперь доказать, что эта стратегия оптимальна. Предположите для начала, что существует стратегия, при которой Вася может получить больше фунтиков.

Подсказка 7

Эта стратегия будет предписывать возрастающую последовательность чисел k₁ < k₂ < ... < kₜ, где t < n. Какое еще условие на k можно наложить через n? Попробуйте доказать через определение n, что такая стратегия не даст нам гарантированно больше фунтиков.