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

а) Когда в задаче дается набор различных натуральных чисел, а также дается либо сумма чисел, либо их среднее арифметическое (зная среднее арифметическое чисел и их количество, можно легко посчитать их сумму), как правило, работает классическая идея минимальной суммы.
Предположим, что наименьшее число равно 3. Тогда наименьшая возможная сумма шести наименьших чисел равна \(3+4+5+6+7+8=33\). Тогда наименьшее среднее арифметическое шести наименьших чисел равно \(\frac{33}6>5\).
Мы взяли шесть самых маленьких различных натуральных чисел при условии, что наименьшее из них равно 3. И если их среднее арифметическое оказалось больше 5, то и среднее арифметическое шести любых различных натуральных чисел, наименьшее из которых равно 3, будет больше 5.
Следовательно, мы получили противоречие, значит, наименьшее число в наборе не может быть равно 3.

б) Пусть мы имеем набор упорядоченных по возрастанию чисел \(a_1, a_2, \dots, a_{10}\). Так как \((a_1+a_2+\dots+a_6):6=5\), то \(a_1+\dots +a_6=30\). Аналогично \(a_5+a_6+\dots a_{10}=90\). Тогда \(a_1+a_2+\dots +a_{10}+(a_5+a_6)=120\).
Наименьшее возможное значение \(a_5\) – это 5, так как числа натуральные и различные и они упорядочены по возрастанию. Тогда самое маленькое возможное значение \(a_6\) – это 6. Но тогда наибольшая возможная сумма \(a_1+\dots +a_{10}=120-(5+6)=109\). Но тогда наибольшее возможное среднее арифметическое всех десяти чисел равно \(109:10=10,9<11\). Следовательно, среднее арифметическое всех чисел не может быть равно 11.

в) В предыдущем пункте мы сказали, что \(a_1+a_2+\dots +a_{10}=120-(a_5+a_6)\). Следовательно, для того, чтобы найти наибольшую возможную сумму всех чисел, нужно найти наименьшую возможную сумму \(a_5+a_6\).
Ранее мы доказали, что минимальная сумма \(a_5+a_6=11\). Заметим, что, учитывая условие, что сумма наименьших шести чисел равна 30, такая ситуация невозможна: наибольшее возможное \(a_5\) тогда равно 5, значит, наибольшая возможная сумма первых четырех чисел равна \(1+2+3+4=10\), откуда мы получаем, что наибольшая сумма первых шести чисел равна \(1+2+3+4+5+6<30\).
Рассмотрим случаи:

1) Пусть \(a_5+a_6=12\). Тогда \(a_1+a_2+a_3+a_4=18\). Тогда наибольшее возможное значение для \(a_5\) – это 5. Следовательно, наибольшая возможная сумма первых четырех чисел равна \(1+2+3+4<18\). Следовательно, такой случай невозможен.

2) Пусть \(a_5+a_6=13\). Тогда \(a_1+a_2+a_3+a_4=17\). Тогда наибольшее возможное значение для \(a_5\) – это 6. Следовательно, наибольшая возможная сумма первых четырех чисел равна \(2+3+4+5<17\). Следовательно, такой случай невозможен.

3) Пусть \(a_5+a_6=14\). Тогда \(a_1+a_2+a_3+a_4=16\). Тогда наибольшее возможное значение для \(a_5\) – это 6. Следовательно, наибольшая возможная сумма первых четырех чисел равна \(2+3+4+5<16\). Следовательно, такой случай невозможен.

4) Пусть \(a_5+a_6=15\). Тогда \(a_1+a_2+a_3+a_4=15\). Тогда наибольшее возможное значение для \(a_5\) – это 7. Следовательно, наибольшая возможная сумма первых четырех чисел равна \(3+4+5+6=18\). Это не больше 15, следовательно, противоречия мы не получили. Попробуем построить пример.
Возьмем \(a_5=7, a_6=8\). Возьмем также \(a_1=2, a_2=3, a_3=4, a_4=6\). Тогда действительно \(a_1+\dots +a_6=2+3+4+6+7+8=30\).
Подберем последние четыре числа: \(a_7=9, a_8=10, a_9=11, a_{10}=45\). Действительно \(a_5+\dots +a_{10}=90\).
Пример приведен, следовательно, наибольшая возможная сумма десяти чисел равна \(120-15=105\). Тогда наибольшее вреднее арифметическое всех чисел равно \(10,5\).

