Принцип дирихле доклад 6 класс

Обновлено: 04.07.2024

Презентация на тему: " Принцип Дирихле Проект обучающихся в 6А классе Жаворонкова Павла и Касьянова Романа. Руководитель: учитель математики высшей категории, Отличник народного." — Транскрипт:

1 Принцип Дирихле Проект обучающихся в 6А классе Жаворонкова Павла и Касьянова Романа. Руководитель: учитель математики высшей категории, Отличник народного просвещения Разумова Зинаида Андреевна.

2 Наш проект - учебный, практического применения. В школьном туре олимпиады встретилась задача. Мы решили изучить подробнее этот вопрос: - Познакомились с литературой по этой теме. - Рассмотрели исторический материал. - Изучили принцип Дирихле. - Подготовили реферат и презентацию. - Научились применять его при решении задач. - Планируем выступить перед учащимися 6 классов.

3 Дирихле родился в вестфальском городе Дюрене в семье почтмейстера. В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом. С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье. Биография

4 - В 1827г. устраивается на должность приватдоцента университета Бреслау (Вроцлав). - В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент. - Затем с 1831 г. как экстраординарный профессор. - С 1839 г. как ординарный профессор Берлинского университета. В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. Биография

5 Принцип Дирихле устанавливает связь между объектами и контейнерами при выполнении определённых условий. Принцип Дирихле

6 Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца.

8 Если в n клетках сидит m голубей, причем m

9 Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев.

13 В городе 15 школ. В них обучается 6015 школьников. В концертном зале городского Дворца культуры 400 мест. Доказать, что найдётся школа, ученики которой не поместятся в этот зал. Решение: Предположим, что в каждой школе не более 400 учеников. Значит во всех школах = 6000(школьников). Ответ: Поэтому ученики этой школы не поместятся в зал на 400 мест. Задача 4.

14 В школе 5 восьмых классов: 8А, …, 8Д. В каждом из них учится по 32 человека. Докажите, что найдутся 14 человек, родившихся в один месяц. Решение: Предположим, что в каждом месяце родилось не более 13 учеников. Значит за 12 месяцев родилось 1213=156(школьников). Но по условию в школе обучается 532=160(человек). Ответ: Значит, найдется месяц, в котором родилось больше, чем 13 учеников, то есть хотя бы 14. Задача 5.

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

Вложение	Размер
printsip_dirihle_5v.docx	172.53 КБ

Предварительный просмотр:

Государственное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа №655

Приморского района Санкт-Петербурга

Математика, информатика, программирование.

Балсанов Савва, Верма Ману

Мороз Ю.В., учитель математики.

Биография Дирихле…………………………………………..5
Формулировка принципа Дирихле………………………….6

3. Задачи на принцип Дирихле………………………………….7

3.1. Арифметические задачи……………………………………..8

3.2. Комбинаторные задачи……………………………………. 9

3.3. Геометрические задачи……………………………………. 11

Даже незнакомый с математикой человек, взяв в руки книгу по математике, может, как правило, сразу определить, что эта книга действительно по математике, а не по какому- нибудь другому предмету. И дело не только в том, что там обязательно будет много формул: формулы есть и в книгах по физике, по химии или астрономии. Дело в том, что в любой книге по математике непременно присутствуют доказательства. Именно доказуемость математических утверждений, наличие в математических текстах доказательств – вот что отличает математику от других областей знания.

Но что же такое доказательство? Доказательство-это рассуждение, которое убеждает того, кот его воспринял, настолько, что он готов убеждать других с помощью этого рассуждения.

Самый естественный способ доказать, что объект с заданными свойствами существует,-это его указать, назвать, построить и убедиться, что он действительно обладает нужными свойствами.

В математике большое значение имеют так называемые доказательства существования. Например, чтобы доказать, что уравнение имеет решение достаточно привести какое-то его решение. Доказательства существования такого рода называют прямыми или конструктивными .

Но бывают и косвенные доказательства существования , когда обоснование факта, что искомый объект существует, происходит без прямого указания на сам объект. Одним из способов косвенно доказать существование является логический прием названный принципом Дирихле – по имени Петера Густава Дирихле, немецкого математика.

