Олимпиадная математика. Задачи на принцип Дирихле с решениями и указаниями. 8-9 классы

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

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

Под редакцией 
М. В. Федотова

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

М. В. Федотов

8–9 
классы

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

УДК 373.167.1:519
ББК 22.171я721.6
Ф34

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

Деривативное издание на основе печатного аналога: Олимпиадная математика. Задачи на принцип Дирихле с решениями
и указаниями. 8–9 классы : учебно-методическое пособие /
М. В. Федотов ; под ред. М. В. Федотова. — М. : Лаборатория знаний, 2024. — 175 с. : ил. — (ВМК МГУ — школе). —
ISBN 978-5-93208-431-1.

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

ISBN 978-5-93208-900-2
© Лаборатория знаний, 2024

ОГЛАВЛЕНИЕ

От редактора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4

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

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

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

1. Принцип Дирихле. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

2. Принцип Дирихле и делимость целых чисел . . . . . .
13

3. Принцип Дирихле и дополнительные соображения
18

4. Принцип Дирихле в геометрии . . . . . . . . . . . . . . . . . . . . .
23

5. Принцип Дирихле и окраска плоскости и ее частей. Таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

6. Задачи
Всероссийских,
Московских
и
Санкт-Петербургских олимпиад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33

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

1. Принцип Дирихле. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39

2. Принцип Дирихле и делимость целых чисел . . . . . .
56

3. Принцип Дирихле и дополнительные соображения
81

4. Принцип Дирихле в геометрии . . . . . . . . . . . . . . . . . . . . .
102

5. Принцип Дирихле и окраска плоскости и ее частей. Таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
123

6. Задачи
Всероссийских,
Московских
и
Санкт-Петербургских олимпиад . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
147

Ответы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170

Список литературы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
172

ОТ РЕДАКТОРА

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

Заместитель декана по учебной работе
факультета ВМК МГУ имени М. В. Ломоносова,
доцент кафедры математической физики
М. В. Федотов

ПРЕДИСЛОВИЕ

Каждый раздел пособия содержит теоретические основы, описание
методов
решения
задач,
примеры
применения
методов
и набор заданий для решения. Задачи в разделах в основном
расположены по принципу «от простого — к сложному». Аналогичная ситуация имеет место и с последовательностью разделов, поэтому сами разделы и задачи в разделах рекомендуется
изучать в предложенном порядке. Приступать к решению задач
надо после изучения соответствующего теоретического материала и разбора примеров. К решениям, которые приведены во
второй части пособия, рекомендуется обращаться только после
того, как сами решите задачу. Если вы уже достаточно долго
безуспешно
пытаетесь
решить
задачу,
то
посмотрите
сначала
идею, потом указания (последовательно по одному). Если же
и это не помогает решить задачу, то изучите решение. Разобрав приведенное решение, самостоятельно решите эту задачу.
Только при такой последовательности действий вы научитесь
решать задачи.
После номера задачи в скобках приведены классы, для которых эта задача была предложена на олимпиаде. Однако это разделение на классы довольно условно. Понятно, что если задачу
давали в 8 классе, то ее можно давать и в 9 классе, и часто,
наоборот, задача, которую давали на олимпиаде для 9 класса,
вполне
по
силам
восьмиклассникам.
Поэтому,
придерживаясь
рекомендаций
в
скобках,
относитесь
к
этим
рекомендациям
творчески. Кстати, распределение задач по параграфам тоже не
всегда однозначно. Одну и ту же задачу можно было отнести
к разным параграфам.
В принципе, по этому пособию можно заниматься два года:
в
8
классе
пройти
по
всем
разделам,
выбирая
задачи
для
8 класса, в 9 классе снова пройти по всем разделам, выбирая
задачи для 9 класса. А можно пройти и за 1 год, если вы уже
в 9 классе.

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

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

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

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

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

В этом пособии приведены задачи на принцип Дирихле. Такие
задачи
относятся
к
логическим
задачам
и,
вообще
говоря,
должны были быть в пособии с названием «Логические задачи», но задачи на принцип Дирихле очень часто встречаются
на
олимпиадах
всех
уровней.
Поэтому
мы
решили
выделить
эти задачи в отдельное пособие, которое получилось довольно
объемным.

1.
Принцип Дирихле

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

В этом разделе собраны задачи на принцип Дирихле. Общая
формулировка принципа Дирихле звучит так:

Утверждение 1. Если m кроликов рассажены в n клеток,

то
хотя
бы
в
одной
клетке
находится
не
менее
m
n
кроликов, и хотя бы в одной клетке находится не более
m
n кроликов.

Если число m

n
не целое, то при решении задач оно округляется: в первой части утверждения — в б´ольшую сторону, а во
второй части — в меньшую.
Доказывается принцип Дирихле очень просто — методом от
противного.
Докажем
только
первую
часть
утверждения,
поскольку вторая часть доказывается аналогично. Предположим,
что в каждой клетке сидит меньше, чем
m
n
кроликов. Тогда

всего кроликов в клетках меньше, чем n · m

n = m. Это противоречит условию, и, значит, есть клетка, в которой сидит не
менее, чем m

n кроликов.

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

Это же утверждение можно сформулировать немного иначе:

Утверждение 2. Если nk + 1 кроликов сидят в k клетках,
то хотя бы в одной клетке находится не менее (n + 1) кроликов и хотя бы в одной из остальных клеток находится
не более n кроликов.

Наиболее распространена следующая частная формулировка
этого принципа:

Утверждение 3. Если кролики рассажены в клетки, причем
число кроликов больше числа клеток, то хотя бы в одной
из клеток находится более одного кролика.

Реже используется другая частная формулировка принципа
Дирихле:

Утверждение 4. Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста.

В принципе Дирихле используется понятие «более». Полезно
знать близкое утверждение, использующее понятие «менее»:

Утверждение 5. Если в n клетках сидит менее n(n − 1)

2
кро
ликов, то найдутся две клетки, в которых сидит одинаковое количество кроликов (может быть, ни одного).

Докажем это. Предположим противное. Пусть во всех клетках сидит различное количество кроликов. Расположим клетки
в порядке увеличения числа кроликов в них. Тогда в первой
клетке число кроликов не менее 0, во второй — не менее 1,
в третьей — не менее 2, ..., в n-й клетке — не менее n − 1. Но

тогда всего кроликов не менее 0 + 1 + 2 + . . . + (n − 1) = n(n − 1)

2
.

Это
противоречит
условию,
и,
следовательно,
предположение
не
верно.
Значит,
найдутся
две
клетки,
в
которых
сидит
одинаковое количество кроликов (может быть, ни одного).
Покажем на конкретных примерах, как работает этот принцип в задачах.

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

Пример 1. В школе 370 учеников. Доказать, что хотя бы двое
из них родились в один день года.

1. Принцип Дирихле
9

Р е ш е н и е. Предположим, что это не так, т. е. в каждый день
года родились не более одного ученика школы. Тогда, поскольку всего дней в году 366 (будем рассматривать максимально
возможное
число
дней
в
году,
т. е.
високосный
год),
всего
учеников
в школе не более 366,
что противоречит
условию.
Следовательно, наше предположение неверно и, значит, в школе есть хотя бы два ученика, которые родились в один день
года.

Замечание. В этой задаче сработала частная формулировка
принципа Дирихле: роль кроликов играют ученики, а роль
клеток — дни года.

Пример 2. На площадке 20 собак восьми разных пород. Доказать, что среди них есть не менее трех собак одной породы.

Р е ш е н и е. Предположим, что это не так, т. е. собак каждой
породы
менее
трех,
т. е.
не
более
двух.
Тогда,
поскольку
пород восемь, то всего собак на площадке не более 2 · 8 = 16,
что противоречит условию. Следовательно, наше предположение
неверно и, значит, есть не менее трех собак одной породы.

Замечание. В этой задаче сработал общий принцип Дирихле:
роль
кроликов
играют
собаки,
а
роль
клеток — породы.
Тогда
m = 20,
n = 8,
m
n = 20

8
= 2,5.
Значит,
по
общему
принципу Дирихле есть порода, к которой принадлежат не
менее 2,5 собак. Так как число собак может быть только
целым, должно быть не менее трех собак одной породы.

Пример 3. В непрозрачном мешке лежат 4 красных и 2 зеленых шара. Какое наименьшее число шаров надо вынуть, чтобы
среди них оказался:
а) один красный шар;
б) один зеленый шар;
в) один красный и один зеленый шар;
г) два шара одного цвета?

Р е ш е н и е. Эта задача из тех, в которых придется при решении использовать слова «в худшем случае».
а) В худшем случае мы можем вытащить первые два шара
зеленого цвета, тогда в мешке останутся только шары красного

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

цвета и третий шар обязательно будет красным. Значит, надо
вынуть три шара. Конечно, может так случиться, что среди
вынутых трех шаров будут два или даже три красных шара,
но в худшем случае будет только один красный шар.
б) Рассуждая аналогично, получаем, что надо вынуть 5 шаров.
в) Поскольку красных шаров больше, то в худшем случае
первые четыре шара могут оказаться красными и только пятый — зеленым. Поэтому надо вынуть 5 шаров.
г) При кажущейся похожести вопрос этого пункта отличается от трех предыдущих. Этот вопрос ставит классическую задачу на принцип Дирихле. Здесь клетки — цвета, а кролики —
шары. Цветов только два. Значит, по принципу Дирихле достаточно вынуть 3 шара, чтобы среди них оказались два шара
одного цвета.

О т в е т. а) 3; б) 5; в) 5; г) 3.

Пример 4.
Можно ли разложить 44 шарика на 9 кучек так,
чтобы количество шариков в разных кучках было различным?

Р е ш е н и е. Предположим, нам это удалось. Упорядочим кучки
по
возрастанию
количества
шариков.
Тогда
в
первой
кучке
должно быть не менее одного шарика, во второй — не менее
двух, ..., в девятой — не менее девяти. Всего шариков должно
быть не менее чем 1 + 2 + 3 + . . . + 9 = 45. А их только 44.
Противоречие. Значит, нельзя.

О т в е т. Нельзя.

Замечание. В этом примере использовалось последнее утверждение
из
теоретической
части,
причем
n
=
10,
так
как
для
использования
этого
утверждения
надо
считать,
что
есть
десятая
кучка,
в
которой
нет
шариков.
Тогда
n · (n − 1)

2
= 10 · 9

2
= 45, а шариков только 44.

Как видите, решать задачи на принцип Дирихле не сложно.
Надо просто понять, что в задаче является клетками, а что —
кроликами.
При решении задач этого раздела обязательно доказывайте
принцип
Дирихле
в
каждой
задаче,
чтобы
отработать
этот
метод доказательства. На олимпиаде же это надо делать обязательно, иначе вам могут снизить оценку за задачу.