Ответ:

а) нет

б) нет

в) 10,5

а) Предположим, что существуют такие \(x,y\), что \(q:d=204\).
Рассмотрим самый простой случай, когда \(d=1\), то есть числа взаимно просты. Тогда \(q=204\).
Так как \(q\cdot d=x\cdot y\), то получаем: \(xy=204\).
Заметим, что \(204=2^2\cdot 3\cdot 17\). Следовательно, нужно составить из множителей \(2, 2, 3, 17\) такие числа \(x\) и \(y\), чтобы их НОД был равен \(1\), и они подходили в \(7x=16y-73\). Перебором убеждаемся, что подходят \(x=17\) и \(y=12\).
Ответ: да.

б) Выпишем решения уравнения \(7x=16y-73\) в натуральных числах. Выразим: \[x=\dfrac{16y-73}7=2y-10+\dfrac{2y-3}7\] Чтобы \(x\) был натуральным, как минимум нужно, чтобы \(\frac{2y-3}7\) было целым числом. Это возможно только тогда, когда \(2y-3\) делится без остатка на \(7\). Все возможные остатки при делении \(y\) на \(7\) – это \(0, 1, 2, 3, 4, 5, 6\). Заметим, что нам подходит только случай, когда \(y\) при делении на \(7\) дает в остатке \(5\), то есть \(y=7k+5\) (\(k\geqslant 0\)). Тогда \[x=2(7k+5)-10+\dfrac{2(7k+5)-3}7=16k+1, k\geqslant 0\] Таким образом, решением уравнения \(7x=16y-73\) будут \(x=16k+1, y=7k+5\), \(k\geqslant 0\).

Предположим, что существуют такие \(x,y\), что \(q:d=2\).

1) Если \(d=1\), то \(q=2\). Следовательно, аналогично пункту а), \(2=q=xy\).
Заметим, что так как \(k\geqslant 0\), то \(xy\geqslant (0+1)(0+5)=5\). Следовательно, \(q\) не может быть равно \(2\). Получили противоречие.

2) Пусть \(d>1\). Следовательно, можно записать \(x=ds\), \(y=dr\) (\(s,r\) – натуральные). И тогда уравнение \(7x=16y-73\) перепишется как \(d(16r-7s)=73\). Тогда, так как \(d, r, s\) – натуральные числа, то \(73\) должно делиться на \(d\). Но \(73\) – простое число, и делится только на \(1\) или на \(73\). Следовательно, \(d=73\). Тогда \(16r-7s=1\). Полученное уравнение также можно решить в натуральных числах (аналогично пункту б)) и получить решения \(r=7p+4\), \(s=16p+9\), \(p\geqslant 0\).
Следовательно, \(x=73(16p+9)\), \(y=73(7p+4)\), \(p\geqslant 0\).
Тогда \(2\cdot 73^2=\frac qd\cdot d^2=qd=xy\).
Но \(xy\geqslant 73(0+9)\cdot 73(0+4)=73^2\cdot 9\cdot 4\), а это явно больше \(2\cdot 73^2\). Следовательно, также получили противоречие.
Ответ: нет.

в) Заметим, что в пункте б) мы доказали, что существует лишь два варианта, чему может быть равно \(d\): либо \(1\), либо \(73\). Причем:

1) если \(d=1\), то \(xy\geqslant 5\). Значит, \(q:d=q=xy\geqslant 5\), то есть минимальное значение для \(q:d=5\).

2) если \(d=73\), то \(xy\geqslant 73^2\cdot 9\cdot 4\). Значит, \(q:d=xy:d^2\geqslant73^2\cdot 9\cdot 4:73^2=36\). То есть минимальное значение для \(q:d\) равно \(36\).

