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

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

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

На той же идее основано доказательство того, что при обращении обыкновенной дроби , ,  в десятичную получается или конечная, или бесконечная периодическая десятичная дробь, причем длина периода не превосходит . Будем делить  на  «уголком» и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то не позже, чем на -м шагу начнут повторяться остатки, а вслед за этим – и цифры в частном.