Олимпиадная математика. Задачи на целые числа с решениями и указаниями. 5-7 классы

Н. Л. Семендяева, М. В. Федотов

ОЛИМПИАДНАЯ
МАТЕМАТИКА

ЗАДАЧИ 
НА ЦЕЛЫЕ ЧИСЛА
с решениями и указаниями 

5–7
классы

Электронное издание

Москва
Лаборатория знаний
2020

УДК 373.167.1:511
ББК 22.130я721.6
С30

Семендяева Н. Л.
С30
Олимпиадная математика. Задачи на целые числа с решениями и указаниями. 5–7 классы / Н. Л. Семендяева,
М. В. Федотов. — Электрон. изд. — М. : Лаборатория знаний,
2020. — 275 с. — (ВМК МГУ — школе). — Систем. требования:
Adobe Reader XI ; экран 10". — Загл. с титул. экрана. — Текст :
электронный.
ISBN 978-5-00101-890-2
Настоящее
пособие
составлено
преподавателями
факультета
ВМК МГУ имени М. В. Ломоносова на основе олимпиадных задач
по математике. Пособие содержит теоретический материал, подборку задач, а также идеи, указания (подсказки) и решения.
Рекомендуется школьникам 5–7 классов, интересующимся олимпиадными задачами, учителям математики, руководителям кружков
и факультативов.
УДК 373.167.1:511
ББК 22.130я721.6

Деривативное издание на основе печатного аналога: Олимпиадная математика. Задачи на целые числа с решениями и указаниями. 5–7 классы / Н. Л. Семендяева, М. В. Федотов. — М. : Лаборатория знаний, 2020. — 272 с. : ил. — (ВМК МГУ — школе).
ISBN 978-5-00101-264-1

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных
техническими
средствами
защиты
авторских
прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации

ISBN 978-5-00101-890-2
c○ Лаборатория знаний, 2020

2

ОГЛАВЛЕНИЕ

От авторов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Используемые обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6

Часть I. Теория и задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

1. Десятичная запись целого числа, НОД, НОК, алгоритм Евклида. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

2. Разложение на множители. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

3. Простые и составные числа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19

4. Деление с остатком. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23

5. Сравнение по модулю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33

6. Признаки делимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35

7. Уравнения в целых числах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

Часть II. Указания и решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51

1. Десятичная запись целого числа, НОД, НОК, алгоритм Евклида. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51

2. Разложение на множители. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87

3. Простые и составные числа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4. Деление с остатком. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5. Сравнение по модулю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6. Признаки делимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7. Уравнения в целых числах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

Ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

3

ОТ АВТОРОВ

Уважаемые читатели, вы держите в руках одну из книг серии
«ВМК
МГУ — школе».
Учебно-методические
пособия,
входящие
в эту серию, являются результатом более чем пятнадцатилетнего
труда коллектива авторов, работающих на подготовительных курсах факультета вычислительной математики и кибернетики (ВМК)
МГУ имени М. В. Ломоносова.
Сейчас
изданы
пособия
по
алгебре,
геометрии,
информатике
и физике для старшеклассников для подготовки к ЕГЭ, олимпиадам и вступительным экзаменам в вузы. Недавно вышли пособия
по математике для подготовки к ГИА для девятиклассников.
Но мы не хотим останавливаться только на стандартных задачах, необходимых для сдачи ГИА и ЕГЭ и экзаменов в вузы.
Мы хотим, чтобы школьники с младших классов и до окончания
школы могли решать задачи повышенной сложности — олимпиадные задачи, на которые у учителя обычно не остаётся времени на
обычном уроке математики. Большинство книг по этой тематике
выходят без разбивки по классам либо без разбивки по темам.
Многие хорошие книги с олимпиадными задачами вышли давно
и
с
тех
пор
не
переиздавались.
Мы
собрали
много
задач
из
различных
старых
и
не
очень
старых
сборников
олимпиадных
задач и предлагаем их вам.
Настоящее
пособие
рассчитано
на
5–7
классы
и
является
вторым
в
серии
пособий
по
олимпиадным
задачам.
Будет
ещё
несколько
книг
для
5–7
классов.
Параллельно
мы
уже
ведём
работу над сборником задач для 8–9 классов. Завершит серию
пособие для 10–11 классов.
Большинство
олимпиадных
задач,
особенно
для
школьников
младших и средних классов, не намного сложнее обычных школьных задач по математике. Поэтому не бойтесь их. Они только
все вместе выглядят страшными, а каждая задача по отдельности
вполне
вам
по
силам.
Берите
их
и
решайте.
Дорогу
осилит
идущий.
Заместитель декана по учебной работе
факультета вычислительной математики и кибернетики
МГУ имени М. В. Ломоносова,
доцент кафедры математической физики
М. В. Федотов

