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

Принцип дирихле ии 9 клеток вмещают 7 голубей, значит, хотя бы 9­7=2 клеткисвободны  Дирихлеи — утверждение, сформулированное немецким математиком Дири Пр нцип хле. Принципустанавливает связь между объектами («кроликами») и контейнерами (« клетками») при выполненииопределённых условий. Формулировки Предположим, m кроликов рассажены в n клетках. Наиболее распространена следую щая формулировка этогопринципа: Предположим, некоторое число кроликов рассажены в клетках. Если число кроликов  больше, чем числоклеток, то хотя бы в одной из клеток будет больше одного кролика. Наиболее общая формулировка звучит так: Предположим, m кроликов рассажены в n клетках. Тогда если m > n, то хотя бы в одн ой клеткесодержится не менее m:n кроликов, а также хотя бы в одной другой клетке  содержится не более m:nкроликов. Возможны также несколько формулировок для частных случаев: Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста. Пусть задана функция  есть | A | > n | B | , где  . Тогда некоторое своё значение функция f примет по крайней мере n + 1 раз.     множества A больше мощности B, то   и мощность   Современная формулировка и доказательство На сегодняшний день существует  несколько разных формулировок данного принципа. Самая понятная и простая  подразумевает, что нельзя посадить 8 кроликов в 3 клетки так, чтобы в каждой было не больше 2. Более научная и сложная формулировка, объясняющая принцип  Дирихле, гласит: если в k ячеек находится k+1 зайцев, то, по крайней мере, в 1  ячейке будет располагаться больше одного зайца. А если в k ячеек находится k­1  зайцев, то по крайней мере в 1 ячейке будет располагаться меньше одного зайца.  Доказательство этого утверждения совсем простое, так сказать, от противного.  Если предположить, что в каждой ячейке располагается зайцев меньше, чем k­1/k, тогда в k ячеек зайцев меньше чем k*k­1/k = k­1, а это противоречит первоначальным  условиям.  Принцип Дирихле утверждает, что если множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов , где N > n ,то по крайней мере в одной части будет более одного элемента. Самая популярная формулировка принципа Дирихле такова: "Если в n клетках сидит N зайцев , причем N > n , то хотя бы в одной клетке сидят по крайней мере два зайца. Принцип Дирихле представляет собой настолько очевидное утверждение, что на первый взгляд даже непонятно, почему он является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь "зайцы" и "клетки" и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден ; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. Авторские задачи, решаемые с помощью принципа Дирихле. Задача №1 К Новому Году в детском саду ребята делали фонарики. В группе 30 детей. Петя Пяточкин сделал 12 фонариков, а остальные – меньше. Докажите, что хотя бы три ребенка сделали одинаковое количество фонариков (может быть, по 0 шт. ). РЕШЕНИЕ: Здесь “зайцы”- дети ,а “клетки” - число сделанных фонариков. В клетку 0 “посадим” всех, кто не сделал ни одного фонарика ,в клетку 1- тех, у кого од ин фонарик ,в клетку 2- два фонарика,и так до клетки 12 ,куда П опал Петя Пяточкин. Применим принцип Дирихле. Докажем утверждение за д ачи от противного. Предположим , никакие три ребенка не сделали по одинаковому числу фонариков ,то есть в каждую из клеток 0,1,. ,11 попало мен ьше трех детей. Тогда в каждой из них два челов ека или меньше, а всего в этих 12 клетках не больше 24 человек. Добавив Петю Пяточкина, все равно не наберем 30 ребят. Получили противоречие. Может быть и такое, что кроме Пети вообще никто не сделал ни одного фонарика ,то есть сделал по 0 штук. Задача № 2 В научно-исследовательском институте 33 отдела. Всего работает 1150 человек. Найдется ли отдел, в котором меньше 35 сотрудников? РЕШЕНИЕ: Допустим,что в каждом отделе работает по 35 сотрудников. Тогда общее число сотрудников будет : 35 х 33 = 1155 человек , что противоречит условию. Следовательно , если в 32 отделах р аботает по 35 человек, то 35 х 32 = 1120 человек , и в 33-м отделе будет только 30 человек. Поэтому, хотя бы в одном отделе работает менее 35 человек. Задача № 3 На свой юбилей отец пригласил 25 сослуживцев. Известно,что среди любых трех из них есть двое знакомых друг с другом. Докажите,что есть такой гость,у которого не менее 2 знакомых. РЕШЕНИЕ: Выберем любых двух гостей, которые не знакомы между собой. ( Если таких нет,то все гости знакомы между собой ,значит,у каждого имеется 24 знакомых, и задача решена). Из оставшихся 23 гостей каждый знаком с одним из этих двух,иначе мы имели бы тройку гостей,среди которых не было бы знакомых. Тогда у одного из выбранны х двух гостей не менее12 з на к ом ых (23 "зайца" рассажены в двух "клетках"). Задача № 4 За пять лет дачники вырастили и собрали 31 кг. черной смородины. Причем каждый год они собирали урожай больший,чем в предыдущем году. На пятом году они собрали ягод втрое больше,чем в первый год. Какой был урожай смородины на четвертый год? РЕШЕНИЕ: Пусть каждый год дачники собирали С1,С2,С3,С4,С5 кг. смородины. Причем: С1 < C 2< C 3< C 4< C 5 , и С5=3С1 Если С1=3 , то С5=9 ,значит С2+С3+С4=19 Учитывая условия задачи, это равенство может быть выполнено в двух случаях: 1) С2=4; С3=7; С4=8 2) С2=5; С3=6; С4=8 Таким образом ,на четвертый год дачники собрали 8 кг. смородины. Задача № 5 При раскопках древнего храма археологи нашли клад. Смогут ли они увезти 50 сундуков з олота, веса которых равны 370 кг, 372 кг,. , 466 кг, 468 кг. на семи трехтонных грузовиках? РЕШЕНИЕ: Если каждая машина увезет по 7 сундуков, то они увезут только 49 сундуков, следова - тельно, одна машина должна будет взять 8 сундуков. 8 сундуков даже самого мало - го веса весят: 370+372+374+376+378+380+382+384=3016 кг. Это больше трех тонн. Таким образом, семь трехтонок не смогут увезти 50 сундуков золота. Задача № 6 Докажите, что из любых 12 натуральных чисел можно выбрать два, разность которых делится на 11. РЕШЕНИЕ: При делении на 11 получается один из 11остатков:0,1,2,,10. У нас же дано 12 чисел, и по принципу Дирихле остатки от деления на 11 у каких-то двух из них совпадают. Разность этих двух делится на 11. Задача № 7 На прослушивание пришло 65 пианистов. Им предложили для исполнения 3 инвенции И. С. Баха. За исполнение каждой инвенции ставилась одна из оценок : 2 ,3 ,4 ,5. Верно ли, что найдутся два исполнителя, получившие одинаковые оценки на всех экзаменах? РЕШЕНИЕ: Рассмотрим множество наборов из трех оценок за соответствующее исполнение. Количество таких наборов равно 4х4х4=64 (4 возможности за каждое из трех исполнений). Поскольку число участников больше 64,то по принципу Дирихле каким-то двум исполнителям соответствует один набор оценок. Применение принципа Дирихле к геометрическим задачам. Некоторые геометрические задачи решаются методами ,в какой-то мере аналогичными принципу Дирихле. Сформулируем соответствующие утверждения: 1) Если на отрезке длиной 1 расположено несколько отрезков, сумма длин которых больше 1, то по крайней мере два из них имеют общую точку. 2) Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2р, то по крайней мере две из них имеют общую точку. 3) Если внутри фигуры площадью 1 расположено несколько фигур, сумма площадей которых больше 1,то по крайней мере две из них имеют общую точку. Задача № 1 В квадрат со стороной 1 м. бросили 51 точку. Докажите,что какие-то три из них можно накрыть кругом радиуса 1 /7 м. РЕШЕНИЕ: Разобьем квадрат на 25 равных квадратов ( со стороной 1 /5 м). Докажем,что в каком-то из них находятся по кайней мере три из данных точек. Применим принцип Дирихле : если бы в каждом квадратике (внутри или на сторонах) было не больше двух точек, то всего их было бы не больше 50. Опишем окружность вокруг квадратика, в котором лежат три ( или более ) из данных точек. Нетрудно вычислить ее радиус, он меньше 1/7 м. Задача №2 На клетчатом листе бумаги размером 8х8 Марина нарисовала 15 звездочек. Докажите, что найдется квадрат размером 2х2 , в котором не будет ни одной звездочки. (Каждая звездочка размещается внутри клетки размером 1х1 ). РЕШЕНИЕ: Разобьем прямоугольник на квадра- ты 2 х2 (см. рисунок). Получилось 16 квадратиков - это "клетки". Даже если звездочки "зайцы расположить по 1 в каждом квадрате, то заняты будут только 15 "клеток",а одна будет пустая. Задача № 3 Доказать, что е сли прямая l ,расположенная в плоскости треугольника АВС, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника. РЕШЕНИЕ: Полуплоскости, на которые прямая разбивает плоскость треугольника АВС, обозначим через q 1 и q 2 ; эти полуплоскости будем считать открытыми (то есть не содержащими точек прямой l ). Вершины рассматривае мого треугольника ( точки А, В, С) будут "зайцами", а полуплоскости q 1 и q 2 - "клетками". Каждый заяц попадает в какую-нибудь клетку (ведь прямая l не проходит ни че рез одну из точек А,В,С ). Так как зайцев три ,а клеток только две,то найдутся два зайца, попавшие в одну клетку; иначе говоря ,найдутся такие две вершины треуголь ника АВС, которые принадлежат одной полуплоскости (см. рисунок). Пусть, скажем, точки А и В находятся в одной полуплоскости, то есть лежат по одну сторону от прямой l. Тогда отрезок АВ не пересекается с l. Итак, в треугольнике АВС нашлась сторона, которая не пересекается с прямой l. Задача № 4 Внутри равностороннего треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5. РЕШЕНИЕ: Средние линии правильного треугольника со стороной 1 разбивают его на четыре правильных треугольничка со стороной 0,5. Назовем их "клетками" ,а точки будем считать "зайцами". По принципу Дирихле из пяти точек хотя бы две окажутся в одном из четырех треугольнич - ков (см. рисунок). Расстояние меж- ду этими точками меньше 0,5 поскольку точки не лежат в вер- шинах треугольничков. (Здесь использована известная лемма о том ,что длина отрезка, рас- положенного внутри треуголь- ника, меньше длины его наибольшей стороны). Задача № 5 В прямоугольнике 5х6 закрашено 19 клеток. Докажите,что в нем можно выбрать квадрат 2х2 , в котором закрашено не менее трех клеток. РЕШЕНИЕ: Разделим прямоугольник на 6 частей по 5 клеток (см. рисунок). Согласно принципу Дирихле в одной из этих частей будет закрашено не менее 4 клеток. Тогда в квадрате 2х2,содержащемся в этой части, закрашено либо 3,либо 4 клетки. Это и будет искомый квадрат. Немного теории Этот принцип достаточно прост и очевиден, иногда им пользуются из соображений логики, даже не зная его формулировки. Но, зная этот принцип, легче догадаться в каких случаях его применять. Проще всего принцип Дирихле выражается в такой шуточной форме: «Если в n клетках больше чем n+1 зайцев, то хотя бы в одной клетке сидят не меньше двух зайцев». А теперь так: «Если множество, состоящее из nk+1 элементов, разбить на k подмножеств, то хотя бы в одном подмножестве найдётся не менее чем n+1 элементов». Доказательство принципа Дирихле можно провести, применив метод от противного. Приведем еще несколько похожих на принцип Дирихле (и столь же очевидных) утверждений, используемых в геометрических и аналитических задачах: а) если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S; б) если на отрезке длины 1 расположено несколько отрезков с суммой длин L, то найдется точка, покрытая не более чем [L] этими отрезками; в) если тело с объёмом V разбили на n частей (которые не имеют общих внутренних точек), то объём наибольшей части не меньше V/n, а объём наименьшей – не больше V/n; г) если среднее арифметическое нескольких чисел больше А, то хотя бы одно из этих чисел больше А. Задачи с решениями 1. Доказать, что среди 101 целого числа всегда можно выбрать два таких, что их разность делится на 100. Решение 2. В розыгрыше первенства по футболу участвуют 30 команд. Каждые две команды должны сыграть между собой один матч. Доказать, что в любой момент состязаний имеются две команды, сыгравшие к этому моменту одинаковое число матчей. Решение 3. Задача Рамсея. Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых. Решение 4. Имеется n целых чисел. Доказать, что среди них найдутся несколько (или, быть может, одно), сумма которых делится на n. Решение 5. Ежедневно на протяжении года ученик решал не менее одной задачи, причём еженедельно он решал не более 12 задач. Доказать, что найдётся несколько последовательных дней, за которые он решил ровно 20 задач. Решение 6. Каждая из девяти прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2:3. Докажите, что, по крайней мере, три из этих прямых проходят через одну точку. Решение 7. «Король-самоубийца». На шахматной доске размером 1000 на 1000 стоит чёрный король и 499 белых ладей. Докажите, что при произвольном первоначальном расположении фигур король может стать под удар белой ладьи, как бы не играли белые. Решение 8. Каждая точка плоскости окрашена в один из двух цветов. Доказать: а) на этой плоскости существует равнобедренный треугольник, все три вершины которого окрашены в один и тот же цвет; б) на этой плоскости существует равносторонний треугольник, все три вершины которого окрашены в один и тот же цвет; в) на этой плоскости найдётся треугольник с углами 30°, 60°, 90° и гипотенузой n, вершины которого окрашены в один и тот же цвет. Решение 9. Пусть у выпуклого 24-угольника все стороны и диагонали окрашены либо в красный, либо в синий цвет. Можно ли выбрать 4 вершины так, чтобы все стороны и диагонали образованного четырехугольника имели одинаковый цвет? Решение 10. Ограниченная плоская фигура имеет площадь S > 1. Докажите, что её можно “перенести” на вектор с целыми коэффициентами так, чтобы начальная фигура и образ пересекались. Решение Задачи без решений 11. Группа людей состоит из 40 человек. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 человека из этой группы? 12. Дано n+1 различных натуральных чисел, меньших 2n. Доказать, что из них можно выбрать три таких числа, что одно из них равно сумме двух других. 13. Можно ли найти такой натуральный показатель степени числа 3, чтобы значение этой степени оканчивалось на 0001? 14. Каждая сторона и диагональ выпуклого 17-угольника окрашена в один из трёх цветов. Докажите, что всегда можно выбрать три вершины так, что получившийся треугольник будет иметь стороны одного цвета. 15. В пространстве расположено n точек так, что любые четыре из них являются вершинами тетраэдра с объёмом не большим k. Докажите, что все эти точки можно заключить в некоторый тетраэдр, объём которого равен 5k Алгоритм Евклида [править | править код] Материал из Википедии — свободной энциклопедии ии ии  — эффективный алгоритм для нахождения наибольшего общего  Алгор тм Евкл да делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в  честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII[1] и  X[2] книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше  время[3]. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел  и формирует новую пару, которая состоит из меньшего числа и разницымежду большим и  меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и  есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только  для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX  веке он был обобщён на другие типы математических объектов, включая целые числа  Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей  алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида был обобщён на  другие математические структуры, такие как узлы и многомерные полиномы. Для данного алгоритма существует множество теоретических и практических применений. В  частности, он является основой для криптографического алгоритма с открытым  ключом RSA   [4], широко распространённого в электронной коммерции. Также алгоритм [6], в методе Штурма  [7]. Алгоритм Евклида является основным   [5], при   [8] и основная теорема арифметики используется при решении линейных диофантовых уравнений построении непрерывных дробей инструментом для доказательства теорем в современной теории чисел, например таких  как теорема Лагранжа о сумме четырёх квадратов Геометрический алгоритм Евклида[править | править код] Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший и заменим  больший отрезок полученной разностью. Повторяем эту операцию, пока отрезки не станут  равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный  отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В  таком виде алгоритм описан Евклидом[2] и реализуется с помощью циркуля и линейки. Пример[править | править код] Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071  и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность  меньше, чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147:  [9]. 1071 = 2 × 462 + 147. Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147.  Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21: 462 = 3 × 147 + 21. Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем  21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка: 147 = 7 × 21 + 0. Таким образом последовательность a > b > r1 > r2 > r3 > … > rn в данном конкретном случае будет выглядеть так: 1071 > 462 > 147 > 21. Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и  НОД(1071, 462) = 21. В табличной форме шаги были следующие: Шаг  k 0 1 2 Равенство Частное и остаток 1071 = q0 462 + r0 q0 = 2 и r0 = 147 462 = q1 147 + r1 q1 = 3 и r1 = 21 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм заканчивается Алгоритм Евклида ­ нахождение  наибольшего общего делителя Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя  (НОД) пары целых чисел. Наибольший общий делитель (НОД) – это число, которое делит без остатка  два числа и делится само без остатка на любой другой делитель данных двух  чисел. Проще говоря, это самое большое число, на которое можно без остатка  разделить два числа, для которых ищется НОД. Алгоритм нахождения НОД делением 1. Большее число делим на меньшее. 2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из  цикла). 3. Если есть остаток, то большее число заменяем на остаток от деления. 4. Переходим к пункту 1. Пример: Найти НОД для 30 и 18. 30/18 = 1 (остаток 12) 18/12 = 1 (остаток 6) 12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6 Алгоритм нахождения НОД вычитанием 1. Из большего числа вычитаем меньшее. 2. Если получается 0, то значит, что числа равны друг другу и являются НОД  (следует выйти из цикла). 3. Если результат вычитания не равен 0, то большее число заменяем на результат  вычитания. 4. Переходим к пункту 1. Пример: Найти НОД для 30 и 18. 30 ­ 18 = 12 18 ­ 12 = 6 12 ­ 6 = 6 6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6