Страница 3

Дискретная математика

Принцип Дирихле [4, c. 105]

Пусть f : A → B - функция, причём как A, так и B - конечные множества. Предположим, что A состоит из n элементов: a₁, a₂,..., a_n. Принцип Дирихле гласит, что если |A| > |B|, то по крайней мере одно значение f встретится более одного раза¹. Проще говоря, найдётся пара элементов a_i ≠ a_j, для которых f(a_i) = f(a_j).

Чтобы убедиться в истинности принципа, предположим, что для любой пары разных индексов i ≠ j мы имеем: f(a_i) ≠ f(a_j). Тогда множество B содержит по крайней мере n различных элементов: f(a₁), f(a₂),..., f(a_n). И уж во всяком случае, |B| ≥ n, что противоречит предположению: n = |A| > |B|. Следовательно, есть хотя бы два разных элемента a_i, a_j ∈ A, для которых f(a_i) = f(a_j).

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