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

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

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

Задачи формата ЕГЭ

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

На окружности некоторым способом расставили натуральные числа от \(1\) до \(21\) (каждое число поставлено по одному разу). Затем для каждой пары соседних чисел нашли разность большего и меньшего.

 

а) Могли ли все полученные разности быть не меньше \(11\)?

 

б) Могли ли все полученные разности быть не меньше \(10\)?

 

в) Помимо полученных разностей, для каждой пары чисел, стоящих через одно, нашли разность большего и меньшего. Для какого наибольшего целого числа \(k\) можно так расставить числа, чтобы все разности были не меньше \(k\)?

а) Ответ: нет.
Найдем среди всех чисел число \(11\). Несложно проверить, что все выражения \[11-1;\quad 11-2;\quad 11-3;\quad ...\quad 11-10\] меньше \(11\). Аналогично, все выражения \[21-11; \quad 20-11;\quad ...\quad 12-11\] также меньше \(11\). То есть какое бы число \(x\) ни стояло рядом с \(11\) (слева или справа), модуль разности между \(x\) и \(11\) будет меньше \(11\).

 

б) Ответ: да.
Приведем пример:

Объясним, как мы его построили. Мы уже поняли, что \(11\) – особенное число и что рядом с ним могут стоять только числа \(1\) или \(21\), чтобы разность между наибольшим из них и \(11\) была равна \(10\).
Разобьем все числа на группы:
— числа от \(1\) до \(10\);
— числа от \(12\) до \(21\).
Заметим, что числа из одной группы не могут стоять рядом, так как разность наибольшего и наименьшего будет меньше \(10\). Поэтому при расстановке будем чередовать числа из разных групп. Начнем: \[11;\quad 1; \quad 12;\quad 2;\quad 13;\quad 3; ...\] Закономерность легко прослеживается. Такими наводящими рассуждениями можно построить искомый пример.

 

в) Разобьем все числа на три группы:
— группа 1: от \(1\) до \(7\);
— группа 2: от \(8\) до \(14\);
— группа 3: от \(15\) до \(21\).
Все расставленные по кругу числа разобьем на 7 блоков по 3 числа в каждом:

Докажем, что \(k\leqslant 6\), от противного. Пусть \(k=7\). Тогда числа из одной группы не могут находиться в одном блоке, так как иначе разность либо соседних, либо стоящих через одно чисел по модулю будет меньше \(7\) (так как разность наибольшего и наименьшего чисел в одном блоке меньше \(7\)) \((*)\). Заметим, что не может быть блока, в котором не будет числа из группы 1: в противном случае 7 чисел из группы 1 должны разместиться не более чем в 6 блоках. Но тогда по принципу Дирихле найдется блок, в котором будут два числа из группы 1, что противоречит доказанному условию \((*)\).
Аналогично можно сказать про числа из группы 2 и группы 3.
Поэтому, не умаляя общности, можно считать, что справа от числа из группы 1 стоит число из группы 2, справа от числа из группы 2 – число из группы 3, справа от числа из группы 3 – число из группы 1 и т.д. (см. рисунок выше)

 

Следовательно, в каждом блоке будет ровно один представитель из каждой группы.
Пусть синие числа – представители группы 1, красные – группы 2, зеленые – группы 3.
Найдем число \(8\) на окружности. Тогда рядом с ним (справа или слева) и через один от него обязательно будут стоять числа \(a\) и \(b\) из группы 1. Так как наименьшие числа из группы 1 – это \(1\) и \(2\), то наибольшая разность среди \(8-a\) и \(8-b\) – это \(8-2=6\). Получили противоречие, следовательно, предположение неверно.
Покажем пример для \(k=6\):

 

Ответ:

а) нет

б) да

в) \(6\)

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

Известно, что \(a, b, c, d\) – попарно различные положительные двузначные числа.

 

а) Может ли выполняться равенство \(\dfrac{a+c}{b+d}=\dfrac7{23} \ ?\)

 

б) Может ли дробь \(\dfrac{a+c}{b+d}\) быть в 12 раз меньше, чем сумма \(\dfrac ab+\dfrac cd \ ?\)

 

