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

а) Пусть число \(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

Пусть \(i-\)ое выписанное число имеет вид \(10\cdot a_i + b_i\), где \(a_i, b_i \in \{1, 2, ..., 9\}\). Для суммы \(b_i\) по всем значениям индекса \(i\), таким, что слагаемое \(b_i\) есть этой в сумме, используем обозначение \(\underset{i}{\Sigma} b_i\).

Тогда сумма всех исходных чисел имеет вид \[\underset{i}{\Sigma} (10a_i + b_i) = 10\cdot\underset{i}{\Sigma} a_i + \underset{i}{\Sigma} b_i.\] Обозначим \(A = \underset{i}{\Sigma} a_i\), \(B = \underset{i}{\Sigma} b_i\), тогда \(2970 = 10\cdot A + B\).

После смены мест цифр \(i-\)ое полученное число имеет вид \(10\cdot b_i + a_i\). Тогда сумма всех полученных чисел имеет вид \[\underset{i}{\Sigma} (10b_i + a_i) = 10\cdot\underset{i}{\Sigma} b_i + \underset{i}{\Sigma} a_i = 10\cdot B + A.\]

а) Уменьшение суммы в 3 раза равносильно тому, что новая сумма равна \(\dfrac{2970}{3} = 990\), что равносильно \(10\cdot B + A = 990\). Рассмотрим систему

\[\begin{aligned} \begin{cases} 10\cdot A + B = 2970\\ A + 10\cdot B = 990 \end{cases} \end{aligned}\]

вычитая из первого уравнения второе, находим, что \(9\cdot A - 9\cdot B = 1980\), откуда \(A = 220 + B\). Подставляя это в первое уравнение системы, находим \(B = 70\), тогда \(A = 290\).

Попробуем брать в качестве \(a_i\) 9, пока их сумма не превосходит 290 – так можно положить \[a_1 = ... = a_{32} = 9,\quad a_{33} = 290 - 32\cdot 9 = 2,\] то есть в сумме 33 слагаемых. Тогда можно положить \[b_1 = ... = b_{32} = 2,\quad b_{33} = 70 - 32\cdot 2 = 6.\]

б) Уменьшение суммы в 5 раза равносильно тому, что новая сумма равна \(\dfrac{2970}{5} = 594\), что равносильно \(10\cdot B + A = 594\). Рассмотрим систему

\[\begin{aligned} \begin{cases} 10\cdot A + B = 2970\\ A + 10\cdot B = 594 \end{cases} \end{aligned}\]

вычитая из первого уравнения второе, находим, что \(9\cdot A - 9\cdot B = 2376\), откуда \(A = 264 + B\). Подставляя это в первое уравнение системы, находим \(B = 30\), тогда \(A = 294\).

Так как \(B = 30\), а все \(b_i\geqslant 1\), то слагаемых в сумме не более 30, но тогда \(A\leqslant 30\cdot 9 = 270\), следовательно, при \(B = 30\) не может быть выполнено \(A = 294\).

в) Пусть сумма полученных чисел равна \(S\), что равносильно системе

\[\begin{aligned} \begin{cases} 10\cdot A + B = 2970\\ A + 10\cdot B = S \end{cases} \end{aligned}\]

вычитая из первого уравнения второе, находим, что \(9\cdot A - 9\cdot B = 2970 - S\), откуда \[A = 330 - \dfrac{S}{9} + B.\] Подставляя это в первое уравнение системы, находим \[B = \dfrac{10\cdot S}{99} - 30,\] откуда в частности следует, что \(S\) делится на \(99\).

Понятно, что \(B > 30\) (так как все \(b_i\geqslant 1\), то при не более чем \(30\) слагаемых сумма исходных чисел не превзойдёт \(30\cdot 90 + 30 = 30\cdot 91 < 2970\)). Тогда \[\dfrac{10\cdot S}{99} - 30 > 30,\] откуда \(S > 594\), но \(S\) делится на \(99\), тогда \(S\geqslant 693\).

При \(S = 693\) получим \(B = 40\), откуда \(A = 293\).

Аналогично примеру из пункта а) построим решение:

Попробуем брать в качестве \(a_i\) 9, пока их сумма не превосходит 293 – так можно положить \[a_1 = ... = a_{32} = 9,\quad a_{33} = 293 - 32\cdot 9 = 5,\] то есть в сумме 33 слагаемых. Тогда можно положить \[b_1 = ... = b_{32} = 1,\quad b_{33} = 40 - 32\cdot 1 = 8,\] итого, искомая сумма \(32\times 91 + 58\).

Ответ:

а) \(32\times 92 + 26\), где запись \(32\times 92\) означает сумму из 32 слагаемых, каждое из которых равно 92.

