Принцип Дирихле - Разработка контрольных работ по математике

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

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

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

В самой простой и несерьезной форме он выглядит так:

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

Действительно, если в каждой клетке не больше двух зайцев, то всего зайцев не больше чем 2*3=6, что противоречит условию.

Существует более общая формулировка:

Если z зайцев сидят в k клетках, то найдется клетка, в которой не менее z/k зайцев. Не надо бояться дробного число зайцев: если получается, что в ящике не меньше 7/3 зайцев, значит, их больше двух.

Доказательство принципа Дирихле в этой формулировке очень простое, но заслуживает внимания, поскольку похожие рассуждения "от противного" часто встречаются. Допустим, что в каждой клетке число зайцев меньше, чем z/k. Тогда в k клетках зайцев меньше, чем k - z/k = z. Получили противоречие.

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

Вот общая формулировка принципа Дирихле:

Если имеется n ящиков, в которых находится в общей сложности не менее n+1 предмета, то непременно есть ящик, в котором лежат, по крайней мере, 2 предмета.

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

Задача 1

В самолете летят 380 пассажиров. Докажем, что, по крайней мере, двое из них родились в один и тот же день года.

Решение. Всего в году 365 или 366 дней, а пассажиров в самолете 380 - значит, их дни рождения не могут приходиться только на различные даты. Вообще, если пассажиров больше, чем 366, то хотя бы у двоих дни рождения совпадают. А вот если пассажиров 366, не исключено, что все они родились в разные дни года, но это маловероятно. (Согласно теории вероятностей, в случайно выбранной группе численностью свыше 22 человек совпадение дней рождения у некоторых из них более вероятно, нежели то, что у всех дни рождения приходятся на разные дни года).

Задача 2

В шахматной партии черные сдались после 15-го хода белых. Требуется доказать, что хотя бы одна из черных фигур ни разу не покидала своего поля (к фигурам отнесем и пешки).

Решение. Если шахматный ход не рокировка (обмен местами), то передвигается одна фигура, в случае рокировки - две. Черные успели сделать 14 ходов (так как первыми ходят белые), и по правилам игры лишь один из них мог быть рокировкой. Поэтому самое большое количество черных фигур, сделавших ходы, - 15. Всего же черных фигур 16. Значит, по крайней мере, какая-то из них не сделала ни одного хода.

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

Рассмотрим решение еще нескольких задач.

Задача 3

В строку выписано 5 натуральных чисел: a1,a2,a3,a4,a5. Докажите, что - либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.

Решение. Рассмотрим 5 чисел: а1,

А1+а2,

А1+а2+а3,

А1 +а2+а3+а4,

А1 +а2+а3+а4+а5.

Если одно из них делится на 5, то все в порядке, утверждение справедливо. В противном случае при делении на 5 они дают в остатке какие-то из четырех чисел: 1,2,3,4. По принципу Дирихле остатки, по крайней мере, двух из выписанных 5 чисел совпадают. Разность их делится на 5. Но эта разность - одно из чисел, данных в задаче, или сумма нескольких из них, стоящих рядом.

Задача 4

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

Решение. Разобьем квадрат на 25 равных квадратиков со стороной 0,2м. Докажем, что в каком-то из них находятся, по крайней мере, три точки. Применим принцип Дирихле: если бы в каждом квадратике (внутри или на сторонах) было не больше двух точек, то всего их бы было не больше 2*25=50. Но всего бросили в квадрат 51 точку. Получили противоречие.

Задача 5

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

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

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

Другое применение принципа Дирихле

Принцип Дирихле можно применять при решении задач на знакомства;

Пример: доказать, что среди 5 человек, по крайней мере двое из них имеют одинаковое число знакомых среди выбранных.

Указание. Рассматриваются все возможные варианты количества знакомых данных 5 человек.

Задач на делимость;

Пример: Доказать, что среди любых 12 натуральных чисел можно выбрать 2, разность которых делится на 11.

Указание. Рассматриваются все возможные остатки при делении числа на 11. геометрических задач (задача 4, 5).

Контрольная работа №2 для учащихся 8 классов

Приведенные ниже задания являются контрольной работой №2 для учащихся 8 классов. Каждая задача оценивается в 5 баллов, для зачета нужно набрать не менее 25 баллов.

Правила оформления работ:

Решения по каждому предмету оформляется отдельно. Каждое задание имеет свой шифр (М 8.2.1 и т. д.), который указывается перед записью решения. Переписывать текст задачи не надо, достаточно краткой записи, если это необходимо. Оформлять решения в порядке следования заданий. Можно присылать нам столько решений, сколько удалось вам сделать, даже если оказалось невозможным выполнить всю работу.

В классе 30 человек. В диктанте Вова сделал 13 ошибок, а остальные - меньше. Докажите, что по крайней мере 3 ученика сделали ошибок поровну (может быть, по 0 ошибок).

В классе 40 учеников. Найдется ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?

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

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

В поход пошли 20 туристов. Самому старшему из них 35 лет, а самому младшему а) 16 лет б) 17 лет. Верно ли, что среди туристов есть одногодки?

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

Каждый из 10 участников переговоров послал по их окончании поздравительные открытки пятерым другим участникам. Докажите, что какие-то двое послали открытки друг другу.

Указание. Докажите сначала, что хотя бы один участник получил не менее пяти открыток.

На шахматной доске стоят 44 ферзя. Докажите, что каждый из них бьет какого-нибудь другого ферзя.

Указание. При любом положении на доске ферзь бьет не менее 21 поля.

На плоскости нарисовали 5 прямых. Докажите, что угол между какими-то двумя из них не больше 36°. (Если какие-нибудь прямые параллельны, считайте, что угол между ними равен 0°.)