Таким образом, мы видим, что минимально возможное значение для \(q:d\) равно \(5\).
Приведем пример.
Этот минимум мы получили из случая, когда \(d=1\) и \(x=16k+1\), \(y=7k+5\) при \(k=0\). Следовательно, пример: \(x=1, y=5\).

Ответ:

а) да

б) нет

в) 5

а) Пусть \(a_1=x\), \(a_2=y\). Тогда \(a_3=x+y, a_4=x+2y, a_5=2x+3y\). Предположим, что выполняется \(4a_5=7a_4\). Тогда: \[4(2x+3y)=7(x+2y)\quad\Leftrightarrow\quad x=2y\] Если взять, например, \(x=2\), \(y=1\), то получим последовательность: \(2, 1, 3, 4, 7, \dots\) Следовательно, такое возможно.

б) Аналогично пункту а): \[5(2x+3y)=7(x+2y)\quad\Leftrightarrow\quad 3x=-y\] Следовательно, один из \(x\) или \(y\) должен быть отрицательным (оба они не могут быть равны \(0\), так как последовательность состоит из натуральных чисел). Но это невозможно, так как последовательность состоит из натуральных чисел. Следовательно, ответ: нет.

в) Отметим основные свойства последовательности, где \(a_{n+1}=a_n+a_{n-1}\) при натуральных \(n\geqslant 2\). Заметим, что первые два элемента этой последовательности задаются произвольно, а вот каждый следующий, начиная с третьего, равен сумме двух предыдущих. Следовательно, так как последовательность состоит из натуральных чисел, то каждый элемент, начиная с третьего, больше предыдущего, то есть \(a_{n+1}:a_n>1\) при \(n\geqslant 2\).
Это же свойство можно переформулировать по-другому: каждый элемент, начиная со второго, меньше следующего: \(a_n:a_{n+1}<1\) при \(n\geqslant 2\).
Но тогда \[\dfrac{a_{n+1}}{a_n}=1+\dfrac{a_{n-1}}{a_n}<1+1=2, \quad n\geqslant 3\] (каждый элемент, начиная с 4-ого, менее чем в два раза больше предыдущего)

Предположим, что равенство \(6na_{n+1}=(n^2+24)a_n\) вплоть до какого-то большого \(n\) (то есть \(n\geqslant 3\)). Тогда \[\dfrac{a_{n+1}}{a_n}=\dfrac{n^2+24}{6n}<2\] Решим неравенство: \[\dfrac{n^2+24}{6n}<2\quad\Rightarrow\quad n^2-12n+24<0 \quad\Leftrightarrow\quad n\in (6-\sqrt{12};6+\sqrt{12})\] Так как \(n\) – натуральное, а \(9<6+\sqrt{12}<10\), то \(n\leqslant 9\).
Следовательно, наибольший элемент, для которого может быть выполнено равенство из пункта в), это \(a_{10}\).
Попробуем привести пример. Для этого нам понадобиться равенство \(a_{n+2}=a_{n+1}+a_n\) использовать в виде \(a_n=a_{n+2}-a_{n+1}\), а также то, что каждый элемент последовательности, начиная с третьего, должен быть больше предыдущего.

Пусть \(n=9\). Тогда \[\begin{aligned} &6\cdot 9\cdot a_{10}=105a_9\\ &18a_{10}=35a_9\quad\Rightarrow\\ &a_{10}=35k\\ &a_9=18k\\ &a_8=17k\\ &a_7=k\\ &a_6=16k\end{aligned}\] Получили, что \(a_6>a_7\) – противоречие.

Пусть \(n=8\). Тогда \[\begin{aligned} &6\cdot 8\cdot a_9=88a_8\\ &6a_9=11a_8\quad\Rightarrow\\ &a_9=11k\\ &a_8=6k\\ &a_7=5k\\ &a_6=k\\ &a_5=4k\end{aligned}\] Получили противоречие.

