Принцип Дирихле (комбинаторика): различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
LGB (обсуждение | вклад) отмена правки 96795560 участника 82.137.176.62 (обс.) Метка: отмена |
→Примеры применения: исправление |
||
Строка 39:
'''Теорема 2'''. Для любого положительного [[Иррациональное число|иррационального числа]] <math>a</math> существует бесконечно много дробей <math>{p \over q}</math>, отличающихся от <math>a</math> менее, чем на <math>\frac{1}{q^2}</math> (это одна из версий [[Теорема Дирихле о диофантовых приближениях|теоремы Дирихле о диофантовых приближениях]])<ref>{{книга |автор=Дуран, Антонио. |заглавие=Поэзия чисел. Прекрасное и математика |место=М. |издательство=Де Агостини |год=2014 |страниц=160 |isbn=978-5-9774-0722-9 |серия=Мир математики: в 45 томах, том 27 |страницы=57}}</ref> {{sfn |Алфутова Н. Б, Устинов А. В.|2009|с=19}}.
'''Доказательство'''. Для произвольного [[натуральное число|натурального числа]] <math>N</math> составим набор из <math>(N+1)</math>
: <math>a-[a];\ 2a-[2a];\ 3a-[3a];\ \dots (N+1)a-[(N+1)a]</math>, где <math>[x]</math>обозначает [[Целая часть|целую часть]] числа.
Все эти числа принадлежат интервалу от 0 до 1. Распределим числа из интервала (0, 1) в <math>N</math> ящиков: в первый ящик попадут числа от 0 до <math>1/N,</math> во второй — от <math>1/N</math> до <math>2/N,</math> {{итд}}. Разности <math>ka-[ka]</math> тоже попадут в эти ящики. Но поскольку их больше, чем число ящиков, то по принципу Дирихле в одном из ящиков будут не менее двух разностей: <math>(ia-[ia])</math> и <math>(ja-[ja]) (i<j).</math> ▼
▲Все эти числа принадлежат интервалу от 0 до 1. Распределим
Значения разностей по построению отличаются менее чем на <math>1/N.</math> Обозначив <math>q=j-i, p=[ja]-[ia],</math> получим:▼
▲Значения разностей по построению отличаются менее чем на <math>1/N.</math>
: <math>|qa-p|<{1 \over N},</math> или: <math>\left|a-{p\over q}\right|<\frac{1}{qN}\leqslant \frac{1}{q^2}</math> (поскольку <math>q \leqslant N</math>)
В силу произвольности числа <math>N</math> близость дроби к числу <math>a</math> можно сделать
Дополнительные примеры см. в статье [[Китайская теорема об остатках]] и в книге Н. Б. Алфутовой и А. В. Устинова{{sfn |Алфутова Н. Б, Устинов А. В.|2009|с=17—20}}.
| |||