4

ПРЕДИСЛОВИЕ

Каждый раздел пособия содержит теоретические основы, описание
методов
решения
задач, примеры применения
методов и набор
заданий для решения. Задачи в разделах в основном расположены
по принципу от простого — к сложному. Аналогичная ситуация
имеет
место
и
с
последовательностью
разделов,
поэтому
сами
разделы и задачи в разделах рекомендуется изучать в предложенном порядке. Приступать к решению задач надо после изучения
соответствующего теоретического материала и разбора примеров.
После номера задачи указаны классы, для которых эта задача
была предложена на олимпиаде. Однако это разделение на классы
довольно условно. Понятно, что если задачу давали в 5 классе,
то
её
можно
давать
и
в
6–7
классах,
и
часто,
наоборот,
задача, которую давали на олимпиаде для 6–7 классов, вполне
по силам пятиклассникам. Поэтому, придерживаясь рекомендаций
о
принадлежности
задачи
тому
или
иному
классу,
относитесь
к ним творчески. Кстати, распределение задач по разделам тоже
не всегда однозначно. Одну и ту же задачу можно было отнести
к разным разделам.
В принципе, по этому пособию можно заниматься три года:
в 5 классе пройти по всем разделам, выбирая задачи для 5 класса, в 6 классе снова пройти по всем разделам, выбирая задачи
для 6 класса и т. д. А можно пройти и за более короткий срок:
за два года, если вы начали заниматься в 6 классе, или за год,
если вы уже в 7 классе.

Рекомендуется
школьникам
5–7
классов,
интересующимся
олимпиадными
задачами,
учителям
математики,
руководителям
кружков и факультативов.
Желаем удачи!

5

ИСПОЛЬЗУЕМЫЕ ОБОЗНАЧЕНИЯ