в) Какое наименьшее значение может принимать дробь \(\dfrac{a+c}{b+d}\), если \(a>4b\) и \(c>7d \ ?\)

 

(ЕГЭ 2017, официальный пробный 21.04.2017)

а) Предположим, что выполняется равенство \[\dfrac{a+c}{b+d}=\dfrac7{23}\] Тогда \(a+c=7k\), \(b+d=23k\), где \(k\) – натуральное число. Так как \(a, c\) – двузначные числа, то наименьшее значение \(a+c\geqslant 10+11=21\), следовательно, \(7k\geqslant 21 \quad\Rightarrow\quad k\geqslant 3\).
Возьмем \(k=3\). Тогда \(a+c=21\), \(b+d=69\). Следовательно, можно взять, например, \(a=10\), \(c=11\), \(b=16\), \(d=53\).
Ответ: да.

 

б) Предположим, что может быть \[12\cdot \dfrac{a+c}{b+d}=\dfrac ab+ \dfrac cd\] Перепишем это равенство в другом виде: \[12\cdot \dfrac a{b+d}+12\cdot \dfrac c{b+d} = \dfrac ab+\dfrac cd\] Докажем, что \[12\cdot \dfrac a{b+d}>\dfrac ab \quad {\small{\text{и}}} \quad 12\cdot \dfrac c{b+d}>\dfrac cd\] Из этого будет следовать, что предположение неверно и такое равенство невозможно. Рассмотрим первое неравенство. \[12\cdot \dfrac a{b+d}>\dfrac ab \quad\Leftrightarrow\quad \dfrac a{b+d}>\dfrac a{12b}=\dfrac a{b+11b}\] Так как все числа двузначные, то \(11b \geqslant 11\cdot 10=110\). Следовательно, \(d<11b\), а значит и левая дробь всегда строго больше правой.
Аналогично доказывается второе неравенство.
Следовательно, ответ: нет.

 

в) Так как все числа натуральные, то из \(a>4b\) можно сделать вывод, что \(a\geqslant 4b+1\). Аналогично \(c\geqslant 7d+1\). Подставим: \[\dfrac{a+c}{b+d} \geqslant \dfrac{4b+1+7d+1}{b+d}=4+\dfrac{3d+2}{b+d}\] Таким образом, наименьшее значение выражение будет принимать при наименьшем значении выражения \(\dfrac{3d+2}{b+d}\). Так как дробь тем меньше, чем больше ее знаменатель (при фиксированном числителе), то максимизируем знаменатель (то есть максимизируем \(b\)).
Так как \(a\) – двузначное, то максимальное значение для \(a\) – это 99, следовательно, \(4b+1\leqslant 99\), следовательно, \(b\leqslant 24\). Таким образом, получаем: \[\dfrac{a+c}{b+d} \geqslant 4+\dfrac{3d+2}{24+d}=4+\dfrac{3(d+24)+2-72}{d+24} =4+3-\dfrac{70}{d+24}\]

Теперь для того, чтобы полученное справа выражение было как можно меньше, нужно сделать как можно больше \(\dfrac{70}{d+24}\), то есть сделать как можно меньше \(d\).
Наименьшее значение для \(d\) – это \(10\). Следовательно: \[\dfrac{a+c}{b+d} \geqslant4+3-\dfrac{70}{10+24}=4\frac{16}{17}\] Таким образом, если наименьшее значение \(4\frac{16}{17}\) достигается, то \(b=24\), \(d=10\), \(a= 4\cdot 24+1=97\), \(c= 7\cdot 10+1=71\).

Ответ:

а) да

б) нет

в) \(4\frac{16}{17}\)

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

Три числа назовём “хорошей” тройкой, если они могут быть длинами сторон треугольника.

Три числа назовём “отличной” тройкой, если они могут быть длинами сторон прямоугольного треугольника.

а) Даны 5 различных натуральных чисел. Может ли оказаться, что среди них не найдётся ни одной “хорошей” тройки?

б) Даны 4 различных натуральных числа. Может ли оказаться, что среди них можно найти три “отличных” тройки?

в) Даны 10 различных чисел (необязательно натуральных). Какое наибольшее количество “отличных” троек могло оказаться среди них?

