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

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

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

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

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

Пусть \(q\) – наименьшее общее кратное, а \(d\) – наибольший общий делитель натуральных чисел \(x\) и \(y\), удовлетворяющих равенству \(7x=16y-73\).   а) Может ли \(\dfrac qd\) быть равным \(204\)?   б) Может ли \(\dfrac qd\) быть равным \(2\)?   в) Найдите наименьшее значение \(\dfrac qd\).

 

(ЕГЭ 2018, СтатГрад, 19 апреля 2018)

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

а) Предположим, что существуют такие \(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

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

Последовательность \(a_1, a_2, \dots, a_n, \dots\) состоит из натуральных чисел, причем \(a_{n+2}=a_{n+1}+a_n\) при всех натуральных \(n\).
а) Может ли выполняться равенство \(4a_5=7a_4\)?
б) Может ли выполняться равенство \(5a_5=7a_4\)?
в) При каком наибольшем натуральном \(n\) может выполняться равенство \(6na_{n+1}=(n^2+24)a_n\)?

 

(ЕГЭ 2018, СтатГрад, 26 января 2018)

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

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

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

С натуральным числом проводят следующую операцию: между каждыми двумя его соседними цифрами записывают сумму этих цифр (например, из числа \(194\) получается число \(1109134\)).

а) Приведите пример числа, из которого получается число \(411781109\).

б) Может ли из какого-нибудь числа получиться число \(210811495\)?

в) Какое наибольшее число, кратное \(9\), может получиться из трехзначного числа, в десятичной записи которого нет девяток?

 

(ЕГЭ 2017, резервный день)

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

а) Так как \(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

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

С натуральным числом проводят следующую операцию: между каждыми двумя его соседними цифрами записывают сумму этих цифр (например, из числа \(194\) получается число \(1109134\)).

а) Приведите пример числа, из которого получается число \(176148179\).

б) Может ли из какого-нибудь числа получиться число \(3107611090\)?

в) Какое наибольшее число, кратное \(11\), может получиться из трехзначного числа?

 

(ЕГЭ 2017, резервный день)

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

а) Так как \(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

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

На доске написано \(30\) натуральных чисел. Какие-то из них красные, а какие-то — зеленые. Все красные числа кратны \(8\), а зеленые – кратны \(3\). Все красные числа отличаются друг от друга, все зеленые числа также отличаются друг от друга. Но между красными и зелеными числами могут быть одинаковые.

 

а) Может ли сумма всех чисел, записанных на доске, быть меньше \(1395=3+6+\dots+90\), если на доске написаны только кратные \(3\) числа?

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

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

 

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

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

а) Заметим, что среди красных чисел также могут встречаться числа, кратные \(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

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

Учитель задумал несколько натуральных чисел (не обязательно различных). Эти числа и все их возможные произведения (по два числа, по три числа и т.д.) он выписал на доску. Если какое-то число, выписанное на доску, повторяется несколько раз, то на доске оставляют только одно такое число, а другие числа, равные ему, стирают.
Например, если задуманы числа \(1, 5, 6, 5\), то на доске будет набор \(1,5, 6, 30, 25, 150.\)

а) Приведите пример задуманных чисел, для которых на доске будет записан набор
\(2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90.\)

б) Существует ли пример таких задуманных чисел, для которых на доске будет записан набор
\(3, 5, 7, 9, 15, 21, 35, 45, 105, 315, 945\)?

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

 

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

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

а) Очевидно, что в нашем задуманном наборе чисел должны быть числа \(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

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

На доске написано \(100\) различных натуральных чисел, причем известно, что сумма этих чисел равна \(5120\).
а) Может ли на доске быть написано число \(230\)?
б) Может ли быть такое, что на доске не написано число \(14\)?
в) Какое наименьшее количество чисел, кратных \(14\), написано на доске?

 

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

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

а) Упорядочим числа по возрастанию \(a_1, a_2, \dots, a_{100}\). Пусть одно из этих чисел равно \(230\). Пусть все оставшиеся 99 чисел – это \(1, 2, 3, \dots, 99\). Тогда сумма всех ста чисел – наименьшая возможная сумма в случае, когда среди чисел есть \(230\). Вычислим ее: \[\dfrac{1+99}2\cdot 99+230=5180>5120\] Получили противоречие с условием, следовательно, ответ: нет.

 

б) Предположим, что на доске нет числа \(14\). Снова упорядочим числа по возрастанию и рассмотрим числа: \(1, 2, \dots, 13, 15, \dots, 101\). Мы взяли наименьшее возможное значение для первого числа, для второго и т.д. Тогда сумма всех этих чисел – наименьшая возможная сумма среди сумм произвольных ста натуральных чисел. Она равна: \[\dfrac{1+101}2\cdot 101-14=5137>5120\] Получили опять же противоречие с условием, следовательно, ответ: нет.

 

в) Приведем пример, когда среди чисел есть четыре числа, кратные \(14\) (это числа \(14, 28, 42, 56\)): \[1, 2, \dots, 69, \quad 71, 72, \dots, 83, \quad 85, 86, \dots, 97, \quad 100, 101, 102, 103, 115.\] Докажем, что не может быть меньше четырех чисел, кратных \(14\).
Возьмем набор чисел от \(1\) до \(100\). Сумма чисел в данном наборе равна \(5050\). Это минимально возможная сумма ста различных натуральных чисел. Назовем числа, кратные \(14\), странными. В данном наборе 7 странных чисел. Будем уменьшать количество странных чисел в нашем наборе, сохраняя минимальность суммы чисел в наборе.
Итак, для того, чтобы сумма чисел была минимальна, мы должны убрать самое большое странное число – это \(98\). Тогда взамен ему придется добавить другое число (не странное!). Самое маленькое такое число – это \(101\). После этого мы получим минимальную сумму, равную \(5053\). Она меньше, чем \(5120\), поэтому будем продолжать дальше.
Поступая аналогично, уберем странные числа \(98, 84, 70\). Вместо них добавим \(101, 102, 103\). Получим при этом минимальную сумму, равную \(5104\). Сделав данную операцию еще раз, то есть убрав \(56\) и добавив \(104\), получим минимальную сумму \(5152\), что больше, чем \(5120\). В силу минимальности суммы чисел в нашем наборе получаем противоречие.

Ответ:

а) нет

б) нет

в) 4