Разнообразие логических задач велико, велико и количество способов их решения. В своей работе мы рассмотрели задачи, решаемые с помощью принципа Дирихле.

Логическая задача – это особый вид задачи, который развивает логику, образное и творческое мышление, поэтому такие задачи являются олимпиадными. Решение таких задач есть гимнастика ума и увлекательное занятие, поскольку для решения большинства из них требуется не только знание определенного программного материала, но и логическое мышление.

В своем исследовании мы выделила несколько видов логических задач:

а) арифметические; б) комбинаторные. в) геометрические.

Цель : научиться применять принцип Дирихле к решению задач.

1. Ознакомиться с биографией Дирихле.

2. Рассмотреть различные формулировки принципа Дирихле.

3. Классифицировать задачи в соответствии с их содержанием и научиться применять изученный принцип к решению задач.

Ио́ганн Пе́тер Гу́став Лежён-Дирихле́

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

В 12 лет Дирихле начал учиться в гимназии в Бонне , спустя два года — в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом.

С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье.

В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 г. молодой человек по приглашению Александра фон Гумбольдта устраивается на должность приват-доцента университета Бреслау. В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент, затем с 1831 г. как экстраординарный, а с 1839 г. как ординарный профессор Берлинского университета.

В 1831 г. Дирихле женится на Ребекке Мендельсон-Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди.

В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. В числе его достижений — доказательство сходимости рядов Фурье.

В комбинаторике принцип Дирихлем ( нем . Schubfachprinzip , “принцип ящиков”) — утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами (“ кроликами ”) и контейнерами (“клетками”) при выполнении определённых условий. В английском и некоторых других языках утверждение известно как “принцип голубей и ящиков” (англ. Pigeonhole principle ), когда объектами являются голуби, а контейнерами — ящики.

2.Формулировка принципа Дирихле.

Самая популярная формулировка принципа Дирихле звучит так:

. "Если в n клетках сидит (n+1) или больше зайцев, то найдётся клетка, в которой сидят, по крайней мере, два зайца".

Однако во всех этих задачах часто нелегко догадаться, что считать "голубем", что - "ящиком", и как использовать наличие двух "голубей", попавших в один "ящик". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.

Данное утверждение устанавливает связь между объектами при выполнении определённых условий. Данный метод автор успешно применял к доказательству арифметических утверждений. Принцип Дирихле применяется в разных разделах математики: в арифметике, в комбинаторике, в геометрии. И в данной работе рассмотрим некоторые изюминки решения задач на принцип Дирихле.

Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д. Принцип Дирихле можно сформулировать на языке множеств и отображений.

ФОРМУЛИРОВКА 2. "При любом отображении множества M, содержащего n+1 элементов, во множество N, содержащее n элементов, найдутся два элемента множества M, имеющие один и тот же образ".

Однако во всех этих задачах часто нелегко догадаться, что считать "зайцем", что - "клеткой", и как использовать наличие двух "зайцев", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.

3. Задачи на принцип Дирихле.

Пример 1 В классе 26 учеников, из них больше половины мальчики. Докажите, что какие-то 2 мальчика сидят за одной партой, если известно, что парт 13.

Мальчиков больше половины, т.е больше 13, а парт ровно 13. Следуя принципу Дирихле, два мальчика будут сидеть за одной партой

При каком наименьшем кол-ве учеников школы среди них найдутся двое, у которых совпадают день и месяц рождения

1. Если в году 365 дней, то по принципу Дирихле учеников должно быть 366.

2. Если в году 366 дней, то учеников - 367

В Санкт-Петербурге живет более 4 млн. человек. Докажите, что у каких-то двух из них одинаковое кол-во волос (известно , что у чел-ка на голове не более 1 млн. волос)

Давайте предположим ,что у всех людей разное кол-во волос на голове, то таких людей будет 1 млн., а по условию задачи их – 4 млн. , по принципу Дирихле найдутся хотя бы два человека с одинаковым кол-вом в

В школе учатся 1200 учеников найдется ли день в который отмечают свои дни рождения не меньше чем 4 ученика

1200:366=3(ост.102) к=3,N=365-366 так как 366 кол-во дней в високосном году m>n значит по обобщенному принципу Дирихле найдутся хотя бы 4 ученика у которых дни рождения в один день

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Описание презентации по отдельным слайдам:

В классе 34 человек. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы? Задача №1 Решение: 10

Биография Дирихле Петер Густав Лежен родился 13.02.1805 года в Вестфальском городе Дюрене в семье почтмейстера. В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом. С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Ж.Фурье. В 1827г. устраивается на должность приватдоцента университета Бреслау (Вроцлав). В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент, затем с 1831 г. как экстраординарный профессор. 2

В числе достижений Дирихле: - сделал ряд крупных открытий в теории чисел: установил формулы для числа классов бинарных квадратичных форм с заданным определителем и доказал теорему о бесконечности количества простых чисел в арифметической прогрессии из целых чисел, первый член и разность которой - взаимно просты. К решению этих задач он применил аналитические функции, названные функциями (рядами) Дирихле. - создал общую теорию алгебраических единиц в алгебраическом числовом поле; - в области математического анализа впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье кусочно-непрерывной и монотонной функции, что послужило обоснованием для многих дальнейших исследований; - значительны труды в механике и математической физике, в частности в теории потенциала. 4

По традиции принцип Дирихле объясняют на примере "зайцев и клеток". При применении принципа Дирихле для решения конкретной задачи, необходимо разобраться, что в ней — "клетки", а что — "зайцы". Это обычно является самым трудным этапом в доказательстве. Наиболее часто принцип Дирихле формулируется в одной из следующих форм: Формулировка 1. Если в n клетках сидит m+1 зайцев или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца . 6 Например: Если в 4 (или n) клетках сидит 5 (или n+1) зайцев, то хотя бы в одной клетке находится более одного зайца (2 зайца).

Если в n клетках сидит m голубей, причем m n, то хотя бы в одной клетке содержится не менее m:n зайцев, а так же хотя бы в одной другой клетке содержится не более m:n зайцев. 8

2.1. "Если в n клетках сидят не более n-1 "зайцев", то есть пустая "клетка". 2.2."Если в n клетках сидят n + 1 «зайцев", то есть клетка, в которой не менее 2-х "зайцев". 2.3."Если в n клетках сидят не более nk-1 "зайцев", то в какой-то из клеток сидят не более k-1 "зайцев". 2.4."Если в n клетках сидят не менее nk+1 "зайцев", то в какой-то из клеток сидят не менее k+1 "зайцев". Порядок (алгоритм) применения принципа Дирихле 1.Определить что в задаче является "клетками", а что-"зайцами". 2.Применить соответствующую формулировку (утверждение) принципа Дирихле: 9

15 Задача №6 Решение: В Москве проживает более 10 000 000 людей. На голове у каждого человека не может быть более 300 000 волос. Доказать, что наверняка найдутся 34 москвича с одинаковым числом волос на голове. На голове может быть 0, 1, …, 300 000 волос — всего 300 001 вариант. Каждого москвича отнесём к одной из 300 001 групп в зависимости от количества волос. Если 34 москвича с одинаковым количеством волос не найдутся, то это значит, что в любую из созданных групп входит не более 33 человек. Тогда всего в Москве живёт не более 33·300 001=9 900 033

Слайд 1

Слайд 2

Принцип Дирихле - Так. Если я что-нибудь в чём-нибудь понимаю, то дыра – это нора… - Ага. - А нора – это кролик… - Ага. - А кролик – это подходящая компания.

Слайд 3

Биография Дирихле Петер Август Лежён (1805-1859) — немецкий математик, иностранный член-корреспондент Петербургской Академии наук (1837), член многих других академий. Основные заслуги П. Дирихле в области математики: — установил, что в арифметической прогрессии аn = а1 + dn, где n = 1,2 . с целыми взаимно простыми а1 и d содержится бесконечно много простых чисел; — исследовал понятие условной сходимости ряда, установил признак сходимости ряда; — ввёл функциональные ряды особого вида; — ввёл (вместе с Н. И. Лобачевским) определение функции через соответствие и т. д.

Слайд 4

Цель: Познакомить учащихся с новыми математическими методами решения задач, которые не рассматриваются в школьном курсе Научить решать олимпиадные задачи с помощью принципа Дирихле; Показать его применение для решения разнообразных задач

Слайд 5