а) Если числа \(a, b, c\) являются сторонами некоторого треугольника, то для них выполнены неравенства треугольника: \(a< b+c, \ b< a+c, \ c< a+b\).
Возьмем последовательные 5 чисел Фибоначчи: \(1, 2, 3, 5, 8\): каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Следовательно, для любых трех чисел \(a_1, a_2, a_3\) из этой пятерки большее число будет \(\geqslant \) сумме двух других, следовательно, не будет выполняться неравенство треугольника (если эти числа последовательные, например, \(3, 5, 8\), то \(8=3+5\); если эти числа непоследовательные, например, \(2, 5, 8\), то \(8>2+5\)).
Ответ: да.

 

б) Упорядочим данные 4 числа по возрастанию: \(a, b, c, d\). Всего из данных чисел можно составить 4 различные тройки: \(a, b, c\); \(a, b, d\); \(a, c, d\); \(b, c, d\).
Заметим, что если тройка чисел является “отличной”, то для нее выполнена теорема Пифагора: \(x^2=y^2+z^2\).
Тогда можно сразу сказать, что у нас не могут быть одновременно “отличными” тройки \(a, b, c\) и \(a, b, d\), так как тогда должно быть выполнено \(c^2=a^2+b^2\), \(d^2=a^2+b^2\), а \(c\ne d\) (так как по условию числа различные).
Таким образом, для того, чтобы среди этих четырех чисел оказалось три “отличных” тройки, то это должны быть: \(a, c, d\); \(b, c, d\) и одна из троек: \(a, b, c\) или \(a, b, d\).
Аналогично можно заметить, что обе тройки \(a, c, d\) и \(b, c, d\) также не могут быть одновременно “отличными” (по тем же рассуждениям: \(a^2+c^2=d^2\) и \(b^2+c^2=d^2\), откуда \(a=b\)). Следовательно, “отличных” троек может быть не более двух. Таким образом, ответ: нет.

 

в) Упорядочим числа по возрастанию: \(c_1, c_2, \dots, c_{10}\). Нам нужно, чтобы у нас было наибольшее возможное количество “отличных” троек. Будем обозначать “отличную” тройку следующим образом: \((a, b, c)\), имея в виду, что \(a, b\) – катеты, \(c\) – гипотенуза, то есть \(c^2=a^2+b^2\).
Давайте подумаем, сколько у нас может быть различных “отличных” троек с одинаковой гипотенузой \(c_{10}\). Заметим, что если в двух различных “отличных” тройках \((x, y, c_{10})\) и \((z, y, c_{10})\) есть одинаковый катет (это катет \(y\)), то тогда по теореме Пифагора \(x=z\), то есть тройки не являются различными. Исходя из этого, в двух различных “отличных” тройках с одинаковой гипотенузой нет одинаковых катетов.
Таким образом, так как среди 10-ти данных чисел ровно 9 чисел, меньших \(c_{10}\), мы можем составить максимум 4 пары катетов так, чтобы получить 4 различные “отличные” тройки с гипотенузой \(c_{10}\).
Аналогично, мы можем составить максимум 4 различные “отличные” тройки с гипотенузой \(c_9\); три — с гипотенузой \(c_8\) и три — с гипотенузой \(c_7\); две — с гипотенузой \(c_6\) и две — с гипотенузой \(c_5\); одну — с гипотенузой \(c_4\) и одну — с гипотенузой \(c_3\) (и, вообще говоря, ни одной с гипотенузой \(c_2\) или \(c_1\)).
Следовательно, максимум мы можем составить 20 различных “отличных” троек, но никто не гарантирует, что мы сможем это сделать.
То есть мы доказали, что больше 20-ти составить точно не удастся, но для того, чтобы дать в задаче ответ: 20, мы должны привести конкретный пример из 10-ти различных чисел, необязательно натуральных, из которых мы сможем составить ровно 20 различных “отличных” троек.
А вот и пример: \[\sqrt1, \ \sqrt2, \ \sqrt3, \ \sqrt4, \ \sqrt5, \ \sqrt6, \ \sqrt7, \ \sqrt8, \ \sqrt9, \ \sqrt{10}\]

