Олимпиадные задачи, решаемые с использованием принципа Дирихле

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

В ряде задач применяют следующее обобщение принципа Дирихле.

ФОРМУЛИРОВКА 3. "Если nk+1 зайцев размещены в n клетках, то найдутся k+1 зайцев, которые посажены в одну клетку (n, k - натуральные числа)".

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

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

ТЕОРЕМА 1. Пусть p, q - натуральные числа, p < q. Если обыкновенную дробь p/q обратить в десятичную, то получится либо конечная, либо бесконечная периодическая десятичная дробь, причём длина периода не превосходит q-1.

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

Комбинаторные задачи, приемы и методы их решения.

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

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

Что же такое комбинаторика?

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

Комбинаторные задачи обладают общей особой приметой. Этой приметой является вопрос задачи, который всегда можно сформулировать так, что он будет начинаться словами: «Сколько … ?», «Сколькими способами …?».

Комбинаторные задачи различаются по подходам к решению. Рассмотрим некоторые основные комбинаторные идеи, лежащие в основе решения некоторых из них.

правило произведения:

Пусть нам даны k множеств по n₁, n₂, n₃, n₄,... ,n_k элементов каждое, и нам нужно произвести выбор по одному в каждом из множеств, тогда число возможных способов находим так:

N = n₁ n₂ n₃ n₄ ...n_k.

Обобщение: на каждое из m мест может быть поставлен элемент n – элементного множества. Тогда количество способов расположения элементов можно найти по формуле mⁿ.

Перестановкой из n элементов называют упорядоченный набор этих элементов. Обозначают P_n.

Размещением из n элементов по k называется упорядоченное подмножество из n элементов множества, имеющего k элементов. Обозначается A_kⁿ

Cочетанием из n элементов по k называется неупорядоченное подмножество из n элементов множества, имеющего k элементов. Обозначается C_kⁿ.

Диафантовы уравнения

ДИОФАНТОВЫ УРАВНЕНИЯ - алгебраические уравнения или системы алгебраических уравнений, решения которых отыскиваются в целых или рациональных числах. Обычно предполагается, что Д. у. имеют число неизвестных, превосходящее число уравнений, в связи с чем они называются также неопределенными уравнениями.

Решение уравнений в целых числах является одной из древнейших математических задач. Уже в начале 2-го тысячелетия до н. э. вавилоняне умели решать системы таких уравнений с двумя неизвестными. Наибольшего расцвета эта область математики достигла в Древней Греции. Уравнения названы в честь греческого математика Диофанта, который жил в третьем веке нашей эры.

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

Диофантовыми уравнениями называются уравнения вида , где - многочлен с целыми коэффициентами.

При исследовании диофантовых уравнений обычно ставятся следующие вопросы:

1. имеет ли уравнение целочисленные решения;

2. конечно или бесконечно множество его целочисленных решений;

3. решить уравнение на множестве целых чисел, т. е. найти все его целочисленные решения;

4. решить уравнение на множестве целых положительных чисел;

5. решить уравнение на множестве рациональных чисел.

Дата добавления: 2018-05-13; просмотров: 397; Мы поможем в написании вашей работы!
Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 7 8 Следующая ⇒

Мы поможем в написании ваших работ!