Пусть \(n=7\). Тогда \[\begin{aligned} &6\cdot 7\cdot a_8=73a_7\quad\Rightarrow\\ &a_8=73k\\ &a_7=42k\\ &a_6=31k\\ &a_5=11k\\ &a_4=20k\end{aligned}\] Получили противоречие.

Пусть \(n=6\). Тогда \[\begin{aligned} &6\cdot 6\cdot a_7=60a_6\\ &3a_7=5a_6\quad\Rightarrow\\ &a_7=5k\\ &a_6=3k\\ &a_5=2k\\ &a_4=k\\ &a_3=k\end{aligned}\] Получили противоречие.

Пусть \(n=5\). Тогда \[\begin{aligned} &6\cdot 5\cdot a_6=49a_5\quad\Rightarrow\\ &a_6=49k\\ &a_5=30k\\ &a_4=19k\\ &a_3=11k\\ &a_2=8k\\ &a_1=3k\end{aligned}\] Противоречия нет, следовательно, наибольшее возможное \(n\) – это \(n=5\). Пример: \(3; 8; 11; 19; 30; 49\).

Ответ:

а) да

б) нет

в) 5

а) Так как \(4+7=11\), то первая цифра искомого числа \(4\), вторая \(7\): \(47...\)
Так как \(7+1=8\), то третья цифра – это \(1\): \(471...\)
Аналогично четвертая, последняя, цифра числа – это \(9\).
Таким образом, число \(4719\).

б) Предположим, что такое число существует. Начнем так же, как в пункте а), определять цифры этого числа слева направо. Очевидно, что первые две цифры – это \(2\) и \(8\), то есть число \(28...\)
Третья цифра не может быть \(1\), так как \(8+1\ne 1\), также третья цифра не может быть \(4\), так как \(8+4\ne 11\). Также она не может быть равна \(9\) или \(5\), так как в этом случае сумма двух цифр уже должна быть равна трех- или четырехзначному числу.
Следовательно, ответ: нет.

в) Пусть дано трехзначное число \(\overline{abc}\). Тогда из него получится число \(N=\overline{a\,(a+b)\,b\,(b+c)\,c}\).
Заметим, что при \(a+b\geqslant 10\) и \(b+c\geqslant 10\) данное число будет семизначным, а во всех остальных случаях — шести- или пятизначным. Таким образом, так как мы ищем наибольшее возможное число, то найдем его среди семизначных чисел.
Пусть \(a+b=10+x, b+c=10+y\), где \(0\leqslant x,y\leqslant 6\) (так как \(a, b, c\ne 9\)).
Тогда число имеет вид: \(N=\overline{a1xb1yc}\).
По признаку делимости число делится на \(9\) тогда и только тогда, когда сумма его цифр кратна \(9\). То есть: \[a+1+x+b+1+y+c \ \vdots \ 9\] Так как \(x=a+b-10\), \(y=b+c-10\), то получаем: \[a+1+a+b-10+b+1+b+c-10+c \ \vdots \ 9\quad\Rightarrow\quad 2a+3b+2c-2\cdot 9 \ \vdots \ 9 \quad\Rightarrow\quad 2a+3b+2c \ \vdots \ 9\] Для того, чтобы число \(N\) было наибольшим, его первая цифра должна быть наибольшей. Следовательно, если возьмем наибольшее возможное \(a=8\), тогда можно взять наибольшее возможное \(b=8\). Следовательно, для того, чтобы \(2a+3b+2c \ \vdots \ 9\), нужно взять \(c=7\).
Таким образом, наибольшее число получится из числа \(887\) и равно \(N=8168157\).

Ответ:

а) 4719

б) нет

в) 8168157

а) Так как \(1+6=7\), то первая цифра искомого числа \(1\), вторая \(6\): \(16...\)
Так как \(6+8=14\), то третья цифра – это \(8\): \(168...\)
Аналогично четвертая, последняя, цифра числа – это \(9\).
Таким образом, число \(1689\).