Будем составлять тройки следующим образом:
\((\sqrt1, \sqrt9, \sqrt{10})\)
\((\sqrt2, \sqrt8, \sqrt{10})\)
\(\dots\)
\((\sqrt1, \sqrt8, \sqrt9)\)
\(\dots\)

 

Придерживаясь этого правила, мы составим ровно 20 различных “отличных” троек.

Ответ:

а) да

б) нет

в) 20

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

Имеются каменные глыбы: \(50\) штук по \(700\) кг, \(60\) штук по \(1\,000\) кг и \(80\) штук по \(1\,500\) кг (раскалывать глыбы нельзя).

а) Можно ли увезти все эти глыбы одновременно на \(65\) грузовиках, грузоподъёмностью \(5\) тонн каждый, предполагая, что в грузовик выбранные глыбы поместятся?

б) Можно ли увезти все эти глыбы одновременно на \(43\) грузовиках, грузоподъёмностью \(5\) тонн каждый, предполагая, что в грузовик выбранные глыбы поместятся?

в) Какое наименьшее количество грузовиков, грузоподъёмностью \(5\) тонн каждый, понадобится, чтобы вывезти все эти глыбы одновременно, предполагая, что в грузовик выбранные глыбы поместятся?

а) Все глыбы по \(1\) т можно увезти в 12 грузовиках (5 глыб в одном грузовике); все глыбы по \(1,5\) т можно увезти в 27 грузовиках (26 грузовиков по 3 глыбы и 1 с двумя глыбами); все глыбы по \(0,7\) т можно увезти в 8 грузовиках (7 грузовиков по 7 глыб и 1 с одной глыбой). Всего при таком разложении глыб нужно \(12+27+8=47\) грузовиков, а у нас – 65. Следовательно, ответ: да.

 

б) Заметим, что масса всех глыб равна: \(50\cdot 0,7+60\cdot 1+80\cdot 1,5=215\) т и грузоподъемность 43-х грузовиков равна также \(43\cdot 5=215\) т. Следовательно, если и возможно вывезти все глыбы на 43 грузовиках, то каждый грузовик должен быть забит полностью.
Пусть в грузовике глыба массой \(0,7\) т. Тогда, чтобы он был забит полностью, в нем должно быть еще ровно 4 такие глыбы, то есть всего 5 таких глыб, и одна глыба массой \(1,5\) т.
Следовательно, чтобы вывести глыбы по \(0,7\) т, нужно 10 грузовиков, и тогда будет вывезено также еще 10 глыб по \(1,5\) т.
Остается 70 глыб по \(1,5\) т и 60 глыб по \(1\) т и 33 грузовика.
Если в грузовике будет глыба по \(1,5\) т, то таких глыб должно быть всего 2, а также 2 глыбы по \(1\) т (чтобы грузовик был забит полностью). Следовательно, чтобы вывезти все глыбы по \(1\) т, нужно 30 грузовиков. Тогда останется 10 глыб по \(1,5\) т и 3 грузовика. Видим, что мы не можем поместить 10 таких глыб в 3 грузовика.
Ответ: нет.

 

в) В предыдущем пункте мы показали, что увезти все глыбы на 43 грузовиках не получится. На меньшем количестве грузовиков также не получится, так как их суммарная грузоподъемность будет меньше суммарной массы всех глыб.
Следовательно, грузовиков нужно точно \(\geqslant 44\). Докажем, что на 44 грузовиках можно вывезти все глыбы.
Возьмем разложение глыб по грузовикам из пункта б). На последнем шаге у нас осталось 10 глыб по \(1,5\) т и использовано уже 40 грузовиков. Но 10 глыб по \(1,5\) т можно спокойно увезти на 4-х грузовиках. Таким образом, получаем, что всего использовано 44 грузовика. Чтд.

Ответ:

а) да

б) нет

в) 44

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

Маша и Наташа делают фотографии. В первый день Наташа сделала \(n\) фотографий, а Маша – \(m\) фотографий. Каждый следующий день каждая из девочек делала на одну фотографию больше, чем в предыдущий. Известно, что в общей сложности Наташа сделала на 1615 фотографий больше Маши, а также то, что фотографировали они больше одного дня.

 

