53 lines
2.8 KiB
HTML
53 lines
2.8 KiB
HTML
|
<!DOCTYPE html>
|
||
|
|
<html lang="en">
|
||
|
|
<head>
|
||
|
|
<meta charset="UTF-8" />
|
||
|
|
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
|
||
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
|
||
|
|
<title>Страница 3</title>
|
||
|
|
</head>
|
||
|
|
<body>
|
||
|
|
<p style="text-align: center">
|
||
|
|
<i><b>Страница 3</b></i>
|
||
|
|
</p>
|
||
|
|
<hr />
|
||
|
|
<h1 style="text-align: center">Дискретная математика</h1>
|
||
|
|
<h2 style="text-align: center">Принцип Дирихле [4, c. 105]</h2>
|
||
|
|
<p>
|
||
|
|
Пусть <i>f : A <i style="text-align: justify">→ </i>B</i> -
|
||
|
|
функция, причём как <i>A</i>, так и <i>B</i> - конечные множества.
|
||
|
|
Предположим, что <i>A</i> состоит из <i>n</i> элементов:
|
||
|
|
<i>a<sub>1</sub>, a<sub>2</sub>,..., a<sub>n</sub></i
|
||
|
|
>. Принцип Дирихле гласит, что если <i>|A| > |B|</i>, то по крайней
|
||
|
|
мере одно значение <i>f</i> встретится более одного раза<sup>1</sup>.
|
||
|
|
Проще говоря, найдётся пара элементов
|
||
|
|
<i
|
||
|
|
>a<sub>i </sub><i style="text-align: center">≠</i
|
||
|
|
><sub> </sub>a<sub>j</sub></i
|
||
|
|
>, для которых <i>f(a<sub>i</sub>) = f(a<sub>j</sub>)</i>.
|
||
|
|
</p>
|
||
|
|
<p>
|
||
|
|
Чтобы убедиться в истинности принципа, предположим, что для любой пары
|
||
|
|
разных индексов
|
||
|
|
<i>i <i style="text-align: center">≠ </i>j</i> мы имеем:
|
||
|
|
<i>f(a<sub>i</sub>) </i><i style="text-align: center">≠ </i
|
||
|
|
><i>f(a<sub>j</sub>)</i>. Тогда множество <i>B</i> содержит по крайней
|
||
|
|
мере <i>n</i> различных элементов:
|
||
|
|
<i>f(a<sub>1</sub>), f(a<sub>2</sub>),..., f(a<sub>n</sub>)</i>. И уж во
|
||
|
|
всяком случае, <i>|B| ≥ n</i>, что противоречит
|
||
|
|
предположению: <i>n = |A| > |B|</i>. Следовательно, есть хотя бы два
|
||
|
|
разных элемента
|
||
|
|
<i
|
||
|
|
>a<sub>i</sub>, a<sub>j </sub
|
||
|
|
><i style="text-align: justify">∈ </i>A</i
|
||
|
|
>, для которых <i>f(a<sub>i</sub>) = f(a<sub>j</sub>)</i>.
|
||
|
|
</p>
|
||
|
|
<hr />
|
||
|
|
<p>
|
||
|
|
<sup>1</sup>Допуская некоторую вольность, принцип Дирихле можно
|
||
|
|
переформулировать в легко запоминающейся форме: нельзя рассадить 10 зайцев
|
||
|
|
в 9 клеток так, чтобы в каждой клетке сидел один заяц - Прим. перев.
|
||
|
|
</p>
|
||
|
|
</body>
|
||
|
|
</html>
|