Указание. Угол между прямыми не изменяется, если к ним применить параллельный перенос (для каждой прямой -- свой перенос).

Найдите значение дроби

,

Где разные буквы -- это разные цифры.

Указание. В дроби записаны 10 разных букв, соответствующие 10 различным цифрам.

Элементы теории сравнений

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

В этой статье мы рассмотрим основные понятия этой теории, их свойства и некоторые приложения.

Определение и свойства сравнений

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

Примеры. 1. Числа 5 и 54 равноостаточные при делении на 7 (в остатке при делении на 7 оба дают 5).

2. Числа -17; 3; 15 равноостаточные при делении на 4.

Теорема 1.2. Для того, чтобы числа и были равноостаточными необходимо и достаточно, чтобы разность делилась на.

Определение 1.3. Целые числа и называются сравнимыми по модулю, если разность делится на.

Обозначение

Читается это так: "сравнимо с по модулю. Сама запись (*) называется сравнением.

Замечания.

Теорема 1.3 утверждает, что определения 1.1 и 1.3 равносильны.

Число, стоящее под знаком будем всегда считать положительным, т. к. сравнение по модулю совпадает со сравнением по модулю.

Если

,

То будем записывать

-

Не сравнимо с по модулю.

Пример. 1.

,

Т. к.

2. , т. к.

Перечислим основные свойства сравнений:

Любое целое число сравнимо с самим собой по любому натуральному модулю.

Если, то

Если и, то

Сравнения по одинаковому модулю можно почленно складывать и вычитать, т. е.

Если и, то

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

Если, то

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

Если, то или

Сравнения по одинаковому модулю можно почленно перемножать, т. е.

Если и, то

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

Если, то

Обе части сравнения можно умножать на одно и тоже целое число, т. е.

Если, то

Обе части сравнения можно делить на их общий делитель, если он взаимно прост с модулем, т. е.

Если и, то

Обе части сравнения и модуль можно умножить на одно и тоже целое положительное число, т. е.

Если то

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

Если и, , , то

Если сравнение имеет место по нескольким модулям, то оно имеет место по модулю, равному наименьшему общему кратному данных модулей, т. е.

Сравнение вычет остаток степень плоскость

Если, ,...,, то, где

Если сравнение имеет место по модулю, то оно имеет место и по модулю, равному любому натуральному делителю числа.

Если одна часть сравнения и модуль делятся на какое-нибудь число, то и другая часть сравнения делится на это число.

Задача 1. Показать, что если

, то.

Решение. 1. Воспользовавшись свойством 9 умножим обе части сравнения

На 4, тогда получим следующее сравнение:

2. Заметим, что

, а,

Поэтому ;

Далее: ;

И, наконец, очевидно,

Что

Таким образом, имеем три сравнения:

; ,

3. По свойству сравнений 4, получаем

,

Что и требовалось доказать.

Задача 2.

Выражение

Есть целое число. Доказать, что число

Тоже целое.

Решение. 1. Так как

- целое,

Делится на 19, следовательно

2. Умножим обе части полученного сравнения на 12, получим сравнение

.

3. Очевидно, что

,

Следовательно

И по свойству 9

,

Аналогично можно получить

.

4. По свойству 4,

,

Следовательно по определению сравнимых чисел

Делится на 19, а это и означает, что

Целое число.

Вычеты по данному модулю, системы вычетов

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

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

Обозначение

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

Пример. Рассмотрим класс вычетов по модулю 3, порожденный числом 11, т. е. . Вычетами этого класса являются, например числа 2; 23;-13;... всего вычетов в классе будет бесконечно много.

Рассмотрим свойства классов вычетов по данному модулю.

Класс вычетов по данному модулю совпадает с множеством чисел вида

,

Где - любое целое число.

Два класса вычетов и совпадают в том и только в том случае, когда

.

Если два класса вычетов и имеют хотя бы один общий элемент, то они совпадают.

Число классов вычетов по конечно и равно ; число вычетов в каждом классе вычетов бесконечно.

Замечания.

    1. Введение классов вычетов позволяет, таким образом, заменять сравнение равенством соответствующих классов, и наоборот, равенство классов - соответствующим сравнением. 2. Отношение сравнения по данному модулю разбивает все множество целых чисел на непересекающиеся классы вычетов.

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

Замечания.

    1. Согласно свойству 4, полная система вычетов по состоит из чисел. 2. Обычно в качестве полной системы вычетов употребляется полная система наименьших неотрицательных вычетов по данному модулю, т. е. система чисел: .

Пример. Числа 12; -23; 2; 63;- 2; 5 образуют полную систему вычетов по.

Определение 2.4. Совокупность чисел, взятых из полной системы вычетов и взаимно простых с модулем, называется приведенной системой вычетов по этому модулю.

Задача 3

Показать, что числа 25; -20; 16; 46; -21; 18; 37; -17 составляют полную систему вычетов по модулю.

Решение. 1. По свойству 4, ПСВ, в данном случае, должна состоять равно из 8 чисел, что мы и имеем.

2. В соответствии с определением, так как числа берутся по одному и только по одному из каждого класса вычетов по данному модулю, все числа должны быть не сравнимы по модулю 8, что, по определению 1.3 и теореме 1.2, они должны иметь равные остатки при делении на 8. Найдем остаток от деления каждого из восьми чисел на 8:

; ; ; ; ; ; ; .

Все остатки разные.

Из 1 и 2, на основании определения 2.3 следует, что числа 25; -20; 16; 46; -21; 18; 37; -17 образуют полную систему вычетов по модулю 8

Похожие статьи




Принцип Дирихле - Разработка контрольных работ по математике

Предыдущая | Следующая