а) Могли ли девочки фотографировать в течение пяти дней?

б) Могли ли девочки фотографировать в течение шести дней?

в) Какое наибольшее количество фотографий могла сделать Наташа, если Маша в последний день сделала меньше 30 фотографий?

а) Пусть \(k\) – количество дней, в течение которых девочки фотографировали. Тогда в последний день Наташа сделала \(n+k-1\) фотографий, Маша – \(m+k-1\) фотографий.
Предположим, что \(k=5\).
Следовательно, всего Наташа сделала \(\dfrac{n+n+k-1}2\cdot k=(n+2)\cdot 5\) фотографий (сумма первых пяти членов арифметической прогрессии), Маша: \(\dfrac{m+m+k-1}2\cdot k=(m+2)\cdot 5\) фотографий. Тогда можно составить уравнение \[(n+2)\cdot 5=(m+2)\cdot 5+1615\quad\Rightarrow\quad n=m+323\] \(n,m\) – любые натуральные числа. Из полученного уравнения мы видим, что можно подставить вместо \(m\) и \(n\) любые натуральные числа и никакого противоречия не будет.
Пусть \(m=1\), \(n=324\). Тогда на пятый день Наташа сделала 328 фотографий, Маша – 5 фотографий. Всего Наташа сделала \((324+328):2\cdot 5=1630\) фотографий, Маша сделала \((1+5):2\cdot 5=15\) фотографий. И действительно, \(1630=15+1615\).
Таким образом, ответ: да.

 

б) Предположим, что \(k=6\).
Поступая аналогично пункту а), получим следующее уравнение \[n=m+\dfrac{1615}6\] Так как \(n,m\) – натуральные числа, то нет ни одного натурального числа, удовлетворяющего полученному уравнению. Следовательно, ответ: нет.

 

в) В общем виде условие, что Наташа сделала суммарно на 1615 фотографий больше, чем Маша, можно записать так: \[\dfrac{2n+k-1}2\cdot k-\dfrac{2m+k-1}2\cdot k=1615 \quad\Leftrightarrow\quad k(n-m)=1615\] Заметим, что \(1615=5\cdot 17\cdot 19\).
Так как в последний день Маша сделала \(m+k-1\) фотографий, и это число меньше 30, то отсюда получаем \(m+k<31\) или \(m+k\leqslant 30\) (так как числа \(m\) и \(k\) – натуральные).
Следовательно, можно сказать, что \(k\leqslant 30\).
Из уравнения \[k(n-m)=5\cdot 17\cdot 19\] тогда можно сделать вывод, что \(k\) равно либо 5, либо 17, либо 19. Рассмотрим все три случая.

 

1) Пусть \(k=5\). Тогда \(m\leqslant 25\). Также тогда \(n-m=323\). Следовательно, сумма сделанных Наташей фотографий равна \[S=\dfrac{2(323+m)+5-1}2\cdot 5\leqslant 1750,\] причем равенство достигается, когда \(m=25\).

 

2) Пусть \(k=17\). Тогда \(m\leqslant 13\), \(n-m=95\). Следовательно, \[S=\dfrac{2(95+m)+17-1}2\cdot 17\leqslant 1972\]

3) Пусть \(k=19\). Тогда \(m\leqslant 11\), \(n-m=85\). Тогда \[S=\dfrac{2(85+m)+19-1}2\cdot 19\leqslant 1995\]

Таким образом мы видим, что наибольшее количество фотографий будет сделано Наташей за 19 дней, если \(m=11\).

 

Выполним проверку.
Наташа делала 96, 97, ... , 114 фотографий в 1, 2, ..., 19 день соответственно.
Маша делала 11, 12, ..., 29 фотографий в 1, 2, ..., 19 день соответственно.
Всего Наташа сделала \((96+114):2\cdot 19=1995\) фотографий.
Всего Маша сделала \((11+29):2\cdot 19=380\) фотографий.
Действительно, \(1995=380+1615\).

Ответ:

а) да

б) нет

в) 1995