б) Предположим, что такое число существует. Начнем так же, как в пункте а), определять цифры этого числа слева направо. Очевидно, что первые две цифры – это \(3\) и \(7\), то есть число \(37...\)
Третья цифра не может быть \(1\), так как \(7+1\ne 6\) и \(7+1\ne 61\). Также она не может быть равна \(0\), \(9\) или \(0\), так как в этом случае сумма двух цифр уже должна быть равна трех-, четырех- или пятизначному числу.
Следовательно, ответ: нет.

в) Пусть дано трехзначное число \(\overline{abc}\). Тогда из него получится число \(N=\overline{a\,(a+b)\,b\,(b+c)\,c}\).
Заметим, что при \(a+b\geqslant 10\) и \(b+c\geqslant 10\) данное число будет семизначным, а во всех остальных случаях — шести- или пятизначным. Таким образом, так как мы ищем наибольшее возможное число, то найдем его среди семизначных чисел.
Пусть \(a+b=10+x, b+c=10+y\), где \(0\leqslant x,y\leqslant 8\).
Тогда число имеет вид: \(N=\overline{a1xb1yc}\).
По признаку делимости число делится на \(11\) тогда и только тогда, когда сумма его цифр, стоящих на нечетных местах, минус сумма цифр, стоящих на четных местах, кратна \(11\). То есть: \[(a+x+1+c)-(1+b+y):11\] Так как \(x=a+b-10\), \(y=b+c-10\), то получаем: \[(a+a+b-10+1+c)-(1+b+b+c-10):11\quad\Rightarrow\quad 2a-b:11\] Для того, чтобы число \(N\) было наибольшим, его первая цифра должна быть наибольшей. Следовательно, если \(a=9\), то \(b=7\) (чтобы \(2a-b:11\)). Заметим, что \(c\) может быть любым. Следовательно, возьмем максимальное \(c=9\).
Таким образом, наибольшее число получится из числа \(979\) и равно \(N=9167169\).

Ответ:

а) 1689

б) нет

в) 9167169

а) Очевидно, что в нашем задуманном наборе чисел должны быть числа \(2, 3, 5\). Для того, чтобы на доске появилось число \(9\), в нашем наборе либо должна быть \(9\), либо еще одна \(3\).
Рассмотрим набор \(2, 3, 5, 9\). Так как на доске должны быть записаны все попарные произведения, то на доске должно быть число \(3\cdot 9=27\). Его там нет. Следовательно, этот набор невозможен.
Рассмотрим набор \(2, 3, 3, 5\). Проверкой убеждаемся, что он нам подходит.
Ответ: \(2, 3, 3, 5\).

б) Очевидно, что в задуманном наборе должны быть числа \(3, 5, 7\). Для того, чтобы на доске была написана \(9\), нужно, чтобы в нашем наборе была либо \(9\), либо еще одна \(3\).
Рассмотрим последнее написанное на доске число: \(945=7\cdot 3\cdot 3\cdot 3\cdot 5\). Заметим, что последнее записанное на доске число – это всегда произведение всех задуманных чисел.
Следовательно, либо этот набор точно содержит числа \(3, 5, 7, 9\), либо содержит \(3, 3, 3, 5, 7\).
Пусть в задуманном наборе как минимум есть числа \(3, 3, 3, 5, 7\). Тогда на доске должно быть записано число \(3\cdot 3\cdot 3=27\), которого там нет. Следовательно, набор с такими числами точно не может быть задуман.
Пусть в задуманном наборе как минимум есть числа \(3, 5, 7, 9\). Проверим, подходит ли он. Тогда на доске, например, должно быть число \(7\cdot 9=63\). А его там нет. Следовательно, набор не подходит.
Ответ: нет.

в) Как уже говорилось в п. б), наибольшее число на доске – это произведение всех задуманных чисел. Следовательно, \(82=2\cdot 41\) (разложили на простые множители) – произведение всех чисел.
Таким образом, либо у нас набор \(82, 1, 1, 1, 1, 1\), либо \(2, 41, 1, 1, 1, 1\).
Если бы в наборе было какое-то число, отличное от \(1, 2, 41\) и \(82\), то оно было бы делителем \(82\). А мы уже выяснили, что у \(82\) делители только \(1, 2, 41, 82\).

