Олимпиадная математика 5-9 класс

Принцип Дирихле:
кролики и не только

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

Классическая трактовка принципа производится с помощью кроликов и клеток: если n+1 кроликов сидят в n клетках, то обязательно найдется клетка, где будет хотя бы 2 кролика.
Имеется 3 кролика и 2 клетки, как бы не размещали кроликов в клетки,
в одной клетке точно будет 2 кролика.
Другими словами – если у нас есть N объектов и M ячеек, и N > M, то как минимум одна ячейка содержит более одного объекта.
Подходы к решению олимпиадных задач с Принципом Дирихле
В задачах использующих для решения принцип Дирихле чаще всего выделяют следующие подходы:
Примеры решения задач на принцип Дирихле
№ 1
Разбейте группу из 8 человек на 5 команд. Каждая команда должна содержать хотя бы двух человек. Докажите, что в какой-то момент две команды будут иметь одинаковое количество человек.

Доказательство:
  1. Докажем задачу от противного. Пусть не существует момента, когда две команды будут иметь одинаковое количество человек.
    Так как минимально в команде может быть 2 человека, начнем разбивать людей на команды согласно нашему предположению (в данной задаче очевидно, что кролики в данной задаче - это люди, клетки - это команды).
  2. В первой команде будет 2 человека, во второй 3, в третьей можно разместить только 3 человека. Итого мы распределили всех 8 людей на три команды и нам не хватило людей, чтобы заполнить все команды согласно нашему принципу,.
  3. Мы пришли к противоречию с нашим утверждением, значит в какой-то момент будут две команды с одинаковым количеством человек. Доказано.

№ 2
Дан выпуклый многоугольник с 20 вершинами. В каждой вершине многоугольника установлен флажок одного из пяти цветов: красный, синий, зелёный, жёлтый и фиолетовый. Каждый цвет используется не менее чем в четырех вершинах многоугольника.
Докажите, что существует такая диагональ многоугольника, на концах которой стоят флажки одного цвета.

Часть выпуклого многоугольника с выбранной красной вершиной.
Доказательство:
  1. Докажем задачу от противного. Считаем цвет вершины такой, какой флаг установлен в ней. Пусть не существует диагонали, когда обе вершины одного цвета.
    Выберем одну вершину и зададим цвет этой вершины, как красный (такая вершина обязательно существует, так как каждый цвет используется не менее чем в четырех вершинах многоугольника). Проведем диагонали из этой вершины. Их будет 17, так как всего вершин 20, а диагонали проводятся к вершинам через одну от выбранной, то есть к 17.
    Тогда в данной задаче клетки - это 17 вершин, к которым провели диагонали, а кролики - это цвета вершин.
  2. Распределим 4 цвета синий, зелёный, жёлтый и фиолетовый (красный использовать нельзя чтобы не было диагонали с вершинами одного цвета) по 17 клеткам с учетом условия, что минимально каждый цвет присутсвует 4 раза. Тогда 16 клеток займет 4 синих, 4 зелёных, 4 жёлтых и 4 фиолетовых вершины. В оставшуюся клетку можно поместить один из выбранных цветов, например зеленый, но в таком случае не будет выполнено правило, что каждый цвет используется не менее чем в четырех вершинах многоугольника, так как красные флаги можно будет расположить только в 3-ех оставшихся вершинах, значит в последнюю клетку необходимо поместить красную вершину.
  3. Мы пришли к противоречию с нашим утверждением, значит существует диагональ у которой в вершинах находятся флаги одинакового цвета. Доказано.
    Задачи на принцип Дирихле для самостоятельного решения
    № 1
    Докажите, что в десятичной записи любого числа длиной 11 цифр найдутся две одинаковые цифры. (5-6 класс)

    № 2
    В библиотеке имеется коллекция из 50 различных книг. Библиотекарь хочет расставить книги на полках так, чтобы каждая полка содержала не менее 10 книг, но не более 15.
    Докажите, что в какой-то момент на каких-то двух полках окажется одинаковое количество книг. (5-7 класс)

    № 3
    В компьютерной сети есть 7 пользователей, у каждого из которых есть свой уникальный пароль. Администратор сети решает сменить пароли пользователям, но каждый новый пароль должен отличаться от предыдущих и при этом содержать не менее 4 символов.
    Докажите, что существует хотя бы одна пара пользователей, у которых новые пароли содержат одинаковые 2 символа, если пароль составляют из 26 букв латинского алфавита. (6-8 класс)

    № 4
    Пусть на плоскости дано бесконечное множество точек с целочисленными координатами. Известно, что каждая точка окрашена в один из трех цветов: красный, зеленый или синий. Докажите, что существует прямоугольник со сторонами, параллельными осям координат, вершины которого окрашены в один и тот же цвет. (8-9 класс).
    Хотите знать и разбираться в школьной математике больше, тогда записывайтесь к нашим преподавателям на индивидуальные уроки или на авторский курс школьной математики.
    Заключение
    Принцип Дирихле – это не просто математический инструмент, но и мощный метод творческого мышления. Применяйте его в решении олимпиадных задач, и вы обнаружите, что даже самые сложные головоломки начинают решаться с легкостью.