б) Нет.

в) \(693\).

а) В качестве примера подходят прогрессии \(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\)

а) Достаточно стирать числа следующим образом: \[\{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\)

а) Данное множество состоит из 100 подряд идущих натуральных чисел, тогда его можно разбить на 50 пар с одинаковыми суммами: \(\{100; 199\}, \{101; 198\}, ..., \{149; 150\}\).

Так как количество таких пар 50 (важно, что оно чётно), то можно составить первое подмножество из всех элементов любых 25 из этих пар, а второе подмножество взять содержащим все остальные числа.

б) Данное множество не является хорошим, так как \(2^{200}\) больше суммы всех остальных его элементов. Это следует из формулы \[1 + 2 + ... + 2^{n-1} = 2^n - 1.\] Покажем по индукции, что эта формула верна.

1) При \(n = 1\) имеем: \(1 = 2^1 - 1\) – верно.

2) Пусть теперь формула верна для \(n = m\), покажем, что тогда она верна и для \(n = m + 1\): \[1 + 2 + ... + 2^{(m + 1) - 1} = 1 + 2 + ... + 2^{m - 1} + 2^m.\] По предположению индукции сумма всех слагаемых без последнего равна \(2^m - 1\), тогда вся сумма равна \[2^m - 1 + 2^m = 2\cdot 2^m - 1 = 2^{m + 1} - 1,\] что и требовалось. Ну а сумма \[2 + 4 + 8 + ... + 2^{199} = -1 + 1 + 2 + 4 + 8 + ... + 2^{199} = -1 + 2^{200} - 1 = 2^{200} - 2 < 2^{200}.\]

в) Для элементов хорошего четырёхэлементного подмножества должно выполняться либо равенство вида \[a + b + c = d,\] либо равенство вида \[a + b = c + d.\]

Равенство \(a + b + c = d\) может быть выполнено только в случае \(3 + 4 + 5 = 12\) (сумма любых трёх других элементов больше любого элемента данного множества). Рассмотрим теперь случай равенства вида \(a + b = c + d\).

В данном множестве всего два нечётных элемента. Для хорошего четырёхэлементного подмножества понятно, что они либо оба содержатся в нём, либо оба не содержатся в нём.

Рассмотрим подходящие четырёхэлементные подмножества, содержащие \(3\) и \(5\). Так как \(3 + 5 = 8\), что меньше суммы любых двух других элементов исходного множества, то в требуемом равенстве вида \(a + b = c + d\) они должны стоять по разные стороны от знака равенства: \[a + 3 = c + 5\qquad\Rightarrow\qquad a - c = 2,\] то есть на роль пары чисел \((a; c)\) подходят пары \((12; 10), (10; 8), (8; 6), (6; 4)\) – всего 4 пары, следовательно, в случае равенства вида \(a + b = c + d\) есть ровно 4 хороших подмножества из 4 элементов, содержащих \(3\) и \(5\).

Остаётся рассмотреть подходящие четырёхэлементные подмножества, не содержащие ни \(3\), ни \(5\). Они, таким образом, являются подмножествами множества \[\{4; 6; 8; 10; 12\},\] но в нём всего 5 элементов, то есть искомое его подмножество должно содержать все его элементы, кроме одного. Кроме того, ясно, что так как в множестве \(\{4; 6; 8; 10; 12\}\) все элементы чётные, то в равенстве вида \(a + b = c + d\) слева и справа должны стоять чётные числа, тогда сумма всех четырёх чисел должна делиться на 4.

Следовательно, нельзя удалять из множества \(\{4; 6; 8; 10; 12\}\) 6 или 10. Остаётся убедиться, что при удалении из него 4, 8 или 12 будут получаться хорошие подмножества. Это видно из равенств \[8 + 10 = 6 + 12,\qquad 6 + 10 = 4 + 12,\qquad 4 + 10 = 6 + 8.\] Таким образом, есть ровно 3 хороших подмножества исходного множества, не содержащие \(3\) и \(5\).

Итого: у исходного множества есть ровно \(1 + 4 + 3 = 8\) хороших четырёхэлементных подмножеств.

Ответ:

а) Да.

б) Нет.

в) \(8\).

а) Перепишем неравенство \(a_k+a_{k+2}<2a_{k+1}\) в другом виде: \[a_{k+2}-a_{k+1}<a_{k+1}-a_k\] Если \(d_k\) – разность \(a_{k+1}\) и \(a_k\), то неравенство значит, что \(d_k>d_{k+1}\). То есть последовательность разностей между двумя соседними “ашками” – строго убывающая последовательность целых чисел.
Пусть \(a_1=1\). Возьмем \(d_1=4\), \(d_2=3\), \(d_3=2\) и т.д. Получим последовательность “ашек”: \[1, \ 5, \ 8, \ 10, \ 11, \ 11, \ 10, \ 8, \ 5, \ 1\] Видим, что \(a_1=a_{10}=1\).

