ПРОЕКТ ПО МАТЕМАТИКЕ НА ТЕМУ "ПРИНЦИП ДИРИХЛЕ"

Министерство образования Российской Федерации Муниципальное бюджетное образовательное учреждение города Новосибирска школа № 206 Проект по математике Принцип Дирихле Выполнила ученица 7 Г класса Плаксина Ангелина Руководитель Куслина Е.В. Новосибирск 2017 2 Оглавление Оглавление I.Введение............................................................................................................................. 4 ............................................................................................................................................... 4 II.Основная часть 2.1. Принцип Дирихле............................................................................7 ............................................................................................................................................... 7 Алгебраические задачи.....................................................................................................8 Арифметические задачи......................................................................................................9 Комбинаторные задачи......................................................................................................11 Геометрические задачи.....................................................................................................14 2.2 Принцип недостаточности...........................................................................................15 2.3 Раскраска...................................................................................................................16 III Заключение.....................................................................................................................18 3 I. Введение Математика - древняя наука. Она существовала и была актуальна ещё до нашей эры, остаётся таковой и сейчас. За время развития математики было создано много теорий, правил, формул с целью решения задач различными способами. Одним из ведущих математиков, работавших над исследованием разных способов решения задач, является немецкий математик Иоганн Петер Густав Лежён Дирихле (13 февраля 1805, Дюрен, Французская империя, ныне Германия — 5 мая 1859, Гёттинген, королевство Ганновер, ныне Германия) . Он внёс существенный вклад в математический анализ, теорию функций и теорию чисел. Являлся членом Берлинской и многих других академий наук, в том числе Петербургской. Дирихле принадлежат крупные открытия в самых разных областях математики, а также в механике и математической физике. Он вывел множество формул и принципов решения задач. Одни из них так и называется - Принцип Дирихле . Цель работы: исследование эффективности применения принципа Дирихле в решении задач, получение знаний о применении и сферах использования принципа Дирихле Объект исследования: принцип Дирихлее Предмет исследования: логические задачи. Разнообразие логических задач велико, но в своей работе я рассмотрела задачи, решаемые с помощью принципа Дирихле. Задачи работы: 1. Изучить научную литературу по данной теме. 4 2. Познакомиться с различными вариациями принципа Дирихле. 3. Рассмотреть способы решения задач на данный принцип. 4. Научиться решать задачи на принцип Дирихле. 5. Определить значимость принципов Дирихле для решения математических задач. Гипотеза: принцип Дирихле позволяет решать логические задачи олимпиадного характера, которые сложно решать другими способами. В своем исследовании я выделила несколько видов логических задач: а) арифметические; б) алгебраические; в) геометрические; г) комбинаторные. Актуальность: я заметила, что для решения многих олимпиадных задач часто используется принцип Дирихле, поэтому я решила изучить его подробнее, т.к. в дальнейшем эти знания будут востребованы при сдаче ЕГЭ (в третьей части ЕГЭ введены олимпиадные задачи). И каждый ученик, мечтающий поступить в вуз, должен уметь решать такие задания. Именно поэтому я заинтересовалась теорией этого ученого, стала находить и решать задачи с применением этого способа доказательства. Принцип Дирихле не рассматривается в учебниках алгебры, поэтому я решила представить его в виде научно-практической работы. 5 6 II. Основная часть 2.1. Принцип Дирихле Знаете ли вы, что среди зрителей, сидящих в Большом театре во время спектакля, обязательно есть люди, родившиеся в один и тот же день одного и того же месяца? Подсчитаем: в зале большого театра 2000 мест. И даже если не все они заполнены (что в этом знаменитом театре бывает нечасто), можно смело утверждать, что на спектакле собралось более 366 человек. Но 366 - это максимально возможное число дней в году, считая 29 февраля. Итак, для 367-го зрителя просто не остаётся свободной от дней рождений его соседей по залу даты в году. Просто? Тем не менее это рассуждение даже имеет своё название в математике: принцип Дирихле. Принцип Дирихле утверждает, что если множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов, где N > n, то по крайней мере в одной части будет более одного элемента. Самая популярная формулировка принципа Дирихле: "Если в n клетках сидит N зайцев, причем N > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца». Обобщенный принцип Дирихле: "Если в n клеток посадить kn+1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц". Докажем обобщенный принцип Дирихле. Доказательство от противного. Предположим, что не найдется такой клетки. Значит, в каждой клетке находится не более чем k зайцев. Тогда в n клетках не более чем kn зайцев. Но по условию у нас было kn+1 зайцев. Получилось противоречие, значит наше предположение неверно. Следовательно, найдется хотя 7 бы одна клетка, в которой находятся не менее чем k+1 заяц. Безусловно, начинать эту тему стоит с задач, в которых нужно работать с конкретными числами. Обязательно в процессе решения нужно обращать внимание, что мы должны говорить «не более», «не менее», а не обсуждать «лучший» («худший») случай, так как доказать это часто достаточно сложно. Алгебраические задачи Задача 1. Докажите, что среди 25 различных натуральных чисел найдутся хотя бы 2числа a и b, таких, что число a2- b2 делятся на 24. Решение. Среди данных чисел в соответствии с принципом Дирихле найдутся хотя бы 2 числа, дающие одинаковые остатки при делении на 24, тогда a-b=(24q1+r)- (24q2+r)=24(q1-q2), т. е.(a-b) делится на 24, т. к. a2-b2=(a- b)(a+b), и (a-b) делится на 24(доказано выше), то a2- b2 делится на 24. Задача 2. Первый член и разность арифметической прогрессии — натуральные числа. Доказать, что найдётся такой член прогрессии, в записи которого участвует цифра 9. Решение. Предположим, что первый член и разность арифметической прогрессии по абсолютной величине меньше 10k. Тогда найдётся член прогрессии, у которого (k + 1)-я цифра — любая заданная цифра. В частности, эта цифра может быть девяткой. Задача 3. Доказать, что среди шести целых чисел найдутся два числа, разность которых делится на пять. 8 Решение: Известно, что разность чисел (a-b) делится на m только тогда, когда a и b при делении на m дают одинаковые остатки. Можем переформулировать задачу. Доказать, что среди шести любых чисел найдутся два числа, которые при делении на пять, дают одинаковые остатки. При делении числа на пять может быть один из пяти остатков: 0,1,2,3,4. Пусть остатки – “кролики”, а числа – 5<6, значит в одной “клетки”. клетке сидит не менее двух кроликов, т.е. Хотя бы два числа имеют одинаковые остатки, а значит, их разность делится на 5. Арифметические задачи Задача 1. На земле живет 6000000000 человек, у каждого на голове – не более 3000000 (цифры условные) волос. Докажите, что обязательно найдутся два человека с одинаковым числом волос. Решение. Т. к. количество людей больше количества возможных вариантов количества волос, то в соответствии с принципом Дирихле, хотя бы двое из них имеют одинаковое число волос. Задача 2. Пятеро молодых рабочих получили на всех зарплату - 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты. Решение: Зарплата равная 1500 руб – количество «клеток» Магнитофоны стоимостью 320 руб – «кролики» Если бы каждый рабочий купил бы по магнитофону, то затратил бы (320 ×5 ) руб, что равняется 1600 руб. 1500<1600, значит, один 9 рабочий не сможет купить магнитофон, и ему придется ждать до следующей зарплаты. Задача 3. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок. Решение: Наибольшее количество сделанных ошибок равно 13. Значит, ученики могли сделать 0,1,2,3…13 ошибок (14 возможных вариантов). Ошибки – «клетки» Ученики – «кролики» 14 учеников сделали разное количество ошибок, остальные 14 тоже сделали разное количество. Осталось еще два ученика. Они тоже сделали разные ошибки. Значит, есть три ученика, которые сделали одинаковое количество ошибок. Задача 4. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно две задачи и школьники, решившие ровно три задачи. Докажите, что есть школьник, решивший не менее пяти задач. Решение: Пусть первый ученик решил 1 задачу, второй ученик решил 2 задачи, а третий ученик решил 3 задачи. 35-1-2-3=29 10-3=7 Значит, на 7 учеников приходится 29 задач. ученики - задачи каждую клетку поместится 4 кролика(4*7=28). Остается еще один кролик. Значит, в одной клетке будет сидеть «Клетки» - «Кролики» В 10 ровно пять кроликов, т.е. один ученик решит ровно пять задач. Задача 5. В бригаде 7 человек и их суммарный возраст – 332. Доказать, что из них можно выбрать 3 человека, сумма возрастов которых не меньше 142 лет. Решение: Выберем трех старших членов бригады. Если им вместе 142 года, то хотя бы одному из них больше 47 лет. Если самому младшему из троих больше 47 лет, то им троим больше 142 лет. Пусть самому младшему из троих 47 лет или меньше, им троим вместе менее 142 лет. Тогда на долю остальных четверых приходится более 320 – 142 = 190 лет. остатком: 190 =4*47 + 2. Тогда по принципу Дирихле одному из четверых больше 47 лет. Это противоречит выбору троих самых старших в бригаде. Разделим 190 на 4 с Комбинаторные задачи Задача 1. Натуральные числа записаны в произвольном порядке. Для каждого числа найдена сумма с его порядковым номером. Могут ли все суммы оканчиваться разными цифрами? Решение: Нет. Докажем, что хотя бы две суммы оканчиваются одинаковой цифрой.Способ 1. В начальной расстановке (все числа записаны по порядку) все суммы – четные. При перестановке двух чисел либо четность сумм не изменится, либо появится две нечетные суммы. Следовательно, в любой расстановке числа Nч четных сумм и Nн нечетных сумм – четны (причем Nч+Nн=10), 11 поэтому одно из чисел Nч, Nн больше 5. А четных и нечетных цифр – по 5. Способ 2. Сумма всех сумм четна, так как каждое число в нее входит дважды. Пусть все суммы оканчиваются разными цифрами, тогда сумма последних цифр 0+1+…+9=45 – нечетна. Противоречие. Задача 2. Докажите, что в любой момент турнира по шашкам (в котором каждый встречается с остальными участниками по одному разу) найдется два игрока, сыгравшие одинаковое число партий. Решение: Если в турнире k+1 участник, то количество сыгранных партий у каждого спортсмена меняется от 0 до k. Однако, если хотя бы у одного участника не сыграно ни одной партии. То ни у кого не может быть сыграно k партий (т. е. количество групп-k). Если же хотя бы один сыграл все k партий, то ни у кого не может быть 0. Если k+1 игрока распределять по k группам, то найдется группа, в которой не менее 2 игроков. Задача 3. Двое показывают карточный фокус. Первый снимает пять карт из колоды, содержащей 52 карты (предварительно перетасованной кем-то из зрителей), смотрит в них и после этого выкладывает их в ряд слева направо, причём одну из карт кладет рубашкой вверх, а остальные - картинкой вверх. Второй участник фокуса отгадывает закрытую карту. Докажите, что они могут так договориться, что второй всегда будет угадывать карту. б) Второй фокус отличается от первого тем, что первый участник выкладывает слева направо четыре карты картинкой вверх, а одну не выкладывает. Могут ли в этом случае участники фокуса так договориться, чтобы второй всегда угадывал невыложенную карту? Решение: а) Между всеми картами колоды можно каким-то образом 12 (каким именно — неважно) установить старшинство. Из пяти карт (по принципу Дирихле) хотя бы две имеют одинаковую масть. Первый фокусник выбирает две такие карты, одну из них располагает рубашкой вверх, а другую ставит первой среди открытых в пятёрке, так что второй фокусник узнаёт масть закрытой карты. Всего карт одной масти 13, одна из них открыта, так что остаётся выбрать из 12 возможностей. Следующие три карты, которые открыты, можно упорядочить шестью способами (в порядке роста старшинства, в порядке убывания и т. д.). Закрытая карта может располагаться между остальными пятью способами. Всего вариантов оказывается 6 x 5 = 30 — этого достаточно, чтобы закодировать 12 карт. б) Как и в задаче а), первый фокусник выбирает масть, которая представлена хотя бы двумя картами, выбирает эти две карты. Дальше он действует иначе. 13 карт выбранной масти можно расположить по кругу в установленном порядке (например, в порядке роста старшинства). Фиксируем направление обхода. От каждой карты проведём стрелки к шести картам, которые в этом круге идут следом за ней в этом направлении. Тогда любые две карты окажутся соединёнными, и притом только одной стрелкой. Теперь фокусник из двух выбранных карт берёт ту, в которую идёт стрелка, и её оставляет у себя, а другую выкладывает. Таким образом, второму фокуснику приходится выбирать уже не из 12, а только из шести карт, что, как мы видели, возможно. 13 Геометрические задачи Задача 1. В квадрате со стороной 1 м находится 20 точек. Найдутся ли 3 из них, которые можно накрыть квадратом со стороной 1/3 м? Решение: Да, разобьем квадрат на 9 квадратов со стороной 1/3м. По принципу Дирихле, по крайней мере в одном из них находится не менее 3 точек. Задача 2. Каждая из девяти прямых разбивает квадрат на два четырехугольника, площади которых относятся как 2:3. Докажите, что, по крайней мере, три из этих прямых проходят через одну точку. Решение: Каждая прямая, разбивающая квадрат на два четырехугольника (либо на две трапеции, либо на два прямоугольника) с отношением площадей 2:3. Пусть дан квадрат ABCD. Его пересекает прямая MN. Пусть PQ – средняя линия квадрата. К – точка пересечения PQ и MN. Площади трапеций ABMN и MNDC равны соответственно AB× PK/2 и CD×KQ/2. Площади относятся как 2:3, поэтому PQ:KQ=2:3. Таких точек, которые делят средние линии квадрата в отношении 2:3, всего четыре, а прямых девять. Согласно принципу Дирихлее найдется точка, через которую проходят, по крайней мере, три прямых. Задача 3. Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками. Решение: Меньший равносторонний треугольник, как его не клади, не сможет покрыть 2 вершины большего. Поэтому, взяв вершины в качестве клеток и маленькие треугольники в качестве кроликов, мы получим, что кроликов меньше, чем клеток, откуда следует, что есть пустая клетка. Это 14 означает, что какую-то из вершин большого треугольника мы никогда не накроем, поэтому и не накроем его целиком. 2.2 Принцип недостаточности У принципа Дирихле есть аналогичные ему принципы. Таковым является принцип недостаточности. Судя по названию эта формула основывается на недостаточности какого-то количества предметов. Так и есть. Ниже приведена формула принципа недостаточности и её доказательство. Если разместить не более n(n−1) 2 − 1 кроликов в n клеток , то найдутся хотя бы две клетки, в которых сидят по одинаковому числу кроликов[4,с2]. Доказательство. Допустим, что в каждой из n клеток по разному числу кроликов. Это означает, что во всех этих клетках находится не менее 0+1+2+...+n - 1 кроликов. Подсчитаем эту сумму. Для этого будем складывать пары 0+n-1, 1+n-2, 2+n-3... . Замечаем, что сумма этих пар постоянна и равна n - 1. Количество пар равно n 2 , если n чётное; если же n- нечётное, то можем рассматривать только n−1 2 пар и прибавить к ним средний член, который равен n−1 2 . В сумме получается число, не зависящее от чётности n, и оно равно (n−1) 2 × , т.е. кроликов должно быть больше чем у нас есть. Значит сделанное предположение неверно, т.е. найдутся две клетки, где сидят по одинаковому числу кроликов. Задача. У 21 мальчика имеется 200 орехов. Доказать, что как бы они не разделили их, найдутся два мальчика, которым досталось поровну орехов (может оказаться, что орехов им не досталось совсем). Пусть дано k орехов. Какому минимальному числу мальчиков можно раздать эти орехи так, чтобы наверняка нашлось двое, которым их досталось поровну. 15 Решение: а) Принимая за "клетки" мальчиков, а за "кроликов" орехи и применяя принцип недостаточности (n=21 ), получаем, что в каких-то двух "клетках" находится по равному числу кроликов. Это и означает, что найдутся два мальчика, которые собрали по одинаковому числу орехов. б) Проанализируем её условие. Пусть n мальчиков имеет по разному числу орехов. Тогда, как было уже установлено при доказательстве принципа недостаточности, они должны были собрать не менее чем n(n−1) условию задачи имеется k орехов. Значит, k ≥ n(n−1) орехов, то между n мальчиками можно разделить орехи так, чтобы никаким двум из них не досталось орехов поровну. Если же k ˂ n(n−1) двое, которым орехов досталось поровну. Итак, остаётся поместить число k между двумя такими числами (они называются треугольными), чтобы выполнялись неравенства: , то обязательно найдутся 2 2 орехов. По 2 n(n−1) 2 ≤ k ˂ n(n+1) 2 Тогда для n мальчиков условие задачи не будет выполняться, а для n+1 уже будет, значит, n+1 - это и есть искомое количество мальчиков. 2.3 Раскраска Ещё один аналог принципа Дирихле - это раскраска. В этой главе будет браться какое-либо поле и его надо будет или раскрасить, или найти какую-либо не закрашенную фигуру, или же расставить какое-либо количество точек или фигур на данном поле. 16 Задача1. На шахматной доске 8×8 расставлена 31 фигура. Доказать, что найдётся свободный треугольник из трёх клеток. Решение: Чтобы не было свободного треугольника, в любом прямоугольнике 2×2 должны быть заняты две клетки, чтобы в него нельзя уже было поместить треугольник. Так как всю доску можно покрыть 16 неперекрывающимися квадратиками 2×2, то всего фигур должно быть 32, а по условию их всего 31. Значит, согласно предложению 1 найдётся квадратик 2×2, в котором окажется только одна фигура, а в ней и содержится свободный треугольник. Задача 2. В клетки прямоугольника 5×41 раскрашены в два цвета. Доказать, что можно выбрать три строки и три столбца так, чтобы все 9 клеток, стоящие на пересечение этих строк и столбцов, были одного цвета. Решение: Получим, что в любом из столбцов будет не менее трёх клеток одного (из двух) цветов. Можно воспользоваться принципом Дирихле, приняв за "клетки" цвета, а за "кроликов" - столбцы; "кролика" сажаем в ту "клетку", которая соответствует цвету большинства его раскрашенных клеток. Тогда получим, что в 21 столбце (из 41) будет по три раскрашенные одним цветом клетки (допустим - первым) . В каждом из этих столбцов три раскрашенные клетки можно расположить 10 способами. Снова в силу принципа Дирихле получаем, что в трёх столбцах (из 21) закрашенные клетки будут располагаться одинаково. Проведём прямые через эти столбцы и через три одинаково закрашенные клетки. Эти 9 клеток пересечения и будут искомыми. В раскраске могут быть как задачи в которых данную плоскость можно покрыть заданными участками без наложений, так и в которых 17 можно покрыть с наложениями. И данные задачи решаются с помощью принципа Дирихле и раскраски III Заключение Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. В ходе работы были изучены различные научные материалы на принцип Дирихле, решено много интересных задач. Я познакомилась с различными вариациями принципа Дирихле. Это такие принципы как раскраска и принцип недостаточности. В ходе исследовательской работы были рассмотрены разные способы решения задач на данные принципы. Материал данного реферата в дальнейшем поможет учащимся разных классов при решении задач на принцип Дирихле и 18 аналогичные ему принципы. Использованные в реферате задачи и их решения являются прекрасным практическим материалом для подготовки к олимпиадам и другим математическим конкурсам. Также эти данные можно использовать на уроках занимательной математики, что позволит развивать у ребят логическое мышление. Список литературы 1) Бородин А.И., Бугай А.С. Биографический словарь деятелей в области математики. - Киев, Радяньская школа, 1979 2) Бабинская И.Л. Задачи математических олимпиад - М., Наука, 1975 3) Большая российская энциклопедия - М., 4) Математика// Первое сентября, 1996, № 7 5) Я познаю мир: Дет. энцикл. Математика.- М.:ООО "Издательство АСТЛТД", 1999 Интернет - источники: 6) http://www.mccme.ru/courses/dirihle.html. 7) http://ru.wikipedia.org/wiki/ Дирихле_Петер_Густав_Лежён 8) http://ru.wikipedia.org/wiki/Принцип_Дирихле 19