Задачи проекта: Научить решать задачи, связанные с числовыми множествами; Научить решать задачи, связанные с делимостью чисел; Научить решать некоторые геометрические задачи; Показать методику решения простейших задачи по теории вероятности.

Слайд 6

Слайд 7

3. Если m зайцев сидят в n клетках, то найдётся клетка, в которой сидят не меньше, чем m/n зайцев, и найдётся клетка, в которой сидят не больше, чем m/n зайцев 4. Если m зайцев съели n килограммов травы, то какой-то заяц съел не менее n/m килограммов травы и какой-то заяц съел не больше n/m килограммов травы 5. Если в n клетках сидят m зайцев и m больше или равно, то в какой-то из клеток сидят по крайней мере k+1 заяц

Слайд 8

Задача 1 В классе 30 человек. В диктанте Витя Медведев сделал 13 ошибок, а остальные – меньше. Докажите что по крайней мере три ученика сделали ошибок поровну.

Слайд 9

Задача 3 ( обобщенный принцип) В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

Слайд 10

Слайд 11

Слайд 12

Задача 6 В мешке лежат 10 белых и 10 черных шаров. Они тщательно перемешаны и не различимы на ощупь. Какое наименьшее количество шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара 1) одного цвета, 2) разного цвета, 3) белого цвета?

Слайд 13

Задача 7 В лесу растет миллион елок. Известно, что на каждой елке не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

Слайд 14

Задача 8 В классе 37 учеников. Докажите, что среди них найдутся 4 ученика, отмечающие день рождения в одном месяце.

Слайд 15

Задача 9 Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.

Слайд 16

Задача 10 В ковре размером 4х4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри дырок.

Слайд 17

Задача 11 В мешке лежат 100 белых и 100 черных шариков. Они тщательно перемешаны и не различимы на ощупь. Какое наименьшее количество шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара 1) одного цвета, 2) разного цвета, 3) белого цвета?

Слайд 18

Вывод: Принцип Дирихле помогает нам при решении некоторых задач. Следовательно мы можем утверждать, что принцип Дирихле облегчает решение задач.

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

По традиции принцип Дирихле объясняют на примере "зайцев и клеток". Если мы хотим применить принцип Дирихле при решении конкретной задачи, то нам предстоит разобраться, что в ней — "клетки", а что — "зайцы". Это обычно является самым трудным этапом в доказательстве. Цель этого статьи — познакомить школьника с некоторыми изюминками решения задач на принцип Дирихле.

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

Формулировка принципа Дирихле

Самая популярная формулировка принципа Дирихле звучит так:

ФОРМУЛИРОВКА 1. "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца".

Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

Принцип Дирихле можно сформулировать на языке множеств и отображений.

ФОРМУЛИРОВКА 2. "При любом отображении множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов, найдутся два элемента множества P, имеющие один и тот же образ".

Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать "зайцем", что - "клеткой", и как использовать наличие двух "зайцев", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.

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

Пример 1. Доказать, что если прямая l, расположенная в плоскости треугольника ABC, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника.

Полуплоскости, на которые прямая l разбивает плоскость треугольника ABC, обозначим через q₁ и q₂ ; эти полуплоскости будем считать открытыми (то есть не содержащими точек прямой l). Вершины рассматриваемого треугольника (точки A, B, C) будут "зайцами", а полуплоскости q₁ и q₂ - "клетками". Каждый "заяц" попадает в какую-нибудь "клетку" (ведь прямая l не проходит ни через одну из точек A, B, C). Так как "зайцев" три, а "клеток" только две, то найдутся два "зайца", попавшиев одну "клетку"; иначе говоря, найдутся такие две вершины треугольника ABC, которые принадлежат одной полуплоскости. См рисунок.

Пусть, скажем, точки A и B находятся в одной полуплоскости, то есть лежат по одну сторону от прямой l. Тогда отрезок AB не пересекается с l. Итак, в треугольнике ABC нашлась сторона, которая не пересекается с прямой l.

Пример 2. Внутри равностороннего треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5.