б) Предположим, что существует такая последовательность. Тогда, с одной стороны, \(a_6=a_1+d_1+d_2+d_3+d_4+d_5\), а с другой стороны, \(a_6=a_{10}-d_9-d_8-d_7-d_6\). Следовательно, равенство \(a_1+a_{10}=2a_6\) примет вид \[\begin{aligned} &a_1+a_{10}=a_1+d_1+d_2+d_3+d_4+d_5+a_{10}-d_9-d_8-d_7-d_6 \quad\Rightarrow\quad \\[1ex] &d_1+d_2+d_3+d_4+d_5=d_6+d_7+d_8+d_9\quad (*)\end{aligned}\] Так как последовательность разностей строго убывающая, то \(d_1>d_2>\dots>d_9\), следовательно, \(d_1+d_2+d_3+d_4+d_5>5d_5\), \(d_6+d_7+d_8+d_9<4d_6\). Так как \(d_5>d_6\), то \(5d_5>4d_6\), следовательно, область значений левой части \((*)\) не имеет пересечений с областью значений правой части. То есть равенство не может быть выполнено ни при каких \(d_i\). Значит, мы получили противоречие.

в) \(a_4=a_1+d_1+d_2+d_3\), \(a_7=a_{10}-d_9-d_8-d_7\). Следовательно, \[a_1-a_4-a_7+a_{10}=-d_1-d_2-d_3+d_7+d_8+d_9=(d_7-d_1)+(d_8-d_2)+ (d_9-d_3)\] Наибольшее возможное значение для \(d_7-d_1\) – когда \(d_1, d_2, \dots, d_9\) представляют собой последовательные целые числа. Тогда \(d_7-d_1\leqslant -6\) (например, числа \(-1,-2,-3,-4,-5,-6,-7,-8,-9\); разность между седьмым и первым членами равна \(-6\)).
Аналогично \(d_8-d_2\leqslant -6\), \(d_9-d_3\leqslant -6\). Следовательно, \[(d_7-d_1)+(d_8-d_2)+ (d_9-d_3)\leqslant -18\] Покажем, что максимум \(-18\) достигается, приведя пример:
последовательность \(45, 44, 42,39,35,30,24,17,9,0\)
с разностями \(-1, -2, -3, -4, -5, -6, -7, -8, -9\).

Ответ:

а) \(1,5,8,10,11,11,10,8,5,1\)

б) нет

в) \(-18\)

а) Один из возможных вариантов: \((1; 3; 30), (2; 4; 27), (5; 7; 20), (6; 8; 17), (9; 11; 10)\).

б) Сделать 10 ходов – значит стереть все числа. Покажем, что все числа стереть нельзя: если число 30 будет стёрто, то обязательно в одной тройке с числом 1 и одним из чисел 2 или 3.

Тогда если будет стёрто и число 29, то обязательно в одной тройке с оставшимся после первого хода из чисел 2 и 3, но третьим числом в тройку к 29 должно быть число не меньше 4, а это значит, что сумма чисел в тройке с 29 слишком велика: \(29 + 4 + \)(\(2\) или \(3\)) \(\geqslant 35\), что противоречит условию.

в) Пусть можно стереть \(k\) троек, тогда сумма всех чисел этих \(k\) троек должна не превосходить \[34 + (34 - 1) + ... + (34 - (k - 1)) = 34k - 1 - ... - (k - 1) = 34k - \dfrac{k(k - 1)}{2}.\] Так как нужно стереть \(3k\) чисел, то наименьшая возможная сумма всех чисел \(k\) троек равна \[1 + ... + 3k = \dfrac{3k(3k+1)}{2},\] откуда получаем неравенство \[\dfrac{3k(3k + 1)}{2}\leqslant 34k - \dfrac{k(k - 1)}{2},\] что равносильно \(k^2 \leqslant 6,6k\), откуда с учётом \(k\in\mathbb{N}\) получаем, \(k\leqslant 6\), то есть стереть больше \(6\) троек нельзя. Пример для 6 троек:
\((5; 11; 17), (1; 12; 18), (4; 10; 16), (3; 9; 15), (6; 7; 13), (2; 8; 14)\).

Ответ:

а) \((1; 3; 30), (2; 4; 27), (5; 7; 20), (6; 8; 17), (9; 11; 10)\).

б) Нет.

в) \(6\).