ЗАПИСАТЬСЯ НА ЗАНЯТИЕ
Первый урок бесплатно
Олимпиадная математика 5-9 класс
Принцип Дирихле:
кролики и не только
Откройте перед собой мир олимпиадного математического мастерства через призму принципа Дирихле.
Узнайте, как этот метод помогает с легкостью решать сложные задачи и преодолевать трудности на пути к олимпийскому успеху.
Узнайте, как этот метод помогает с легкостью решать сложные задачи и преодолевать трудности на пути к олимпийскому успеху.
Принцип Дирихле: Краткое Введение
Принцип Дирихле, названный в честь известного немецкого математика Петера Густава Ле́йбница Дирихле, представляет собой мощный метод решения задач, связанных с распределением объектов по ячейкам.
Классическая трактовка принципа производится с помощью кроликов и клеток: если n+1 кроликов сидят в n клетках, то обязательно найдется клетка, где будет хотя бы 2 кролика.
Классическая трактовка принципа производится с помощью кроликов и клеток: если n+1 кроликов сидят в n клетках, то обязательно найдется клетка, где будет хотя бы 2 кролика.
Имеется 3 кролика и 2 клетки, как бы не размещали кроликов в клетки,
в одной клетке точно будет 2 кролика.
в одной клетке точно будет 2 кролика.
Другими словами – если у нас есть N объектов и M ячеек, и N > M, то как минимум одна ячейка содержит более одного объекта.
Подходы к решению олимпиадных задач с Принципом Дирихле
В задачах использующих для решения принцип Дирихле чаще всего выделяют следующие подходы:
Применяйте принцип Дирихле к задачам, где требуется разместить элементы в определенном порядке с соблюдением определенных условий.
В большинстве задач на принцип Дирихле просят доказать определенный факт. Поэтому первым маркером, что в задаче может быть использован принцип Дирихле - это слово "Докажите".
Решая задачу на принцип Дирихле определите, что будет являться в вашей задаче кроликами, а что клетками. Так вы поймете, что придется размещать и куда. Это поможет применить принцип правильно.
Доказательство задач на принцип Дирихле стоит производить методом от противного.
Рассмотрим пример доказательства формулировки принципа Дирихле:
"Если n+1 кроликов сидят в n клетках, то обязательно найдется клетка, где будет хотя бы 2 кролика"
Доказательство:
Рассмотрим пример доказательства формулировки принципа Дирихле:
"Если n+1 кроликов сидят в n клетках, то обязательно найдется клетка, где будет хотя бы 2 кролика"
Доказательство:
- Постройте утверждение обратное тому, что просят доказать в задаче:
Предположим, что в каждом ящике сидит менее двух кроликов (один или ни одного). - Сделайте логический вывод из этого утверждения:
Тогда во всех n ящиках в совокупности сидит не более n кроликов. - Получите противоречие:
По условию имеется n+1 кролик, а не n кроликов. Значит во всех клетках не может быть менее двух кроликов, следовательно найдется клетка с двумя или более кроликами.
Получиличи противоречее с изначальным предположением и таким образом доказали задачу.
Примеры решения задач на принцип Дирихле
№ 1
Разбейте группу из 8 человек на 5 команд. Каждая команда должна содержать хотя бы двух человек. Докажите, что в какой-то момент две команды будут иметь одинаковое количество человек.
Доказательство:
№ 2
Дан выпуклый многоугольник с 20 вершинами. В каждой вершине многоугольника установлен флажок одного из пяти цветов: красный, синий, зелёный, жёлтый и фиолетовый. Каждый цвет используется не менее чем в четырех вершинах многоугольника.
Докажите, что существует такая диагональ многоугольника, на концах которой стоят флажки одного цвета.
Разбейте группу из 8 человек на 5 команд. Каждая команда должна содержать хотя бы двух человек. Докажите, что в какой-то момент две команды будут иметь одинаковое количество человек.
Доказательство:
- Докажем задачу от противного. Пусть не существует момента, когда две команды будут иметь одинаковое количество человек.
Так как минимально в команде может быть 2 человека, начнем разбивать людей на команды согласно нашему предположению (в данной задаче очевидно, что кролики в данной задаче - это люди, клетки - это команды). - В первой команде будет 2 человека, во второй 3, в третьей можно разместить только 3 человека. Итого мы распределили всех 8 людей на три команды и нам не хватило людей, чтобы заполнить все команды согласно нашему принципу,.
- Мы пришли к противоречию с нашим утверждением, значит в какой-то момент будут две команды с одинаковым количеством человек. Доказано.
№ 2
Дан выпуклый многоугольник с 20 вершинами. В каждой вершине многоугольника установлен флажок одного из пяти цветов: красный, синий, зелёный, жёлтый и фиолетовый. Каждый цвет используется не менее чем в четырех вершинах многоугольника.
Докажите, что существует такая диагональ многоугольника, на концах которой стоят флажки одного цвета.
Часть выпуклого многоугольника с выбранной красной вершиной.
Доказательство:
- Докажем задачу от противного. Считаем цвет вершины такой, какой флаг установлен в ней. Пусть не существует диагонали, когда обе вершины одного цвета.
Выберем одну вершину и зададим цвет этой вершины, как красный (такая вершина обязательно существует, так как каждый цвет используется не менее чем в четырех вершинах многоугольника). Проведем диагонали из этой вершины. Их будет 17, так как всего вершин 20, а диагонали проводятся к вершинам через одну от выбранной, то есть к 17.
Тогда в данной задаче клетки - это 17 вершин, к которым провели диагонали, а кролики - это цвета вершин. - Распределим 4 цвета синий, зелёный, жёлтый и фиолетовый (красный использовать нельзя чтобы не было диагонали с вершинами одного цвета) по 17 клеткам с учетом условия, что минимально каждый цвет присутсвует 4 раза. Тогда 16 клеток займет 4 синих, 4 зелёных, 4 жёлтых и 4 фиолетовых вершины. В оставшуюся клетку можно поместить один из выбранных цветов, например зеленый, но в таком случае не будет выполнено правило, что каждый цвет используется не менее чем в четырех вершинах многоугольника, так как красные флаги можно будет расположить только в 3-ех оставшихся вершинах, значит в последнюю клетку необходимо поместить красную вершину.
- Мы пришли к противоречию с нашим утверждением, значит существует диагональ у которой в вершинах находятся флаги одинакового цвета. Доказано.
Задачи на принцип Дирихле для самостоятельного решения
№ 1
Докажите, что в десятичной записи любого числа длиной 11 цифр найдутся две одинаковые цифры. (5-6 класс)
№ 2
В библиотеке имеется коллекция из 50 различных книг. Библиотекарь хочет расставить книги на полках так, чтобы каждая полка содержала не менее 10 книг, но не более 15.
Докажите, что в какой-то момент на каких-то двух полках окажется одинаковое количество книг. (5-7 класс)
№ 3
В компьютерной сети есть 7 пользователей, у каждого из которых есть свой уникальный пароль. Администратор сети решает сменить пароли пользователям, но каждый новый пароль должен отличаться от предыдущих и при этом содержать не менее 4 символов.
Докажите, что существует хотя бы одна пара пользователей, у которых новые пароли содержат одинаковые 2 символа, если пароль составляют из 26 букв латинского алфавита. (6-8 класс)
№ 4
Пусть на плоскости дано бесконечное множество точек с целочисленными координатами. Известно, что каждая точка окрашена в один из трех цветов: красный, зеленый или синий. Докажите, что существует прямоугольник со сторонами, параллельными осям координат, вершины которого окрашены в один и тот же цвет. (8-9 класс).
Докажите, что в десятичной записи любого числа длиной 11 цифр найдутся две одинаковые цифры. (5-6 класс)
№ 2
В библиотеке имеется коллекция из 50 различных книг. Библиотекарь хочет расставить книги на полках так, чтобы каждая полка содержала не менее 10 книг, но не более 15.
Докажите, что в какой-то момент на каких-то двух полках окажется одинаковое количество книг. (5-7 класс)
№ 3
В компьютерной сети есть 7 пользователей, у каждого из которых есть свой уникальный пароль. Администратор сети решает сменить пароли пользователям, но каждый новый пароль должен отличаться от предыдущих и при этом содержать не менее 4 символов.
Докажите, что существует хотя бы одна пара пользователей, у которых новые пароли содержат одинаковые 2 символа, если пароль составляют из 26 букв латинского алфавита. (6-8 класс)
№ 4
Пусть на плоскости дано бесконечное множество точек с целочисленными координатами. Известно, что каждая точка окрашена в один из трех цветов: красный, зеленый или синий. Докажите, что существует прямоугольник со сторонами, параллельными осям координат, вершины которого окрашены в один и тот же цвет. (8-9 класс).
Заключение
Принцип Дирихле – это не просто математический инструмент, но и мощный метод творческого мышления. Применяйте его в решении олимпиадных задач, и вы обнаружите, что даже самые сложные головоломки начинают решаться с легкостью.
Хотите знать и разбираться в школьной математике больше, тогда записывайтесь к нашим преподавателям на индивидуальные уроки или на авторский курс школьной математики.
Попробуйте лучшие курсы по математике!
Первый урок бесплатно