Средние линии правильного треугольника со стороной 1 разбивают его на четыре правильных треугольничка со стороной 0,5. Назовём их "клетками", а точки будем считать "зайцами". По принципу Дирихле из пяти точек хотя бы две окажутся в одном из четырёх треугольничков (См. рисунок). Расстояние между этими точками меньше 0,5, поскольку точки не лежат в вершинах треугольничков. (Здесь использована известная лемма о том, что длина отрезка, расположенного внутри треугольника, меньше длины его наибольшей стороны.)

Пример 3. На краю круглого стола расположены на одинаковом расстоянии друг от друга n флагов стран, за столом сидят n послов этих стран, причём каждый посол сидит рядом с чужим флагом. Доказать, что существует такое вращение стола, после которого хотя бы два посла окажутся рядом с флагом своей страны.

Решение Существует n-1 способов вращения стола, после каждого из них взаимное расположение флагов и послов изменится. Каждому послу сопоставим вращение, после которого он окажется рядом со своим флагом. Согласно принципу Дирихле при каком-то вращении два (может, и больше) посла окажутся рядом со своим флагом. В решении задачи роль "зайцев" играют, естественно, послы, а роль "клеток" - положения стола при различных вращениях. Посол попадает в "клетку", если при соответствующем этой "клетке" вращении стола он оказывается рядом с флагом своей страны. Таким образом, "клеток" у нас n-1, а "зайцев" - n. Замечание Условие о том, что вначале ни один из послов не находится рядом со своим флагом, существенно. На самом деле первоначальное положение также является "клеткой", но эта "клетка" по условию заведомо окажется пустой. Так что можно считать, что всего "клеток" имеется n-1.

Пример 4. Доказать, что для любого действительного числа a > 0 и любого натурального N найдутся такие целые m і 0 и k > 0, что |ka-m| Ј 1 /_N .

Решение Разобьём отрезок [0, 1] точками 1 /_N , 2 /_N , . . . , [(N-1)/( N)] на N отрезков (См. рисунок). Полученные отрезки будем считать "клетками", а числа 1, 2, . . . , N+1 примем в качестве "зайцев".

Если k - один из "зайцев", то число ka можно записать в виде ka = m + x, где m - целое, 0Ј x 1 /_N .

