Математика
Русский язык

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

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

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

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

На доске были написаны несколько натуральных чисел. Несколько раз с доски стирали по два числа, разность которых делится на \(5\).

а) Может ли сумма всех оставшихся на доске чисел равняться \(70\), если изначально на доске по одному разу были написаны все натуральные числа от \(27\) до \(38\) включительно?

б) Могло ли на доске остаться ровно два числа, произведение которых оканчивается на цифру \(6\), если изначально на доске по одному разу были написаны квадраты целых чисел от \(112\) до \(217\) включительно?

в) Пусть известно, что на доске осталось ровно два числа, а изначально по одному разу были написаны квадраты целых чисел от \(112\) до \(217\) включительно. Какое наибольшее значение может иметь отношение оставшихся на доске чисел?

Добавить задание в избранное

а) Достаточно стирать числа следующим образом: \[\{31; 36\},\quad \{30; 35\},\quad \{29; 34\},\quad \{28; 38\},\quad \{27,32\}\,,\] тогда на доске останутся \(33\) и \(37\), сумма которых и есть \(70\).

 

б) Рассмотрим отдельно процесс стирания чисел, кратных числу \(5\).

Так как \(5\) – простое, то квадрат числа делится на \(5\) тогда и только тогда, когда и само это число делится на \(5\). Итак, пусть \(n\in\mathbb{N}\), \((5n)^2\) – одно из чисел на доске (\(112 \leqslant 5n\leqslant 217\)). Пусть при этом число \((5n)^2\) было стёрто вместе с числом \(a^2\), тогда существует \(k\in\mathbb{Z}\), такое что \[(5n)^2 - a^2 = 5\cdot k\,,\] откуда следует, что \(a^2\) делится на \(5\), следовательно, и само \(a\) должно делиться на \(5\).

Итак, мы доказали, что числа, кратные пяти, могут стираться только в паре друг с другом. Но сколько их на доске? Их количество равно \((215 - 115) : 5 + 1 = 21\), то есть все такие числа в принципе нельзя стереть, так как одному из них обязательно не найдётся пары, ведь их количество нечётно.

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

 

в) В принципе наибольшее отношение могло бы быть \(\left(\dfrac{217}{112}\right)^2\), но мы знаем из решения пункта б), что из двух оставшихся чисел ровно одно делится на \(5\). Тогда наибольшее отношение может быть \(\left(\dfrac{215}{112}\right)^2\) или \(\left(\dfrac{217}{115}\right)^2\). Какое из этих чисел больше? Нетрудно убедиться, что \[\dfrac{215}{112} > \dfrac{217}{115}\qquad\Rightarrow\qquad \left(\dfrac{215}{112}\right)^2 > \left(\dfrac{217}{115}\right)^2\,.\]

Итак, большего отношения, чем \(\left(\dfrac{215}{112}\right)^2\), нам не получить. Попробуем получить хотя бы его.

Заметим теперь, что разность квадратов двух целых чисел делится на \(5\) тогда и только тогда, когда выполнено хотя бы одно из условий: 1) их сумма делится на \(5\), 2) их разность делится на \(5\). Таким образом, можно считать, что на доске выписаны сами числа от \(112\) до \(217\) включительно, но стирать можно пару, для которой выполнено хотя бы одно из условий 1), 2), а мы хотим оставить числа \(112\) и \(215\).

Для этого будем стирать числа следующим образом:

\[\begin{aligned} &\{113; 118\},\quad \{123; 128\},\quad \{133; 138\}, ...,\quad \{203; 208\} \\ &\{114; 119\},\quad \{124; 129\},\quad \{134; 139\}, ...,\quad \{204; 209\} \\ &\{115; 120\},\quad \{125; 130\},\quad \{135; 140\}, ...,\quad \{205; 210\} \\ &\{116; 121\},\quad \{126; 131\},\quad \{136; 141\}, ...,\quad \{206; 211\} \\ &\{117; 122\},\quad \{127; 132\},\quad \{137; 142\}, ...,\quad \{207; 212\} \end{aligned}\]

(здесь разность чисел в каждой паре делится на \(5\)). В первом столбце в итоге стираются все числа от \(113\) до \(122\) включительно. Во втором столбце стираются все числа от \(123\) до \(132\) включительно и т.д.

Теперь на доске остались числа \(112\), \(213\), \(214\), \(215\), \(216\) и \(217\). Избавиться от неугодных чисел можно так: \[\{213; 217\},\quad \{214; 216\}\] (здесь сумма чисел в каждой паре делится на \(5\)).

Итак, мы добились того, чего хотели, следовательно, ответ \[\left(\dfrac{215}{112}\right)^2\]

Ответ:

а) Да

б) Нет

в) \(\left(\dfrac{215}{112}\right)^2\)

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

Возрастающие арифметические прогрессии \(a_1, ..., a_n, ...\) и \(b_1, ..., b_n, ...\) состоят из целых положительных чисел.

а) Приведите пример таких прогрессий, для которых \(a_2b_2 + 3a_4b_4 = 5a_3b_3\).

б) Существуют ли такие прогрессии, для которых \(3a_2b_2 + a_6b_6 = 4a_3b_3\)?

в) Какое наибольшее значение может принимать произведение \(a_3b_3\), если \(3a_2b_2 + a_6b_6\leqslant 108\)?

Добавить задание в избранное

а) В качестве примера подходят прогрессии \(4, 5, 6, 7, ...\) и \(2, 3, 4, 5, ...\) (то есть \(a_1 = 4\), \(b_1 = 2\), а разности у обеих прогрессий равны \(1\)).

