42418

Функции. Принцип Дирихле

Лабораторная работа

Математика и математический анализ

Докажите что либо одно из них делится на 5 либо сумма нескольких рядом стоящих чисел делится на 5. Докажите что какието три из них можно накрыть квадратиком со стороной 02 м. Докажите что найдутся как минимум 2 ученика отмечающих дни рождения в один месяц. Докажите что расстояние между некоторыми двумя из них меньше 05 см.

Русский

2013-10-29

46 KB

14 чел.

Практическое занятие №5

Тема: Функции. Принцип Дирихле.

Занятие рассчитано на 2 академических часа.

Цель работы: ознакомиться с принципом Дирихле.

Теоретический материал

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

В математике большое значение имеют так называемые доказательства существования. Самый простой способ доказать существование объекта с заданными свойствами – это указать его и, разумеется,  убедиться, что он действительно обладает нужными свойствами. Например, чтобы доказать, что уравнение имеет решение достаточно привести какое-то его решение. Доказательства существования такого рода называют прямыми или конструктивными.

Но бывают и косвенные доказательства существования, когда обоснование факта, что искомый объект существует, происходит без прямого указания на сам объект. Рассмотрим несколько примеров.

Задача 1. В самолёте летят 380 пассажиров. Докажем, что, по крайней мере, двое из них родились в один и тот же день года.

Решение. Всего в году 365 или 366 дней, а пассажиров в самолёте 380 – значит, их дни рождения не могут приходиться только на различные даты. Вообще, если пассажиров больше, чем 366, то хотя бы у двоих дни рождения совпадают. А вот если пассажиров 366, не исключено, что все они родились в разные дни года, но это маловероятно. (Согласно теории вероятностей, в случайно выбранной группе численностью свыше 22 человек совпадение дней рождения у некоторых из них более вероятно, нежели то, что у всех дни рождения приходятся на разные дни года).

Задача 2. В шахматной партии чёрные сдались после 15-го хода белых. Требуется доказать, что хотя бы одна из чёрных фигур ни разу не покидала своего поля (к фигурам отнесём и пешки).

Решение. Если шахматный ход не рокировка (обмен местами), то передвигается одна фигура, в случае рокировки – две. Чёрные успели сделать 14 ходов (так как первыми ходят белые), и по правилам игры лишь один из них мог быть рокировкой. Поэтому самое большое количество чёрных фигур, сделавших ходы, 15. Всего же чёрных фигур 16. Значит, по крайней мере, какая-то из них не сделала ни одного хода.

Логический приём, использованный в приведённых доказательствах, называется принципом Дирихле – по имени Петера Густава Дирихле, немецкого математика, автора описанного метода.

В самой простой и несерьёзной форме он выглядит так:

Нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев.

Действительно, если в каждой клетке не больше двух зайцев, то всего зайцев не больше чем 2*3=6, что противоречит условию.

Вот общая формулировка принципа Дирихле:

Если имеется n ящиков, в которых находится в общей сложности не менее n+1 предмета, то непременно есть ящик, в котором лежат, по крайней мере, 2 предмета.

В первом примере такими «ящиками» были дни года, а «предметами» - даты рождения пассажиров, летевших в самолёте. Во втором, мы «раскладывали» все чёрные фигуры («предметы») по максимальному количеству их ходов («ящикам»). То есть каждой фигуре ставили в соответствие один неповторимый ход, но фигур оказалось на одну больше, чем ходов, таким образом «ящиков» оказалось на один меньше, чем «предметов».

Метод Дирихле является мощным математическим методом решения задач, причём самых разнообразных. Дело в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «зайцев», а что в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток». Выбор «зайцев» и «клеток» часто неочевиден. Далеко не всегда по формулировке задачи можно определить, что следует применить принцип Дирихле. Главное же достоинство данного метода решения в том, что он даёт неконструктивное решение, попытка же дать конструктивное решение приводит к большим трудностям.

Рассмотрим решение ещё нескольких задач.

Задача 3. В строку выписано 5 натуральных чисел: a1,a2,a3,a4,a5. Докажите, что  либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится  на 5.

Решение. Рассмотрим 5 чисел:  а1,

                                                    а12,  

                                                    а123,

                                                    а1234,  

                                                    а12345.

Если одно из них делится на 5, то всё в порядке, утверждение справедливо. В противном случае при делении на 5 они дают в остатке какие-то из четырёх чисел: 1,2,3,4. По принципу Дирихле остатки, по крайней мере, двух из выписанных 5 чисел совпадают. Разность  их делится на 5. Но эта разность – одно из чисел, данных в задаче, или сумма нескольких из них, стоящих рядом.

Задача 4. В квадрат со стороной 1 м бросили произвольным способом 51 точку. Докажите, что какие-то три из них можно накрыть квадратиком со стороной 0,2 м.

Решение. Разобьем квадрат на 25 равных квадратиков со стороной 0,2 м. Докажем, что в каком-то из них находятся, по крайней мере, три точки. Применим принцип Дирихле: если бы в каждом квадратике (внутри или на сторонах) было не больше двух точек, то всего их бы было не больше  2*25=50.          

Контрольные вопросы

  1.  Дайте определение принципа Дирихле.
  2.  Почему он является мощным математическим методом решения задач.

Индивидуальные задания

1. В ящике лежат носки одного и того же размера. Белых носков вполне достаточно, чтобы составить 5 пар, черных - для 10 пар и коричневых - для 15 пар. Какое самое маленькое количество носков нужно вытащить из ящика (не заглядывая туда), так, чтобы наверняка у вас в руках оказалась пара носков? (Между левым и правым носком нет никакой разницы.)

