Выбрана 1 задача 
Убрать все задачи
Имеется кучка из 100 камней. Двое играют в следующую игру. Первый игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый может забрать 1, 2 или 3 камня, затем второй 1, 2, 3 или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?
Решение
|
|
 |
Условие
Положительные числа х1, ..., хk удовлетворяют неравенствам
а) Докажите, что k > 50.
б) Построить пример таких чисел для какого-нибудь k.
в) Найти минимальное k, для которого пример возможен.
Решение
а) По условию Таким образом, хотя
бы для одного числа (пусть для х1) выполнено неравенство
то есть х1 > 4.
Отсюда
Поскольку минимум функции 2x² –
x равен – ⅛, то k – 1 > 8·28 > 50.
б) Возьмём k = 2501, х1 = 10, х2 = х3 = ... = х2501 = 0,1. Тогда
и все неравенства выполнены.
в) Положим p(х) = 2х² – х, q(х) = х³ – 2х, Заметим, что функция p отрицательна на интервале (0, ½), убывает на интервале (0, ¼) и возрастает на интервале (¼, +∞); q убывает на (0, ½); f возрастает на интервалах (–∞, ½) и (½, +∞) и положительна на (0, ½) и
Пусть k минимально, а числа x1 ≤ x1 ≤ ... ≤ xk удовлетворяют условию, то есть p(x1) + ... + p(xk) < 0, q(x1) + ... + q(xk) > 0.
Тогда xk–1 < ½. Действительно, в противном случае можно уменьшить k, заменив xk–1 и xk на такое число x0 ≥ xk, что p(x0) = p(xk–1) + p(xk). При этом сумма p(xi) не изменится, а сумма q(xi) не уменьшится: q(x0) = f(x0)p(x0) = f(x0)p(xk–1) + f(x0)p(xk) ≥ f(xk–1)p(xk–1) + f(xk)p(xk) = q(xk–1) + q(xk).
Теперь из решения а) видно, что xk > 4.
Далее, не меняя k, будем набор {xi} последовательно упрощать.
3) Если какое-то число xi ∈ (¼, ½), заменим его на ½ – xi. При этом сумма p(xi) не изменится, а сумма q(xi) не уменьшится. Поэтому далее считаем, что x1, x2, ..., xk–1 ≤ ¼.
Положим n = k – 1. На следующем шаге сделаем числа x1, x2, ..., xn равными, сохранив сумму p(xi) и увеличив сумму q(xi). Нам понадобится
Лемма. Пусть 0 < a < b < c < d ≤ ¼ и p(a) + p(d) = p(b) + p(c). Тогда q(a) + q(d) < q(b) + q(c).
Доказательство. Поскольку p(a) + p(d) = p(b) + p(c), а p(x) убывает, то p(c) – p(d) = p(a) – p(b) > 0. Поэтому доказываемое неравенство
q(a) + q(d) < q(b) + q(c) (или q(a) – q(b) < q(c) – q(d)) можно заменить на Подставив в дробь
явные формулы для p и q, разложив на множители и сократив на x – y, получим
Поскольку f возрастает на (0, ½), то F(y, z) возрастает при одновременном возрастании x и y (0 < x < y < ¼); в частности, F(a, b) < F(c, d).
Применим теперь метод Штурма. Пусть P – среднее арифметическое чисел p(x1), p(x2), ..., p(xn). Если среди этих чисел есть неравные, то найдутся такие i, j, что p(xi) < P и p(xj) > P. Сблизим xi и xj так, чтобы сумма p(xi) + p(xj) не изменилась, а хотя бы одно из слагаемых стало равным P (это возможно ввиду монотонности и непрерывности p(x) на полуинтервале (0, ¼]). По лемме сумма q(xi) + q(xj) возрастёт. Будем повторять операцию, пока все p(xi) не станут равны P.
Осталось выяснить, при каком минимальном n существуют такие u ≤ ½, v > 4, что 2(nu² + v²) < nu + v, 2(nu + v) < (nu³ + v³).
Перепишем эти неравенства в виде Отсюда f(v) > f(u).
Оценим, какое минимальное значение может принимать выражение при наших ограничениях. Это и будет оценкой снизу для n.
Будем уменьшать v, пока не достигнем значения, при котором f(v) = f(u). Так как f(u) > f(0) = 2 = f(4), то и новое значение v больше 4. При этом число только уменьшится.
Теперь u и v – корни квадратного уравнения x² – 2 = t(2x – 1) (где t = f(u)), поэтому u + v = 2t, то есть
Теперь выражение принимает вид
Числитель производной g' равен –14(3u² – 16u + 2), поэтому g' обращается в нуль в точке причём это точка минимума.
Таким образом, n > g(u0) = 514,16..., то есть n ≥ 515, а k ≥ 516.
Построим пример для n = 515. Возьмём u = ⅛ (это число близко к u0). Соответствующее значение при этом
. Будем увеличивать значение v. При этом f(v) будет расти и наступит момент, когда
станет больше 515, а
будет еще меньше 515. На этом значении v и остановимся (например, подходит v = 5,169).
Ответ
в) k = 516.
Замечания
Для знатоков. 1. Для доказательства леммы можно использовать теорему Коши, согласно которой где z ∈ (x, y).
2. Можно обойтись без леммы и метода Штурма, если воспользоваться выпуклостью функций p и f на (0, ½).
Заменим каждое из чисел x1 ≤ x1 ≤ ... ≤ xn на такое число u ∈ (0, ¼], что p(u) = P < 0. При этом сумма p(xi) не изменится. Докажем, что сумма q(xi) не уменьшится.
Положим В силу неравенства Иенсена и неравенства между средними
следовательно, t ≥ u.
Значит,
3. Баллы: 3 + 3 + 3.
4. Задача также предлагалась в Задачнике "Кванта" ("Квант", 2007, №2, М2040).
