Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

19. Задачи на теорию чисел

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Решение задач на теорию чисел из ЕГЭ прошлых лет (страница 4)

Задание 22 #2921
Уровень задания: Равен ЕГЭ

На доске написаны числа \(1\) и \(2\). За один ход два числа \(m\) и \(n\), записанные на доске, заменяются на два числа \(2m + 2n - 1\) и \(3m + n - 4\) или \(2m + 2n - 1\) и \(3n + m - 4\).

а) Приведите пример последовательности ходов, после которых одно из двух чисел на доске окажется числом \(29\).

б) Может ли после \(100\) ходов одно из двух чисел на доске быть равно \(10^{30}\)?

в) Сделали \(2017\) ходов, причём на доске никогда не было написано одновременно двух равных чисел. Какое наименьшее значение может принимать разность большего и меньшего из полученных чисел?

а) В качестве ответа подходит следующая последовательность ходов:
0) \(\{1; 2\}\),
1) \(\{2\cdot 1 + 2\cdot 2 - 1 = 5; 3\cdot 1 + 2 - 4 = 1\}\),
2) \(\{2\cdot 5 + 2\cdot 1 - 1 = 11; 3\cdot 1 + 5 - 4 = 4\}\),
3) \(\{2\cdot 11 + 2\cdot 4 - 1 = 29; 3\cdot 4 + 11 - 4 = 19\}\).

б) Грубо говоря, начиная с некоторого момента после каждого хода минимальное из чисел на доске вырастает примерно в \(4\) раза по сравнению с минимальным числом до этого хода. Тогда после \(100\) ходов минимальное значение должно в некотором смысле не слишком сильно отличаться от \(1\cdot 4^{100} = 2^{200} = 1024^{20}\), что намного больше, чем \(1000^{10} = 10^{30}\). Данное рассуждение не является строгим, но именно его формальный аналог и приведёт нас к строгому решению.

 

Итак, изложим аналогичное решение формально. Пусть в какой-то момент каждое из чисел \(m\) и \(n\), записанных на доске, не меньше \(4\), тогда

\[\begin{aligned} &2n + 2m - 1 > 2n\geqslant \min(2m, 2n)\,,\\ &3m + n - 4 > 2m\geqslant \min(2m, 2n)\,,\\ &3n + m - 4 > 2n\geqslant \min(2m, 2n)\,. \end{aligned}\]

Таким образом, в любом случае после следующего хода оба числа на доске будут больше, чем минимальное из \(2m\) и \(2n\) (и опять будут не меньше \(4\)).

Покажем, что спустя \(2\) хода минимальное из чисел на доске обязательно будет не меньше \(4\). После первого хода мы получим либо \(\{5; 1\}\), либо \(\{5; 3\}\). Тогда после второго хода мы можем получить только одну из пар \[\{11; 4\},\qquad\qquad \{11; 12\},\qquad\qquad \{15; 10\},\qquad\qquad \{15; 14\}\]

То есть в результате второго хода каждое из чисел на доске так или иначе не меньше \(4\), следовательно, и далее оба числа на доске будут не меньше \(4\).

Получается, что после второго хода минимальное из чисел на доске не меньше \(4\), а с каждым ходом после второго минимальное из чисел на доске вырастает более чем в \(2\) раза по сравнению с минимальным числом до этого хода. Тогда после \(100\) ходов минимальное из чисел на доске будет больше, чем \(4\cdot 2^{98} = 2^{100} = 1024^{10} > 1000^{10} = 10^{30}\), следовательно, после \(100\) ходов ни одно из двух чисел на доске не может быть равно \(10^{30}\).

в) По условию эта разность не может быть равна \(0\). При этом оба числа на доске – натуральные, следовательно, разность большего и меньшего из них не меньше \(1\).

Рассмотрим повнимательнее преобразование, которое мы делаем с числами за один ход. Если до этого хода ровно одно из чисел было чётным, то после этого хода обязательно оба числа будут нечётными. Если же до этого хода оба числа были нечётными, то после этого хода ровно одно из чисел будет нечётным.

Тогда после одного хода, начиная с \(\{1; 2\}\), на доске оба числа будут нечётными, как и после трёх ходов и вообще после любого нечётного количества ходов. Так как \(2017\) – нечётное, то через \(2017\) ходов оба числа на доске будут нечётными, следовательно, разность между большим и меньшим из них не может быть равна \(1\).

В итоге, мы доказали, что разность между большим и меньшим из чисел на доске после \(2017\) ходов не меньше \(2\).

Пусть в какой-то момент на доске оказались числа, разность между большим и меньшим из которых равна \(1\). Пусть это числа \(n\) и \(n + 1\), тогда следующим ходом можно получить числа \(4n + 1\) и \(3(n + 1) + n - 4 = 4n - 1\) (разность между которыми равна \(2\)).

