Научно-практическая работа на тему: Признак Дирихле. - презентация

1 Научно-практическая работа на тему: Признак Дирихле

2 В комбинаторике принцип Дирихле(принцип ящиков) утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков, когда объектами являются голуби, а контейнерами ящики. Принцип Дирихле применяется, в частности, в теории диофантовых приближений при анализе систем линейных неравенств.

3 1) Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика. 2) Если m кроликов рассажены в n клеток, то хотя бы в одной клетке находится не менее кроликов, а также хотя бы в одной клетке находится не более кроликов. 3) Если число клеток больше, чем число кроликов, то как минимум одна клетка пуста. 4) Пусть задана функция на конечных множествах A и B, причём | A | > n | B |, где. Тогда некоторое своё значение функция f примет по крайней мере n+1 раз.

4

5

6 Условие: Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.

7 Рассмотрим три грани куба, имеющие общую вершину. Назовем их "кроликами", а данные цвета "клетками". По принципу Дирихле, найдутся две грани, окрашенные в один цвет. Они и будут соседними.

8 Условие: Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?

9 Пусть "клетками" у нас будут сорта конфет, а "кроликами" -сами конфеты. По принципу Дирихле найдется "клетка", в которой не менее 25 / 3 "кроликов". Так как 8 < 25 / 3 < 9, то найдется 9 конфет одного сорта.

10 Условие: Доказать, что среди шести целых чисел найдутся два числа, разность которых делится на 5.

11 Рассмотрим 5 коробок, пронумерованных 0,1,2,3,4, - цифрами, представляющими собой остатки от деления на 5. Распределим в эти коробки шесть произвольных целых чисел в соответствии с остатком от деления на 5, то есть, в одну и ту же коробку помещаем числа, имеющие одинаковый остаток от деления на 5. Поскольку чисел ("предметов") больше, чем коробок, согласно принципу Дирихле, существует одна коробка, содержащая более одного предмета. То есть, существуют (по крайней мере) два числа, помещенные в одну и ту же коробку. Следовательно, существуют два числа с одинаковым остатком от деления на 5. Тогда, разность этих чисел делится на 5.

12 Условие: В доме живут 40 учеников. Существует ли такой месяц в году, когда хотя бы 4 ученика празднуют свой день рождения.

13 Пусть "коробками" будут месяцы, а "предметами" - ученики. Распределяем, "предметы" по "коробкам" в зависимости от месяца рождения. Так как число месяцев, то есть, коробок, равно 12, а число учеников, то есть, предметов 40 = 12·3+4, согласно принципу Дирихле существует коробка (месяц) с по крайней мере 3+1=4 предметами (учениками).

14 Условие: 500 коробках лежат яблоки. Известно, что в каждой коробке находятся не более 240 яблок. Доказать, что существуют хотя бы 3 коробки, которые содержат одинаковое количество яблок.

15 Пусть в первых 240 коробках находится различное количество яблок (1,2,...,240), в следующих 240 коробках - аналогично (то есть, анализируется экстремальный случай; более подробно об этом методе рассказывается в теме "принцип крайнего"). Таким образом, остались ·240 = 20 коробок, в которые необходимо поместить яблоки от 1 до 240.

16 Условие: В коробке лежат 10 красных карандашей, 8 синих, 8 зеленых и 4 желтых. Наугад (произвольно) из коробки вынимают n карандашей. Определить наименьшее число карандашей, которые необходимо вынуть, чтобы среди них было: a)не менее 4 карандашей одного цвета; b)по одному карандашу каждого цвета; c)хотя бы 6 карандашей синего цвета.

17 . Решение. a) Пусть вынули 13 карандашей. Так как у нас всего 4 цвета, согласно принципу Дирихле (карандаши будут «кроликами", а цвета - "коробками"), по крайней мере 4 карандаша будут одинакового цвета. Докажем, что n = 13 является наименьшим числом. С этой целью покажем ситуацию, при которой условия задачи не выполняются. Например, когда вынуто по 3 карандаша каждого цвета (12 карандашей). Отметим, что эта ситуация возможна, так как в коробке находится не менее 3 карандашей каждого цвета. Значит наименьшее чило «13»,так как уже 12 «невозможно»

18 Условие: В международном симпозиуме участвуют 17 человек. Каждый знает не более трех языков и любые два участника могут общаться между собой. Доказать, что хотя бы три участника, знают один и тот же язык.

19 По принципу Дирихле мы можем сказать, что коробки- «языки»,а кролики-«люди».А по условию известно, что два участника могут общаться между собой, значит в «коробках» находятся по 2 кролика. Всего «кроликов»(участников)- 17,значит целых коробок (по 2 кролика) 7,а в одной коробке находится 3 «кролика»,т.к.(17/2=8,5,сказать что 8 коробок по 2 кролика и один кролик в 9 коробке, нельзя, т.к. 1 кролик не может сидеть в одной коробке, поэтому он находится в 8 коробке третьем.)

20 Условие: Внутри равностороннего треугольника со стороной 1 лежат 5 точек. Доказать, что найдутся две точки из пяти, расстояние между которыми меньше 0,5.

21 Делим равносторонний треугольник со стороной 1 на четыре равносторонних треугольника со стороной 0,5.В одном из этих четырех треугольников лежат по крайней мере две из данных точек. Расстояние между этими двумя точками меньше 0,5.

22 Условие: Пятеро программистов получили на всех зарплату долларов. Каждый из них хочет купить себе новый компьютер за 360 долларов. Докажите, что кому-то из них это не светит.

23 Воспользуемся утверждением Дирихле,n- программисты,S-зарплата: n=5, S=1750. Тогда понятно, что зарплата одного из программистов не более S/n=350 долларов. Ему и не светит покупка. А четыре других программиста купят себе компьютер!

24 Условие: На олимпиаде 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну, ровно две и ровно три задачи. Доказать, что кто-то из них решил не менее 5 задач. Решение: Возьмем одного школьника, решившего ровно одну задачу, одного, решившего ровно две и одного, решившего ровно три. Эти трое решили в сумме 6 задач. Остается еще 7 школьников, решивших в сумме 29 задач. Если взять задачи в качестве кроликов и школьников в качестве клеток, то получается в точности утверждение п.3 при n=7, k=5 ч.т.д.

25 Возьмем одного школьника, решившего ровно одну задачу, одного, решившего ровно две и одного, решившего ровно три. Эти трое решили в сумме 6 задач. Остается еще 7 школьников, решивших в сумме 29 задач. По принципу Дирихле клетки- школьники, а кролики- задачи. Значит 29/7, в одной клетке 5 кроликов, а в 6 клетках-4 кролика. Значит один школьник решил 5 задач!

26 Принцип Дирихле очень интересный и важный, а так же ещё и полезный. С помощью него можно решать задачи разных трудностей! Этот принцип все равно где-то понадобиться! Так же он нужен при решение задач, где используется логическое размышление!

27 ru.wikipedia.org www/bars.na.by/teachers/dirichle.html

28