Дирихле принцип

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

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

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