XV Международная студенческая научная конференция Студенческий научный форум - 2023

Введение

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

В данной работе рассматривается основные понятия Принципа Дирихле, а также приводятся типовые примеры для закрепления знаний, полученных из изложенного в данной работа материала.[1]

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

1.1 Общая информация о принципе Дирихле

Дирихле Петер Густав Лежен (13.02.1805 – 05.05.1859) – немецкий математик. Родился в Дюрене. В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье.

В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 занял место доцента в Бреславе; с 1829 работал в Берлине. В 1831-1855гг. – профессор Берлинского университета, после смерти К. Гаусса (1855г.) – Гёттингенского университета.

Сделал ряд крупных открытий в теории чисел; установил формулы для числа классов бинарных квадратичных форм с заданным определителем и доказал теорему о бесконечности количества простых чисел в арифметической прогрессии из целых чисел, первый член и разность которой взаимно просты. К решению этих задач применил аналитические функции, названные функциями (рядами) Дирихле. Создал общую теорию алгебры, единиц в алгебраическом числовом поле. В области математического анализа впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье кусочно-непрерывной и монотонной функций, что послужило обоснованием для многих дальнейших исследований. Значительны труды Дирихле в механике и математической физике, в частности, в теории потенциала. С именем Дирихле связаны задача, интеграл (ввел интеграл с ядром Дирихле), принцип, характер, ряды. Лекции Дирихле имели огромное влияние на выдающихся математиков более позднего времени, в том числе на Г. Римана, Ф. Эйзенштейна, Л. Кронекера, Ю. Дедекинда.[2]

1.2 Различные формулировки принципа Дирихле

При решении многих задач используется логический метод рассуждения — "от противного". Здесь мы рассмотрим одну из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из n элементов разбито на m непересекающихся частей, не имеющих общих элементов, где n > m то, по крайней мере, в одной части будет более одного элемента.

На языке отображений эта формулировка означает, что если в А (множестве предметов) больше элементов, чем в В (множестве ящиков), то не существует обратимого отображения А в В.

Другая формулировка “ принципа Дирихле“: если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета.

В шутливой форме принцип Дирихле выглядит так: “нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев “. [2]

Применение принципа Дирихле для решения различных задач

Пример 1. Если на шахматную доску, имеющую 8 горизонталей, ставят 9 фигур, то хотя бы одна пара фигур оказывается на одной горизонтали.

Принцип Дирихле называет также принципом ящиков, или правилом птичьих гнезд.

Справедливость принципа Дирихле можно проверить, рассуждая от противного. Допустим, что не существует классов, в которые попало более одного элемента, тогда, окажется что в n классах окажется не болееn элементов, а это противоречит тому, что элементов больше n.

Простой и очевидный принцип Дирихле позволяет получать далеко не очевидные результаты.

Пример 2. Доказать, что если в комнате находится m (m>2) человек, то

хотя бы двое из них имеют одинаковое число знакомых среди присутствующих.

Доказательство

Число знакомых каждого человека (n) может принимать значения от 0

(если он не знаком ни с кем в комнате) до m - 1 (если он знаком со всеми

присутствующими), т.е. m различных значений.

Возможны два случая - либо хотя бы для одного значения n в зале нет

человека с n знакомыми, либо для всех n найдется хотя бы один человек,

имеющий ровно n знакомых в комнате.

В первом случае m>n, так как хотя бы одно значение n пропущено, а тогда по принципу Дирихле хотя бы для двух из m человек значение n одно и то же, т.е. в этом случае есть двое людей, имеющих поровну знакомых.

Во втором случае в комнате должен находиться человек, имеющий о

знакомых, и человек, имеющий m - 1 знакомых. Однако это невозможно, так как если эти люди знакомы друг с другом, то первый уже имеет хотя бы одного знакомого, а если они не знакомы, то число знакомых второго человека меньше чем m – 1.

Это утверждение геометрически можно сформулировать так: если некоторые из m точек плоскости соединены отрезками прямых, то всегда найдутся две точки, из которых выходит одинаковое число отрезков.

Пример 3. Доказать, что если ни одно из данных 10 натуральных чисел не делится на 10, то делится на 10 сумма нескольких этих рядом стоящих чисел.

Доказательство

Обозначим данные числа через n₁, n₂, …, n₁₀и рассмотрим числа m₁ = n₁, m₂ = n_{1 +} n₂, …, m₁₀ = n₁ + n₂ +… + n₁₀. Если одно из них кратно 10, тоутверждение доказано.

В противном случае рассмотрим их остатки от деления на 10. Так как остатков 10 и они могут принимать не более 9 значений (от 1 до 9), то по принципу Дирихле получаем, что найдутся два числа m_i, m_j (i<j) c равными остатками от деления на 10. Разность этих чисел m_i-m_j = n_i+1 +...+ n_j; является суммой нескольких рядом стоящих чисел и кратна 10. Утверждение полностью доказано.

При решении комбинаторных задач используют очевидное обобщение принципа Дирихле: если m = n·k + p (0<p< n), то при отнесении каждого из mэлементов к одному из n классов хотя бы в один класс попадет не менее k + 1 элементов. Справедливость этого утверждения также можно проверить, рассуждая от противного.

Иногда вместо прямого использования принципа Дирихле проще применить метод рассуждения от противного.

Пример 4. Доказать, что в студенческой группе из 25 человек не менее чем у троих день рожденья в одном месяце.

Доказательство

Допустим, что в каждом месяце день рожденья не более чем у двоих студентов, тогда на 12 месяцев приходится не более 24 дней рожденья.

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

Пример 5. В квадрате со стороной 1 метр находится 20 точек. Доказать,

что из этих 20 точек можно выбрать 3 точки, которые находятся внутри квадрата со стороной 1/3 метра.

Доказательство

Квадрат со стороной 1 м можно разбить на 9 квадратов со стороной 1/3 м. Допустим, что в каждом из этих квадратов находится не более двух точек, тогда в этих 9 квадратах, а следовательно, и в исходном квадрате находится не более 18 точек.

Полученное противоречие доказывает, что хотя бы в одном квадрате со стороной 1/3 м находится более двух точек (т.е. не менее трех).

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

Я считаю, что проделанная мною работа, дала положительные результаты. Так как большое количество логических задач можно решить только этим способом. Этот метод необходимо знать и применять его на практике. Я собираюсь продолжить мои исследования дальше и найти еще новые способы решения логических задач.

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

https://ru.wikipedia.org/wiki/Принцип_Дирихле_(комбинаторика)

https://school-science.ru/2/7/30571

Код для цитирования: Скопировать