Ответ:

а) 2, 3, 3, 5

б) нет

в) 1, 1, 1, 1, 1, 82 или 1, 1, 1, 1, 2, 41

а) Заметим, что среди красных чисел также могут встречаться числа, кратные \(3\). Например, число \(24\) может встретиться в списке два раза: один раз как красное, второй – как зеленое.

Так как \(1395=3+6+\dots+90\), и чисел \(3, 6, \dots, 90\) – ровно тридцать штук, и они все кратны \(3\), то уберем из них, например, число \(90\), а вместо него возьмем число \(24\) (которое будет красным). Тогда мы получим 29 зеленых чисел: \(3, 6, \dots, 87\) и одно красное \(24\) (кратное \(3\)), причем очевидно, что сумма всех чисел будет строго меньше \(1395\).
Ответ: да.

б) Упорядочим зеленые числа по возрастанию. Тогда наименьшее возможное значение первого числа – это \(3\), второго – это \(6\) и т.д. Наименьшее значение последнего, тридцатого числа, это \(87\). Сумма всех этих чисел равна \(1305\) – и это наименьшее возможное значение суммы 29-ти зеленых чисел. Следовательно, если сумма всех чисел равна \(1066\), то красное число должно быть отрицательным, что невозможно. Ответ: нет.

в) Докажем, что наименьшее возможное количество красных чисел – это 7.
Рассмотрим минимальное значение для суммы всех чисел для всех случаев, когда красных чисел от 2 до 6 (то, что на доске не может быть написано одно красное число, мы рассмотрели в пункте б)). Оформим это в таблице: \[\begin{array}{|c|c|c|} \hline \text{зеленые} & \text{красные} & \text{минимальная сумма}\\ \hline 28 \ \text{чисел} & 2 \ \text{числа} & 1242\\ 3, 6, \dots, 84 & 8, 16 & \\ \hline 27 \ \text{чисел} & 3 \ \text{числа} & 1182\\ 3, 6, \dots, 81 & 8, 16, 24 &\\ \hline 26 \ \text{чисел} & 4 \ \text{числа} & 1133\\ 3, 6, \dots, 78 & 8, 16, 24, 32 &\\ \hline 25 \ \text{чисел} & 5 \ \text{чисел} & 1095\\ 3, 6, \dots, 75 & 8, 16, 24, 32, 40 &\\ \hline 24 \ \text{числа} & 6 \ \text{чисел} & 1068\\ 3, 6, \dots, 72 & 8, 16, 24, 32, 40, 48 &\\ \hline \end{array}\] То есть мы брали самые маленькие зеленые числа и самые маленькие красные числа и общая сумма чисел получалась больше \(1066\). Следовательно, для любых наборов красных и зеленых чисел, где красных чисел от 2 до 6, общая сумма чисел будет больше, чем \(1066\).

Итак, мы имеем пример для 6 красных чисел, когда сумма всех чисел (зеленых и красных) равна \(1068\). Нужно добавить одно красное число и убрать одно зеленое так, чтобы общая сумма чисел стала равна \(1066\). Для этого нужно убрать одно зеленое число, которое больше добавленного красного числа на \(2\). Теперь смотрим: если мы добавим красное \(56\), то нам нужно убрать зеленое \(58\). Но такого числа среди зеленых нет.
Перебираем дальше: если добавить красное \(64\), то убрать нужно зеленое \(66\), которое как раз у нас имеется! Таким образом, мы построили пример, когда на доске написано 7 красных чисел: \[\begin{array}{|c|c|c|} \hline \text{зеленые} & \text{красные} & \text{сумма}\\ \hline 23 \ \text{числа} & 7 \ \text{чисел} & 1066\\ 3, 6, \dots ,63, 69, 72 & 8, 16, 24, 32, 40, 48, 64 & \\ \hline \end{array}\]

Ответ:

а) да

б) нет

в) 7