{a}
— множество, состоящее из одного элемента a;
∪
— объединение;
∩
— пересечение;
∅
— пустое множество;
∈
— знак принадлежности;
⊂
— знак включения подмножества;
∀
— для любого;
A∖B
— разность множеств A и B;
=⇒
— следовательно;
⇐⇒
— тогда и только тогда, когда;
N
— множество всех натуральных чисел; N0 = N ∪ {0};
Z
— множество всех целых чисел;
Q
— множество всех рациональных чисел;
R
— множество всех действительных чисел;
ОДЗ
— область допустимых значений;
{︂ · · ·
· · ·
— знак системы, означающий, что должны выполняться все
условия, объединённые этим знаком;
[︂ · · ·
· · ·
— знак совокупности, означающий, что должно выполняться
хотя бы одно из условий, объединённых этим знаком.

Необходимо отметить, что в формулировках задач параллельно
с
математически
более
корректной
терминологией
типа
«длина
отрезка AB равна 5» и записью |AB| = 5 используются школьная
терминология типа «отрезок AB равен 5» и запись AB = 5.

6

Часть I. ТЕОРИЯ И ЗАДАЧИ

В этом пособии приведены задачи на целые числа. Такие задачи
предлагают
на
любой
олимпиаде.
В
наших
пособиях
мы
уже
встречались
с
задачами
на
целые
числа,
например
в
книге
«Арифметические задачи» в разделах, посвящённых логическим
задачам. Здесь мы обобщим уже известные нам свойства целых
чисел и рассмотрим некоторые новые типы задач.
В
задачах
этого
пособия
иногда
встречается
произведение
n
подряд
идущих
натуральных
чисел,
начиная
с
единицы.
Такое
произведение
называется
факториалом
числа
n:
n! = 1 · 2 · 3 · . . . · n (читается «n-факториал»).
При решении задач этого пособия полезно помнить формулы
сокращённого умножения:

a2 − b2 = (a − b)(a + b);

(a ± b)2 = a2 ± 2ab + b2;

(a ± b)3 = a3 ± b3 ± 3ab(a ± b) = a3 ± 3a2b + 3ab2 ± b3;

a3 ± b3 = (a ± b)(a2 ∓ ab + b2);

an − bn = (a − b)(an−1 + an−2b + . . . + abn−2 + bn−1)
для любого целого n > 1;
an + bn = (a + b)(an−1 − an−2b + . . . − abn−2 + bn−1)
для любого нечётного n > 1
(минусы и плюсы во второй скобке чередуются).

1. Десятичная запись целого числа,
НОД, НОК, алгоритм Евклида

Теоретический материал

В
этом
разделе
собраны
задачи
на
использование
основных
свойств целых чисел. Приведём некоторые теоретические факты.
Любое натуральное число можно разложить в сумму по степеням числа 10:

anan−1 . . . a1a0 = an · 10n + an−1 · 10n−1 + . . . + a1 · 101 + a0 · 100.

Часть I. Теория и задачи

Основная
теорема
арифметики
гласит:
каждое
натуральное
число, кроме единицы, раскладывается в произведение простых
сомножителей, причём единственным образом, т. е. любое натуральное число n, большее единицы, можно представить в каноническом виде
n = p m1
1
· p m2
2
· . . . · p mk
k
,

где
p1,
p2,
. . .,
pk — простые
числа;
k,
m1,
m2,
. . .,
mk —
натуральные числа.
Наибольшее
натуральное
число,
на
которое
делятся
целые
числа
n1
и
n2,
называется
их
наибольшим
общим
делителем
и обозначается НОД(n1, n2). Если НОД(n1, n2) = 1, то числа n1
и n2 называются взаимно простыми.
Наименьшее
натуральное
число,
которое
делится
на
целые
числа
n1
и
n2,
называется
их
наименьшим
общим
кратным
и обозначается НОК(n1, n2).
Для того чтобы найти НОД(n1, n2), надо в каноническом разложении чисел n1 и n2 найти все общие простые сомножители
и возвести каждый из них в наименьшую степень, в которой этот
множитель
входит
в
каноническое
разложение
чисел
n1
и
n2.
Произведение
полученных
степеней
простых
множителей
даёт
НОД(n1, n2). Если же перемножить все простые сомножители чисел n1 и n2 в наибольших степенях, то получим НОК(n1, n2). Запишем правила нахождения наибольшего общего делителя и наименьшего общего кратного двух натуральных чисел формулами:
если n1 = p m1
1
· pm2
2
· . . . · pmk
k
, n2 = p l1
1 · pl2
2 · . . . · plk
k , то

НОД(n1, n2) = pmin(m1 ,l1 )
1
· pmin(m2 ,l2 )
2
· . . . · pmin(mk ,lk )
k
,

НОК(n1, n2) = pmax(m1 ,l1 )
1
· pmax(m2 ,l2 )
2
· . . . · pmax(mk ,lk )
k
.

Рассмотрим несколько примеров.

Примеры решения задач

Пример 1.
Доказать,
что
сумма
двух
нечётных
чисел
чётна,
а произведение нечётно.

Р е ш е н и е.
Рассмотрим
два
произвольных
нечётных
числа
n1
и n2. Их можно представить в виде n1 = 2m + 1, n2 = 2k + 1.
Тогда их сумма

n1 + n2 = 2m + 1 + 2k + 1 = 2(m + k + 1),

очевидно, чётна, а произведение

n1 · n2 = (2m + 1) · (2k + 1) = 2(2mk + m + k) + 1

нечётно. Утверждение доказано.

1. Десятичная запись целого числа, НОД, НОК, алгоритм Евклида
9

Пример 2. Доказать, что НОД(n1, n2) · НОК(n1, n2) = n1 · n2.

Р е ш е н и е. Это равенство следует из канонических разложений
чисел n1 и n2, определений НОД(n1, n2), НОК(n1, n2) и очевидного равенства
min(n1, n2) + max(n1, n2) = n1 + n2.
Действительно,
НОД(n1,n2)· НОК(n1,n2)=

=pmin(m1 ,l1 )
1
·pmin(m2 ,l2 )
2
· ... ·pmin(mk ,lk )
k
·pmax(m1 ,l1 )
1
·pmax(m2 ,l2 )
2
· ...

... ·pmax(mk ,lk )
k
=

=pmin(m1 ,l1 )+max(m1 ,l1 )
1
·pmin(m2 ,l2 )+max(m2 ,l2 )
2
· ...

... ·pmin(mk ,lk )+max(mk ,lk )
k
=

=pm1 + l1
1
·pm2 + l2
2
· ... ·pmk + lk
k
=

=pm1
1
·pm2
2
· ... ·pmk
k
·pl1
1 ·pl2
2 · ... ·plk
k =n1 ·n2.
Утверждение доказано.

Пример 3. Доказать, что НОД(n1, n2) = НОД(n1 ± n2, n2).
Р е ш е н и е. Пусть
n = НОД(n1, n2).
Тогда
существуют
взаимно
простые целые числа p и q такие, что n1 = n · p и n2 = n · q.
Поэтому n1 ± n2 = n · (p ± q). Поскольку числа (p ± q) и q взаимно
просты, НОД(n1 ± n2, n2) = n, что и требовалось доказать.

Пример 4.
Выполнив
деление
с
остатком
n1
на
n2,
получим
n1 = n2 · m + r1. Доказать, что НОД(n1, n2) = НОД(n2, r1).
Р е ш е н и е. Пусть
n = НОД(n1, n2).
Тогда
существуют
взаимно
простые целые числа p и q такие, что n1 = n · p и n2 = n · q.
Следовательно,
n · p = n · q · m + r1.
Поэтому r1 делится на n и не делится на q (иначе p делилось бы
на q). Значит, НОД(n2, r1) = n, что и требовалось доказать.

Замечание. На утверждениях примеров 3 и 4 основан алгоритм Евклида нахождения НОД двух чисел.
Пусть
a,
b — натуральные
числа,
a ⩾ b.
Требуется
найти
НОД(a, b).
Выполнив
деление
с
остатком
a
на
b,
получим
a = b · q0 + r1.
Если
r1
= 0,
то
a
делится
нацело
на
b
и НОД(a, b) = b. Если же r1 ̸= 0, то, выполнив деление с остатком b на r1, получим, что b = r1 · q1 + r2. Затем выполняется
деление с остатком r1
на r2
и т. д. В результате повторных
делений получим систему равенств
a = b · q0 + r1,
b = r1 · q1 + r2,
r1 = r2 · q2 + r3, . . . ,
rn−2 = rn−1 · qn−1 + rn,
rn−1 = rn · qn,
где
b > r1 > r2 > . . . > rn > 0.
Из
утверждений
примеров
3 и 4 следует, что последний ненулевой остаток rn является
НОД(a, b).

Часть I. Теория и задачи

Пример 5.
Отец
и
сын
решили
померить
шагами
расстояние
между двумя деревьями, для чего отошли одновременно от одного
и того же дерева. Длина шага отца — 70 см, сына — 56 см. Найти
расстояние между этими деревьями, если известно, что следы их
совпали 10 раз, причём в последний раз ровно у второго дерева.

Р е ш е н и е. Разложим
на
простые
множители
числа
70
и
56:
70 = 2 · 5 · 7;
56 = 23 · 7.
Найдём
НОК(70, 56) = 23 · 5 · 7 = 280.
Следовательно, через каждые 280 см следы отца и сына совпадают. Поскольку следы совпали ровно 10 раз, то расстояние между
двумя деревьями равно 280 · 10 = 2800 см, т. е. 28 метров.
О т в е т. 28 м.

Задачи

1.

5
а) Запишите
наибольшее
и
наименьшее
семизначные
числа.
б) Какое наибольшее и какое наименьшее семизначное число
можно написать четырьмя нулями и тремя единицами?

