Читать онлайн «Принцип Дирихле»

САМАРСКИЙ МУНИЦИПАЛЬНЫЙ КОМПЛЕКС НЕПРЕРЫВНОГО ОБРАЗОВАНИЯ «Университет Наяновой» А. А. Андреев, Г. Н. Горелов, А. И. Люлев, А. Н. Савин Серия А: MATEMATUKA САМАРА 1997 САМАРСКИЙ МУНИЦИПАЛЬНЫЙ КОМПЛЕКС НЕПРЕРЫВНОГО ОБРАЗОВАНИЯ «Университет Наяновой» АЛ. Андреев, Г. Н. Горелов, А. И. Люлев, АН. Савин Принцип Дирихле Серия А: Математика Выпуск 1 Издательство «Пифагор» Самара 1997 Серия А: Математика Андреев А. А. , Горелов Г. Н. , Люлев А. И. , Савин А. Н. Принцип Дирихле. Учебное издание. Серия А: Математика. Вып. 1. — Самара: Пифагор, 1997. — 21 с, ил. При решении многих задач используется логический метод рассуждения — "от противного". В данной брошюре рассмотрена одна из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из N элементов разбито на п непересекающихся частей, не имеющих общих элементов, где N>n, то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика П. Г. Л. Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений. По традиции принцип Дирихле объясняют на примере "зайцев и клеток". Если мы хотим применить принцип Дирихле при решении конкретной задачи, то нам предстоит разобраться, что в ней — "клетки", а что — "зайцы". Это обычно является самым трудным этапом в доказательстве. Цель этого сборника — познакомить читателя с некоторыми изюминками решения задач на принцип Дирихле. В конце сборника приведены задачи для самостоятельного решения, что дает возможность читателю попробовать свои силы в решении подобных задач. Книга предназначена главным образом для старшеклассников, однако школьники младших классов также несомненно найдут в ней много полезного. Учебное издание Редактор серии канд. физ. -мат. наук, доцент Андреев А. А. Рецензент докт. физ. -мат. наук. , профессор Кислое Н. В. , кафедра математического моделирования, Московский Государственный Технический Университет (МЭИ) © Андреев А. А. , Горелов Г. Н. , Люлев А. И. , Савин А. Н. , 1997 §1. Принцип Дирихле Самая популярная формулировка принципа Дирихле звучит так. Формулировка 1. «Если в п клетках сидит #1 + 1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца». Заметим, что в роли зайцев могут выступать различные предметы и математические объекты — числа, отрезки, места в таблице и т. д. Принцип Дирихле можно сформулировать на языке множеств и отображений. Формулировка 2. «При любом отображении множества Р, содержащего п + 1 элементов, в множество Q, содержащее п элементов, найдутся два элемента множества Р, имеющие один и тот же образ». Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать "зайцем", что — "клеткой", и как использовать наличие двух "зайцев", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения.