Принцип Дирехле. Теоритическая справка
 Скачать 17.27 Kb.
|
|
Панарин Р. Н. Принцип Дирихле Теоритическая справка Решение задач на принцип Дирихле обычно основывается на методе доказательство от противного. Название данного метода говорит само за себя: если в задаче требуется доказать некоторое утверждение, будем предполагать, что оно не верное, то есть верно отрицание. После этого каким-то образом необходимо прийти к противоречию, что будет означать, что наше предположение неверно, и задача будет решена. Утверждение 1. Принципом Дирихле называется утверждение, сформулированное немецким математиком Иоганном Петером Густавом Лежён Дирихле в 1834 году. Оно гласит: Если в N клетках сидят не менее N+1 кроликов, то в какой-то из клеток сидит не менее двух кроликов Доказательство. Воспользуемся методом от противного: предположим, что это не так, то есть в каждой клетке сидит менее двух кроликов, то есть 0 или 1. Тогда в N клетках максимально будет сидеть N · 1 = N кроликов, что меньше, чем N + 1, - противоречие! Утверждение 2. Обобщенным принципом Дирихле называется следующее утверждение: «Если в N клетках сидят не менее kN + 1 кроликов, то в какой-то из клеток сидят хотя бы k + 1 кроликов». При решении задач Вы вряд ли встретите задачу, в которой в самом деле необходимо рассаживать кроликов по клеткам, поэтому в каждой конкретной задаче необходимо понять, что играет роль клеток, а что роль кроликов. Утверждение 3. Вариацией принципа Дирихле является метод усреднения, состоящий в следующем. Пусть каждому из n вариантов сопоставлено некое число. Тогда если сумма всех n чисел равна S, то одному из вариантов сопоставлено число, не меньшее S/n. Примеры решения задач Пример 1. Дано 6 целых чисел. Доказать, что среди них можно выбрать два, разность которых делится на 5. Доказательство. Числа, данные в условии задачи, намекают на то, что она решается с помощью принципа Дирихле. Кроликов должно быть на один больше, чем клеток, а 6 на один больше, чем 5. Следовательно кроликами являются сами числа. Осталось понять, каким образом выбираются клетки. Клеток должно быть 5 штук, а в условии задачи идјт речь о делимости на 5. А возможных остатков при делении на 5 как раз ровно 5 штук: 0, 1, 2, 3, 4. То есть мы сажаем кролика число в клетку остаток при делении на 5. По принципу Дирихле какие-то два кролика сидят в одной клетке значит, какие-то два числа имеют одинаковый остаток при делении на 5, а это значит, что их разность делится на 5. Пример 2. Числа от 1 до 9 разбили на три группы. Докажите, что хотя бы в одной из групп произведение чисел будет не меньше, чем 72. Доказательство. Воспользуемся принципом от противного. Пусть то, что требуется доказать, не верно, это значит, что в каждой группе произведение будет меньше 72, то есть меньше или равно 71. Но 71 число простое, то есть оно не может быть произведением указанных чисел. Отсюда следует, что произведение всех чисел меньше либо равно 703. C другой стороны, произведение всех чисел равно 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 = (3 · 4 · 6) · (2 · 5 · 7) · (8 · 9) = 72 · 70 · 72, что больше, чем 703. Полученное противоречие завершает решение задачи. Пример 3. Докажите, в любой компании найдётся двое с одинаковым числом знакомых из этой компании. Доказательство. Снова найдём кроликов и клетки. Нетрудно догадаться, что в качестве кроликов будут выступать люди, а в качестве клеток количество их знакомств. У любого человека может быть от 0 до n − 1 знакомых, где n количество людей в компании. Значит клетки будут иметь номера от 0 до n − 1. Казалось бы и клеток, и кроликов поровну, так что же, принцип Дирихле тут не работает? Работает, но с небольшой модификацией. Как обычно предположим противное тогда в каждой клетке сидит не более 1 кролика, но в клетках 0 и n − 1 не могут одновременно сидеть кролики. Действительно, тогда будет человек, который не знаком ни с кем, и человек, который знаком со всеми, чего не может быть. Пример 4. Доказать, что среди 101 целого числа всегда можно выбрать два таких, что их разность делится на 100. Доказательство. Отметим сразу, что при делении на 100 возможны 100 остатков: 0, 1, 2, ... , 99. Среди 101 остатка, которые мы получим после деления данных 101 числа на 100, по крайней мере, два одинаковых. Разность этих двух чисел при делении на 100 имеет остаток 0, а значит, делится на 100. |