Двое играют в игру: ** доску выписывают натуральное число, а затем по очереди они...

Question

72 просмотров

Двое играют в игру: на доску выписывают натуральное число, а затем по очереди они вычитают из числа на доске, квадрат, не превосходящий этого числа, и полученную разность вместо исходного числа записывают на доске, квадрат, не превосходящий этого числа, и полученную разность записывают на доску. Докажите, что существует бесконечно много начальных чисел,при которых выигрывает второй игрок

Алгебра DanielDzekson_zn (6.9k баллов) 29 Апр, 18 | 72 просмотров

Дан 1 ответ

polka125_zn · Answer 1 · 2018-04-29T07:14:36+0000

Предположим противное: всего чисел, для которых выигрывает второй игрок конечно. Пусть всего их c: { $x_1, x_2, ... x_c$ }. Возьмём произвольное число y, для которого выигрывает первый игрок. Понятно, что должно существовать такое z, что $y - z^2 = x_i$ для некоторого i. То есть утверждение задачи эквивалентно тому, что существует некоторое конечное множество A такое, что любое натурально число либо принадлежит A, либо может быть представлено как $z^2$ + элемент из А. (z - натуральное). Предположим, что это так. Тогда возьмём отрезок [1, m]. Далее будем брать элемент из A и прибавлять к нему квадраты натуральных чисел (1, 4, 9 ...) и если это число лежит в промежутке [1, m] увеличивать некий счётчик count. Понятно, что для элемента xi мы увеличим счётчик на $\sqrt{m - x_i}$ . Но тогда когда мы сделаем это для каждого элемента из A, в счётчике будет $[\sqrt{m - a_1}] + [\sqrt{m - a_2}] + ... + [\sqrt{m - a_c}] \ \textless \ = [\sqrt{m}] + ... + [\sqrt{m}] =$ $c[\sqrt{m}] \leq c\sqrt{m}$ , но так как m растёт быстрее, чем $c\sqrt{m}$ , то для некоторого m в промежутке [1...m] будут числа, не представимые в виде $x_i + z^2$ , приходим к противоречию, а значит утверждение задачи истинно. Замечание 1: понятно, что count >= чем чисел в промежутке [1, m], которые представимы как xi^2 + z^2. Замечание 2: [x] - целая часть числа х (или наибольшее целое число, не превосходящее x).