13.Олимпиадные задачи. Инварианты. Полуинварианты.

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

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

Классическая формулировка звучит так: «Если кроликов сидят в ящиках, то найдётся ящик, в котором сидит, по крайней мере, два кролика».

Доказательство этого утверждения также строится от противного:

Предположим, что в каждом ящике сидит менее двух кроликов (один или ни одного). Тогда во всех ящиках в совокупности сидит не более кроликов. Противоречие.

Аналогично доказывается общая формулировка принципа Дирихле: «Если кроликов сидят в ящиках, то найдётся ящик, в котором сидят не меньше чем кроликов».

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

Немного иначе это утверждение выглядит так: «Если кроликов сидят в ящиках, то найдётся ящик, в котором сидит, по крайней мере, кроликов».

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

Задача: Имеется конфет сортов. Верно ли, что не менее из них будут какого-то одного сорта?

Решение. Пусть «клетками» у нас будут сорта конфет, а «кроликами» – сами конфеты. По принципу Дирихле найдется «клетка», в которой не менее «кроликов». Так как , то найдется конфет одного сорта.

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более , то есть не превышает восьми. Тогда всего конфет не больше , а по условию их . Противоречие.

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

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

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

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

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

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

Произведение P_n = 10•9•8•...•2•1 можно записать короче P_n = 10! = 3628800.

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

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

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