2.

5
Возраст
дедушки
выражается
наименьшим
трёхзначным
числом, которое записывается различными цифрами. Сколько
лет дедушке?

3.

5
Вычеркните
в
числе
4 000 538
пять
цифр
так,
чтобы
оставшееся число стало наибольшим.

4.

5
Из
числа
12345678910111213 . . . 5657585960
вычеркните
100 цифр так, чтобы оставшееся число стало наибольшим.

5.

5
Сколько
существует
натуральных
чисел,
меньших
100,
в записи которых цифра 5 использована хотя бы 1 раз?

6.

5-6 а) Сумма 2002 натуральных чисел — нечётное число. Каким числом — чётным или нечётным — является произведение
этих чисел?
б) Доказать,
что
если
произведение
двух
чисел
есть
число
нечётное, то сумма этих чисел всегда будет числом чётным.

7.

5-6 Сколькими нулями оканчивается число

100! = 1 · 2 · 3 · . . . · 98 · 99 · 100?

8.

5-6 Сколькими нулями оканчивается произведение

2003! = 1 · 2 · 3 · . . . · 2001 · 2002 · 2003?

9.

5-6 В произведении всех целых чисел от 1 до 100 вычеркнули все нули. Какой будет последняя цифра получившегося
числа — чётной или нечётной?

