ДИРИХЛЕ ПРИНЦИП

Этот принцип утверждает, что если множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов, где N > n, то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика П. Г. Л. Дирихле (1805—1859), который успешно применял его к доказательству арифметических утверждений.

По традиции в популярной литературе принцип Дирихле объясняют на примере «зайцев и клеток»: если N зайцев сидят в n клетках и N > n, то хотя бы в одной клетке сидит более одного зайца. Часто применяют обобщение принципа Дирихле: если зайцев N > nk, то хотя бы в одной клетке сидит более к зайцев. Самая популярная задача на прямое применение принципа Дирихле такова: на Земле живет 3 млрд. человек, у каждого на голове — не более миллиона волос (цифры условные). Нужно доказать, что обязательно найдутся два человека с одинаковым числом волос. А какое число людей с одинаковым числом волос можно гарантировать?

На той же идее основано доказательство того, что при обращении обыкновенной дроби p/q, p < q, q > 0 в десятичную получается или конечная, или бесконечная периодическая десятичная дробь, причем длина периода не превосходит q - 1. Будем делить p на q «уголком» и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то не позже, чем на (q - 1)-м шагу начнут повторяться остатки, а вслед за этим — и цифры в частном.