Задание 19 ЕГЭ профиль: Число ходов и наибольшее число

19.38.2.1.6 Числа и их свойства › Остаток не меняется при ходах с числами

Из пары натуральных чисел (a;b)( a ; b ) за один ход можно получить пару (a+2;b−1)( a + 2 ; b - 1 ) или (a−1;b+2)( a - 1 ; b + 2 ) при условии, что оба числа в новой паре положительны. Сначала есть пара (5;7)( 5 ; 7 ).

а) Можно ли за 50 таких ходов получить пару, в которой одно из чисел равно 100?

б) За какое число ходов получится пара, сумма чисел в которой равна 400?

в) Какое наибольшее число ходов можно сделать так, чтобы после каждого хода оба числа в паре не превосходили 100?

Источник: Открытый банк ФИПИ
Ответ и решение
  1. Обозначим ходы: AA: (a;b)→(a+2; b−1)(a;b)\to(a+2;\,b-1) и BB: (a;b)→(a−1; b+2)(a;b)\to(a-1;\,b+2). В обоих случаях сумма a+ba+b увеличивается ровно на 11, значит, после nn ходов сумма равна 12+n12+n.

    Авторский приём: в учебниках перечня этот шаг полностью не изложен.

  2. Ещё одно наблюдение: ход AA увеличивает разность a−ba-b на 33, ход BB уменьшает её на 33. Поэтому остаток от деления a−ba-b на 33 не меняется:

    a−b≡5−7=−2≡1(mod3).(1)a-b\equiv 5-7=-2\equiv 1\pmod 3.\quad(1)
    Как обычно, a≡ba \equiv b (mod pp) означает «aa и bb имеют равные остатки при делении на pp», или, что то же самое, a−b ⋮ pa - b \,\vdots\, p.
    Пособие. Вольфсон Г. И., Пратусевич М. Я., Рукшин С. Е., Столбов К. М., Ященко И. В. ЕГЭ 2019. Математика. Арифметика и алгебра. Задача 19, под ред. И. В. Ященко, МЦНМО, 2019, Решения задач диагностической работы, с. 5
    Сумма (произведение) чисел aa и bb даёт тот же остаток при делении на число mm, что и сумма (произведение) остатков чисел aa и bb при делении на число mm.
    Пособие. Вольфсон Г. И., Пратусевич М. Я., Рукшин С. Е., Столбов К. М., Ященко И. В. ЕГЭ 2019. Математика. Арифметика и алгебра. Задача 19, под ред. И. В. Ященко, МЦНМО, 2019, Краткая теоретическая справка, Теорема, с. 17

а) Можно ли за 5050 ходов получить пару, в которой одно из чисел равно 100100?

  1. После 5050 ходов сумма равна 12+50=6212+50=62. Оба числа натуральные, поэтому каждое из них меньше суммы, то есть меньше 6262.

    62<100.62<100.
  2. Значит, число 100100 получить нельзя.

Ответ а): нет\text{нет}

б) За сколько ходов сумма станет равной 400400?

  1. Сумма после nn ходов равна 12+n12+n, и она равна 400400 при n=400−12=388n=400-12=388 только при таком числе ходов. Такие ходы возможны: чередуя AA и BB (одна пара ходов ABAB даёт (a;b)→(a+1; b+1)(a;b)\to(a+1;\,b+1)), числа остаются положительными. Например, 194194 раза ABAB дают пару (199;201)(199;201) с суммой 400400.

Ответ б): 388388

в) Наибольшее число ходов, если после каждого хода оба числа не больше 100100

  1. Оба числа не больше 100100, поэтому сумма не больше 200200. Рассмотрим возможные суммы ss и пары (u;v)(u;v) с u,v≤100u,v\le 100 в порядке убывания ss.

    Авторский приём: в учебниках перечня этот шаг полностью не изложен.

  2. По (1) остаток u−vu-v при делении на 33 должен быть равен 11. Проверим суммы:

    s=200: пары (u;v), u,v≤100: (u;v)=(100;100), u−v=0≢1s=200:\ \text{пары }(u;v),\ u,v\le 100\text{: }(u;v)=(100;100),\ u-v=0\not\equiv 1s=199: (100;99), u−v=1≡1 подходитs=199:\ (100;99),\ u-v=1\equiv 1\ \text{подходит}
  3. Значит, наибольшая сумма равна 199199, и число ходов 199−12=187199-12=187. Покажем, что это достижимо: чтобы получить (100;99)(100;99), нужно сделать xx ходов AA и yy ходов BB, где a0+2x−y=100a_0+2x-y=100, b0−x+2y=99b_0-x+2y=99; отсюда x=94x=94, y=93y=93. Сделаем 9393 пары ходов ABAB (пара увеличивает оба числа на 11) и ещё 11 ход AA; все промежуточные числа положительны и не больше 100100.

Ответ в): 187187

Ответ: а) нет; б) 388; в) 187\text{а) нет; б) }388\text{; в) }187

Пособия: Вольфсон Г. И., Пратусевич М. Я., Рукшин С. Е., Столбов К. М., Ященко И. В. ЕГЭ 2019. Математика. Арифметика и алгебра. Задача 19, под ред. И. В. Ященко, МЦНМО, 2019, Решения задач диагностической работы; Вольфсон Г. И., Пратусевич М. Я., Рукшин С. Е., Столбов К. М., Ященко И. В. ЕГЭ 2019. Математика. Арифметика и алгебра. Задача 19, под ред. И. В. Ященко, МЦНМО, 2019, Краткая теоретическая справка, Теорема