10.

5-6 Доказать, что если перемножить все целые числа от 1
до
1965,
то
получится
число,
последняя
ненулевая
цифра
которого чётна.

1. Десятичная запись целого числа, НОД, НОК, алгоритм Евклида
11

11.

6-7 Каково наименьшее натуральное n, при котором n! делится на 990?

12.

6-7 Может ли n! оканчиваться ровно на 5 нулей?

13.

6-7 Подряд
записаны
числа
1,
2,
. . . ,
2001,
2002.
Каких
цифр при записи этих чисел использовано больше: двоек или
единиц? На сколько больше?

14.

6-7 Найти двузначное число, равное сумме его цифр, увеличенной в 6 раз.

15.

6-7 Найти все такие двузначные числа N, что сумма цифр
числа N в пять раз меньше самого числа N.

16.

6-7 Найти все натуральные числа, которые в 12 раз больше
суммы своих цифр.

17.


6-7 Найти
все
трёхзначные
числа,
которые
уменьшаются
в 5 раз после вычёркивания первой цифры.

18.

6-7 На каждой из одиннадцати карточек написано по цифре,
не
превосходящей
пяти.
Расположив
эти
карточки
в
ряд,
Миша получил 11-значное число; затем, расположив те же
карточки по-другому, Миша получил второе 11-значное число.
Доказать, что сумма двух этих чисел будет содержать хотя
бы одну чётную цифру в своей десятичной записи.

19.

6-7 Показать, что (100−a)(100−b) = 100((100−a)−b)+ab и что
двузначные числа, близкие к 100, удобно перемножать так:
86 · 97 = (86−3) · 100+14 · 3 = 8342, где 14 = 100−86, 3 = 100−97.

20.

6-7 Доказать, что
а) два числа ab = 10a + b и ac = 10a + c, т. е. такие числа,
у которых число десятков одинаковое, можно перемножать по
формуле 10a ((10a + b) + c) + bc;
б) два числа ab = 10a + b и ac = 10a + c, у которых число
десятков
одинаковое,
а
сумма
единиц
b + c = 10,
можно
перемножать по формуле 100a(a + 1) + bc, т. е. число десятков
a надо умножить на следующее за ним число (a + 1) и к произведению приписать справа произведение единиц.

21.

6-7 Какое наибольшее значение может принимать выражение
aek − afh + bfg − bdk + cdh − ceg,
если каждое из чисел a, . . . , k равно 1 или −1?

22.

6-7 Число 111 . . . 11 (100 единиц) представлено в виде
a0 + a1 · 101 + a2 · 102 + . . . + a99 · 1099,
где a0, a1, . . . , a99 — неотрицательные целые числа, сумма
которых не больше 100. Доказать, что все они равны 1.

23.

6-7 Найти сумму цифр куба числа, состоящего из трёх единиц и некоторого количества нулей.