Пусть в какой-то момент на доске оказались числа, разность между большим и меньшим из которых равна \(2\). Пусть это числа \(k\) и \(k + 2\), тогда следующим ходом можно получить числа \(4k + 3\) и \(3(k + 2) + k - 4 = 4k + 2\) (разность между которыми равна \(1\)).

Так как в начальный момент на доске написаны числа, разность между которыми равна \(1\), то можно последовательно выполнять ходы, такие что разность между числами на доске будет чередоваться: то она равна \(1\), то равна \(2\). Следовательно, через \(2017\) ходов разность чисел на доске действительно может быть равна \(2\).

Ответ:

а) \(\{1; 2\}\mapsto \{5; 1\} \mapsto \{11; 4\} \mapsto \{29; 19\}\)

б) Нет

в) \(2\)

Задание 23 #2967
Уровень задания: Равен ЕГЭ

Дано трехзначное натуральное число (число не может начинаться с нуля).
а) Может ли частное этого числа и суммы его цифр быть равным \(20\)?
б) Может ли частное этого числа и суммы его цифр быть равным \(81\)?
в) Какое наименьшее натуральное значение может иметь частное данного числа и суммы его цифр?

 

(ЕГЭ 2013, основная волна)

а) Пусть число \(N=100a+10b+c\), где \(a,b,c\) – число сотен, десятков и единиц соответственно, следовательно, они могут принимать натуральные значения от \(0\) до \(9\) (только \(a\) не может быть равно \(0\)).

 

Предположим, что \[\dfrac{N}{a+b+c}=20 \quad\Rightarrow\quad 10(8a-b)=19c\] Пусть \(8a=b\), откуда, так как \(a,b\) – цифры, то \(a=1\) и \(b=8\). Тогда \(10(8a-b)=0\), следовательно, \(19c=0\), откуда \(c=0\). Таким образом, получили число \(180\).
Проверкой убеждаемся, что действительно \(180:(1+8+0)=20\).
Ответ: да.

б) Предположим, что \[\dfrac{N}{a+b+c}=81 \quad\Rightarrow\quad N=81(a+b+c)\] Следовательно, \(N\) делится на \(81\), следовательно, его можно представить в виде \(N=81\cdot k\), где \(k\) – некоторое натуральное число и \(k=a+b+c\). Заметим, что так как \(N\) – трехзначное число, то \(81\cdot k\leqslant 999\), откуда \(k\leqslant 12\).

 

Из того, что \(N\) делится на \(81\), можно сделать вывод, что \(N\) делится на \(9\). Следовательно, сумма его цифр должна делиться на \(9\). Но так как сумма его цифр равна \(k\), а \(k\leqslant 12\), то \(k=9\). Следовательно, \(N=9\cdot 81=729\). Но у числа \(729\) сумма цифр не равна \(9\), следовательно, \(729\) не подходит. Так как это был единственный возможной вариант, то ответ: нет.

 

в) Рассмотрим \(\dfrac{N}{a+b+c}\).

 

Попробуем поискать наименьшее трехзначное число с наибольшей суммой цифр. Значит, в нем должно быть мало сотен и много десятков и единиц. Возьмем \(198\). Сумма его цифр равна \(18\) и оно нацело делится на нее, в результате чего получаем \(11\).
Докажем, что \(11\) – наименьшее натуральное частное от деления числа на сумму его цифр.

 

Предположим противное. Пусть частное от деления \(N=100a+10b+c\) на \(a+b+c\) равно \(k\), где \(k\leqslant 10\) – натуральное число. Тогда: \[\dfrac{100a+10b+c}{a+b+c}=k \quad\Leftrightarrow\quad (100-k)a+(10-k)b=(k-1)c\]

Так как число сотен не может быть равно нулю, то \(a\geqslant 1\). Так как \(k\leqslant 10\), то \(100-k\geqslant 90\), следовательно, \((100-k)a\geqslant 90\). Так как \(b\geqslant 0\), то \((10-k)b\geqslant 0\), следовательно, вся левая часть равенства \(\geqslant 90\).

 

Так как число единиц не может быть больше \(9\), то есть \(c\leqslant 9\), и \(k-1\leqslant 9\), то \((k-1)c\leqslant 9\cdot 9=81\).

 

Следовательно, в нашем равенстве левая часть \(\geqslant 90\), а правая \(\leqslant 81\). Следовательно, равенство не имеет решений.
Значит, предположение неверно и \(11\) – наименьшее натуральное значение для частного трехзначного числа и суммы его цифр.

Ответ:

а) да

б) нет

в) 11