ДИРИХЛЕ ПРИНЦИПЭтот принцип утверждает, что если множество из элементов разбито на непересекающихся частей, не имеющих общих элементов, где , то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика П. Г. Л. Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений. По традиции в популярной литературе принцип Дирихле объясняют на примере «зайцев и клеток»: если зайцев сидят в клетках и , то хотя бы в одной клетке сидит более одного зайца. Часто применяют обобщение принципа Дирихле: если зайцев , то хотя бы в одной клетке сидит более зайцев. Самая популярная задача на прямое применение принципа Дирихле такова: на Земле живет 3 млрд. человек, у каждого на голове – не более миллиона волос (цифры условные). Нужно доказать, что обязательно найдутся два человека с одинаковым числом волос. А какое число людей с одинаковым числом волос можно гарантировать? На той же идее основано доказательство того, что при обращении обыкновенной дроби , , в десятичную получается или конечная, или бесконечная периодическая десятичная дробь, причем длина периода не превосходит . Будем делить на «уголком» и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то не позже, чем на -м шагу начнут повторяться остатки, а вслед за этим – и цифры в частном.
|