2. В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц.

  1.  Внутри равностороннего треугольника со стороной 1 см расположено 5

точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5 см.

  1.  Дано 12 целых чисел. Докажите, что из них можно выбрать два,

разность которых делится на 11.

  1.  В ковре размером 3х3 метра Коля проделал 8 дырок. Докажите, что из

него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок. (Дырки можно считать точечными.)

6. Дано 9 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 8.

7. В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы?

8. В лесу растет миллион елок. Известно, что на каждой из них не более     600 000 иголок. Докажите, что в лесу найдутся две елки с одинаковым количеством иголок.

9. На дискотеку в студенческое общежитие, в котором 42 комнаты, пришло 36 гостей. Докажите, что найдется комната, в которую не пришёл ни один гость.

10. В классе 26 учеников, из них более половины- мальчики. Докажите, что какие-то  2 мальчика сидят за одним столом, если в классе 13 столов.

11. Внутри правильного шестиугольника со стороной 1 см расположено 7 точек. Докажите, что расстояние между некоторыми двумя точками меньше, чем 1 см.

12. В вершинах квадрата записаны числа 3,1,2,5. Разрешается прибавлять к любым двум числам, стоящим в квадрате, одно и то же целое число. Можно ли через несколько ходов получить во всех вершинах одинаковые числа?

13. В магазин привезли 25 ящиков яблок трех сортов. В каждом ящике лежат яблоки одного сорта. Продавец утверждает, что у него нет девяти ящиков с яблоками одного сорта. Не ошибся ли он?

14. В поход пошли 20 туристов. Самому старшему из них 35 лет, а самому младшему а) 16 лет б) 17 лет. Верно ли, что среди туристов есть одногодки?

15. В школе учатся 400 учеников. Докажите, что хотя бы двое из них отмечают день рождения в один и тот же день.

16. Сможете ли вы разложить 44 шарика на 9 кучек так, чтобы количество шариков в разных кучках было различным?

17. Занятия математического кружка проходят в девяти аудиториях. Среди прочих, на эти занятия приходят 19 учеников из одной и той же школы.

а) Докажите, что как их не пересаживай, хотя бы в одной аудитории окажется не меньше трех таких школьников.

б) Верно ли, что в какой-нибудь аудитории обязательно окажется ровно три таких школьника?

18. Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.

Литература

  1.  http://ru.wikipedia.org/wiki/Принцип_Дирихле

    2 .  http://www.smekalka.pp.ru/math_dir.html


 

А также другие работы, которые могут Вас заинтересовать

68460. ФОРМАТИРОВАНИЕ ДАННЫХ В ЯЧЕЙКАХ 1.36 MB
  Ячейка – это минимальный адресуемый элемент рабочего листа. Ячейка определяется адресом. Кроме этого можно задавать диапазон ячеек. Диапазоном называется группа ячеек. Чтобы задать адрес диапазона нужно указать адреса верхней левой и нижней правой ячейки, разделив их двоеточием.
68461. РАБОТА С ФОРМУЛАМИ И ФУНКЦИЯМИ 72 KB
  Формулы в таблице и технология их использования Формула в электронной таблице это выражение по которому вычисляется значение в ячейке. Формула всегда начинается с символа равно =. Формула состоит из операндов и символов операций В качестве операндов используются: Числа.
68462. Разработка рекомендаций по обеспечению защиты информации в отделе записей актов гражданского состояния (ЗАГС) по Центральному району 435 KB
  Информационная безопасность организации - целенаправленная деятельность её органов и должностных лиц с использованием разрешённых сил и средств по достижению состояния защищённости информационной среды организации, обеспечивающее её нормальное функционирование и динамичное развитие.
68463. Работа с текстом в Excel 64.5 KB
  Excel предоставляет очень много функций для работы с текстом позволяющие преобразовывать исходные текстовые данные и производить разнообразные действия. Все функции для обработки текста можно просмотреть в диалоговом окне Мастер функций кнопочка fx в категории Текстовые.
68464. Основные положения стереохимии. Реакционная способность гетерофункциональных соединений 97 KB
  Стереохимия изучает пространственное строение органических соединений. Органические молекулы с одинаковой молярной массой, он отличающиеся природой или последовательностью связей между атомами и пространственным расположением атомов называются изомерами.
68465. Аминокислоты, пептиды и белки 820 KB
  Для записи аминокислотных остатков в макромолекулах пептидов и белков используют трехбуквенные сокращения их тривиальных названий (см. табл. 1). –аминокислоты – кристаллические вещества, растворимые в воде. Часть из них обладает сладким вкусом.
68466. НРАВСТВЕННОЕ СОЗНАНИЕ И МОРАЛЬНЫЙ ФАКТОР В ДЕЯТЕЛЬНОСТИ ЮРИСТОВ 103.5 KB
  Оно сформировалось в силу объективной необходимости регуляции отношений между людьми в их совместной деятельности. Честь конкретной личности связывается с ее общественным положением родом деятельности и признаваемыми за ней моральными заслугами.
68467. Юридическая этика – вид профессиональной этики 64.5 KB
  Термин профессиональная этика обычно употребляется для обозначения не столько отрасли этической теории сколько своеобразного нравственного кодекса людей определенной профессии. Профессиональная этика обусловлена особенностями некоторых профессий корпоративными интересами профессиональной культурой.
68468. Нравственные основы законодательства о правосудии и правоохранительной деятельности 158.5 KB
  Нравственное содержание конституционных норм о правосудии и правоохранительной деятельности Правосудие как вид государственной деятельности призванной обеспечить справедливость в отношении тех чьи права и интересы оно затрагивает базируется на правовых и нравственных началах.