В самом деле, для таких прогрессий требуемое равенство превращается в \[5\cdot 3 + 3\cdot 7\cdot 5 = 5\cdot 6\cdot 4\] верное равенство.

б) Пусть разность прогрессии \(a_1, ...\) равна \(d\), а разность прогрессии \(b_1, ...\) равна \(\tilde{d}\). Тогда требуемое равенство можно переписать в виде \[3(a_3 - d)(b_3 - \tilde{d}) + (a_3 + 3d)(b_3 + 3\tilde{d}) = 4a_3b_3\]

Раскрывая скобки и приводя подобные слагаемые, получим \[12d\tilde{d} = 0\,,\] чего быть не может, ведь по условию обе прогрессии возрастают и состоят из целых положительных чисел, следовательно, \(d\geqslant 1\) и \(\tilde{d}\geqslant 1\), но тогда \(12d\tilde{d} \geqslant 12 > 0\,.\)

в) Аналогично пункту б) имеем \[3a_2b_2 + a_6b_6 = 3(a_3 - d)(b_3 - \tilde{d}) + (a_3 + 3d)(b_3 + 3\tilde{d}) = 4a_3b_3 + 12d\tilde{d}\,.\]

Таким образом, условие пункта в) равносильно условию \[4a_3b_3 + 12d\tilde{d}\leqslant 108\qquad\Leftrightarrow\qquad a_3b_3 + 3d\tilde{d}\leqslant 27\,.\]

Так как \(d\geqslant 1\) и \(\tilde{d}\geqslant 1\), то получаем оценку сверху: \[a_3b_3\leqslant 24 = 6\cdot 4\,.\]

Покажем, что эта оценка достигается: рассмотрим прогрессии \(4, 5, 6, 7, 8, 9, ...\) и \(2, 3, 4, 5, 6, 7, ...\), тогда \[3a_2b_2 + a_6b_6 = 3\cdot 5\cdot 3 + 9\cdot 7 = 108\,,\] следовательно, условие задачи выполнено и \(24\) действительно является наибольшим возможным значением для \(a_3\cdot b_3\).

Ответ:

а) \(4, 5, 6, 7, ...\) и \(2, 3, 4, 5, ...\)

б) Нет

в) \(24\)

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

Пусть \(n\) – трёхзначное натуральное число, в десятичной записи которого нет нулей.

а) Приведите пример такого \(n\), что его отношение к произведению его цифр равно \(\dfrac{109}{18}\).

б) Может ли отношение \(n\) к произведению его цифр быть равно \(\dfrac{113}{18}\)?

в) Какое наибольшее значение может принимать отношение \(n\) к произведению его цифр, если оно равно несократимой дроби со знаменателем \(18\)?

Добавить задание в избранное

а) Покажем, что \(n = 763\) подходит: произведение цифр \(n\) равно \(7\cdot 6\cdot 3\), тогда отношение \(n\) к произведению его цифр равно \[\dfrac{763}{7\cdot 6\cdot 3} = \dfrac{109}{6\cdot 3} = \dfrac{109}{18}\]

б) Числа \(113\) и \(18\) взаимно просты, тогда для того, чтобы отношение \(n\) к произведению его цифр было равно \(\dfrac{113}{18}\), необходимо, чтобы \(n\) делилось на \(113\).

Таким образом, если какое-то \(n\) подходит, то оно имеет вид \(n = 113 k\), где \(k\in\{1, ..., 8\}\) (так как \(113\cdot 9 = 1017\) – уже не трёхзначное).

Перебором убеждаемся, что ни одно число из множества \(\{1, ..., 8\}\) не подходит на роль \(k\), следовательно, отношение \(n\) к произведению его цифр не может быть равно \(\dfrac{113}{18}\).

в) Такое отношение по крайней мере может быть равно \(\dfrac{631}{18}\) (при \(n = 631\)), но может ли оно быть ещё больше? Если при каком-то \(n\) оно оказалось ещё больше, необходимо, чтобы произведение цифр \(n\) и было равно \(18\).

В самом деле, произведение цифр \(n\) должно делиться на \(18\), раз уж отношение \(n\) к нему можно сократить до дроби вида \(\dfrac{m}{18}\), но если \(n < 1000\), то даже при сокращении числителя всего в \(2\) раза там останется \(n : 2 < 500\), а в предложенном выше примере в числителе стоит \(631 > 500\), то есть предложенный выше пример даёт заведомо большее отношение, чем любое допустимое отношение, для которого произведение цифр \(n\) было не \(18\).

Теперь разберёмся со случаем, когда произведение цифр \(n\) равно \(18 = 3\cdot 3\cdot 2\). Тогда наибольшее значение, которое может принимать число сотен в \(n\), равно \(3\cdot 3 = 9\), но чтобы произведение цифр было равно \(18\), нам придётся взять в качестве двух других цифр \(2\) и \(1\). При этом всякое трёхзначное число, записанное полученными цифрами, делится на \(3\) и дробь \(\dfrac{n}{18}\) оказывается сократимой.

Наибольшее значение, которое может принимать число сотен в \(n\), отличное от \(9\), равно \(3\cdot 2 = 6\), тогда нам придётся взять в качестве двух других цифр \(3\) и \(1\). Ну а наибольшее такое \(n\), собственно, и есть \(631\).

Ответ:

а) \(763\)

б) Нет

в) \(\dfrac{631}{18}\)

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

На доске написаны числа \(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\)

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

Дано трехзначное натуральное число (число не может начинаться с нуля).
а) Может ли частное этого числа и суммы его цифр быть равным \(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

1 2 3