то есть числа k = k₂ - k₁ и m = m₂ - m₁ являются искомыми. Здесь k > 0, так как k₂ > k₁ , и m і 0, так как k₂ a - k₁ a = (m₂ + x₂ ) - (m₁ + x₁ ) > 0, откуда m₂ - m₁ > x₁ - x₂ > -1 (ведь 0 Ј x₁ 1 /₅ ·[(Ц2)/ 2] = [1/( [Ц50])] 1 /₇ , поэтому этот квадратик можно накрыть кругом радиуса 1/7.

Принцип Дирихле в теории чисел

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

ТЕОРЕМА 1. Пусть p, q - натуральные числа, p 2 - x + 41, который при всех целых x от -39 до 40 включительно принимает только простые значения (т.е. при x = 0, ±1, ±2, . . . , ±39, 40). Однако при x = 41 и x = 42 значения этого многочлена будут уже составными числами. В общем случае многочлен с целыми коэффициентами не может при всех натуральных значениях аргумента принимать только простые значения.

ТЕОРЕМА 2. Любой многочлен с целыми коэффициентами (отличный от константы) при некотором натуральном значении аргумента принимает значение, представляющее собой составное число.

Доказательство Пусть f(x) = a₀ x n + a₁ x n - 1 +. . . +a_n , где все a_i - целые числа. Предположим, что при некотором k значение многочлена f(x) - простое число, т.е. f(k) = p, где p - простое. Многочлен степени n принимает одно и то же значение не более чем в n точках. (Действительно, если f(x) = y₀ более чем в n точках x₁ , x₂ , . . ., x_{n + 1} , то многочлен g(x) = f(x)-y₀ имеет корни x₁ , x₂ , . . ., x_{n + 1} , а, как известно, любой многочлен не может иметь более n действительных корней.) Покажем, что найдётся такое целое t, что f(k+pt) отлично от 0 и p. Нам поможет принцип Дирихле. Будем считать значени многочлена (в натуральных точках) "клетками", а натуральные числа вида k+pt "зайцами". Натуральное число N = k+pt будем помещать в "клетку", соответствующую значению многочлена f(N). Согласно высказанному выше утверждению, в "клетке" не может поместитьс больше n "зайцев". Так как "зайцев" много, то это значит, что f(k + pt) не может принимать только значени 0 и p при различных целых t, т.е. найдётся "заяц" k+pt, который не попадёт ни в "клетку" 0, ни в "клетку" p. Итак, при некотором t имеем: f(k + pt) № 0 и f(k + pt) № p. Разлагая f(k + pt) по степеням pt (используя бином Ньютона), получим

где все c_i - некоторые целые числа. Поскольку f(k) = p, из предыдущего равенства получаем, что f(k + pt) делится на p, причём f(k + pt) № 0 и f(k + pt) № p, так что f(k + pt) - составное число. Теорема доказана.

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

Следующая теорема, сформулированная П. Ферма, является одним из самых фундаментальных фактов в теории делимости целых чисел и находит широкое применение как в теоретических исследованиях, так и в арифметических приложениях.

МАЛАЯ ТЕОРЕМА ФЕРМА. Если p - простое число, a - целое число, не делящееся на p, то a p - 1 при делении на p даёт остаток 1, т. е.

Доказательство Каждое из p - 1 чисел a, 2a, . . ., (p-1)a ("зайцев") даёт при делении на p ненулевой остаток (ведь a не делится на p):

где N - некоторое целое число. Следовательно, (p-1)!·(a p-1 -1) делится на p, а тогда и a p - 1 - 1 делится на p. Теорема доказана.

Следствие. Если p - простое число, то при любом целом a разность a p - a делится на p.

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

"Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".

При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2, . . . , p-1. Они то и играют здесь роль "клеток", а сами целые числа являются "зайцами". Так как чисел ("зайцев") больше, чем остатков ("клеток"), то хотя бы два числа "сидят в одной клетке", т.е. имеют одинаковые остатки при делении на p. Рассмотрим классические примеры.

Пример 10. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.

Решение По крайней мере два числа из 11 дают одинаковый остаток при делении на 10 (принцип Дирихле). Пусть это будут A = 10a + r и B = 10b + r. Тогда их разность делится на 10: A - B = 10(a - b).

Пример 11. Доказать, что если имеется 100 целых чисел x₁ , x₂ , . . . , x₁₀₀ , то из них можно выбрать несколько чисел (может быть, одно), сумма которых делится на 100.

Решение Рассмотрим 100 следующих сумм:

Если хотя бы одна из этих сумм делится на 100, то наша цель достигнута. Допустим, что ни одно из чисел S₁ , S₂ , . . . , S₁₀₀ не делится на 100. Значит, два из них при делении на 100 дают равные остатки (т. к. сумм у нас 100, а различных остатков может быть лишь 99). Пусть это S_n и S_m (n l). Их разность a_k - a_l = 10 l ·a_{k - l} делится на 1997. Так как 10 l и 1997 - взаимно просты, то a_{k - l} делится на 1997. Это число Петя сможет записать.

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ. Если числа a₁ , a₂ , . . . , a_n попарно взаимно просты, то для любых остатков r₁ , r₂ , . . ., r_n таких, что 0 Ј r_i 99S, поэтому

Sў₁ + Sў₂ +. . .+ Sў₁₀₀ = (S- S₁ )+ (S- S₂ )+. . .+ (S- S₁₀₀ ) = 100S-(S₁ + S₂ +. . .+ S₁₀₀ ) 8AB, то на отрезке AB есть точка, принадлежащая проекциям по крайней мере девяти кругов. Прямая, проходящая через эту точку и перпендикулярная диаметру AB, - искомая.

Пример 15. Дана фигура площади больше N. Доказать, что в ней найдутся N+1 точек, разности соответствующих координат которых - целые числа.

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

Площади проекций частей фигуры в сумме дадут площадь самой фигуры, т.е. больше N. Поэтому на выделенной клетке (площади 1) согласно принципу Дирихле найдётся точка X, покрытая не менее N+1 кусочками фигуры. Вернёмся теперь к исходной фигуре и отметим на ней N+1 точек, проектирующихся в точку X при переносе клеток. Эти точки будут искомыми, т.к. после переноса кусочка фигуры в выделенную клетку координаты каждой точки этого кусочка изменяются на целое число.

Пример 16. В кубе с ребром a лежит ломаная, которую каждая плоскость, параллельная одной из граней, пересекает не более k раз. Доказать, что длина ломаной меньше 3ka.

Решение Введём в пространстве прямоугольную систему координат, оси которой направим вдоль рёбер куба. Пусть ломаная состоит из нескольких отрезков, длины которых мы обозначим через L_k .

Пусть x_k , y_k , z_k - проекции отрезка L_k на оси координат. Тогда L_k = [Ц(x 2 _k +y 2 _k +z 2 _k )]. Задачу будем решать методом от противного. Допустим, что длина ломаной не меньше 3ka. Тогда попробуем найти плоскость, параллельную одной из граней, которая пересечёт ломаную не менее чем в k+1 точках. Спроектируем ломаную на три грани куба, расположенные в плоскостях XOY, YOZ и XOZ, и рассмотрим одну из таких проекций, например, XOY (См. рисунок).

Каждый k-ый отрезок спроектированной ломаной образует также 4 проекции на сторонах квадрата, сумма длин которых равна 2(x_k + y_k ). Если сложить длины всех таких проекций для каждого отрезка, то получим S2(x_k + y_k ). Если бы эта величина была больше 4ka (т.е. более чем в k раз превосходила периметр квадрата), то по принципу Дирихле на одной из сторон квадрата нашлась бы точка, покрытая не менее чем k+1 проекциями. Тогда прямая, проведенная через эту точку и параллельная стороне квадрата, пересечёт проекцию исходной ломаной не менее чем в k + 1 точках. Значит, если через эту прямую провести плоскость, параллельную грани, то она пересечет исходную ломаную по крайней мере в k + 1 точках.

Осталось показать, что для одной из трёх граней, на которые проектировалась ломаная, сумма длин проекций, лежащих на сторонах квадрата, будет больше 4ka, т.е. одна из величин S2(x_k + y_k ), S2(z_k + y_k ), S2(x_k + z_k ) больше 4ka. Длина ломаной равна SL_k = S[Ц(x 2 _k +y 2 _k +z 2 _k )] и по предположению не меньше 3ka. Поэтому получаем

Если сумма трёх слагаемых больше 3·4ka, то по крайней мере одно из них больше 4ka, что и требовалось.

Непрерывный принцип Дирихле

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

"Если сумма n чисел больше S, то по крайней мере одно из этих чисел больше S/n".

По-другому его можно сформулировать так:

"Если среднее арифметическое нескольких чисел больше a, то хотя бы одно из этих чисел больше a";

или в терминах "зайцев":

"Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг травы".

Кроме того, существует простая геометрическая интерпретация непрерывного принципа Дирихле:

"Пусть из некоторой точки на плоскости проведено N различных лучей; тогда угол между некоторыми двумя из них не менее 360 ° /N".

Понятно, что если рассматривать только углы между соседними лучами, то всего получится N углов (См. рисунок). В сумме они составляют полный угол, равный 360 ° . Следовательно,

по непрерывному принципу Дирихле градусная мера одного из этих углов не менее 360 ° /N (иначе их сумма будет меньше 360 ° ).

Рассмотренный принцип называется непрерывным постольку, поскольку здесь числа (или градусные меры углов) могут принимать любое значение из некоторого промежутка, в то время как принцип Дирихле в обычном смысле оперирует с дискретным набором объектов ("зайцев") - было бы абсурдным предполагать, что в клетке может оказаться, скажем, два с половиной зайца.

Пример 17. На плоскости дано n попарно непараллельных прямых. Доказать, что найдутся две из них, угол между которыми не меньше 180 ° /n.

Указание. Достаточно перенести прямые параллельно самим себе так, чтобы все они проходили через одну точку. Из этой точки будет выходить 2n лучей, и теперь можно применить принцип Дирихле.

Пример 18. На полях шахматной доски 8×8 расставлены действительные числа, каждые два из которых отличаются не менее чем на 1/9. Доказать, что есть пара соседних (имеющих общую сторону) клеток, разность чисел в которых не меньше 1/2.

Решение Пусть A - наименьшее из выписанных на доске чисел, а B - наибольшее. Покажем, что B-A і7.

Запишем числа в порядке возрастания (заметим, что никакие два числа не равны):

Читайте также: