Принцип Дирихле
По традиции принцип Дирихле почему-то всегда объясняют на примере кроликов в клетках: если общее число кроликов больше числа клеток, в одной из этих клеток наверняка сидит более одного кролика. Также этот принцип может выглядеть следующим образом: в n клетках невозможно рассадить по одиночке n+1 кроликов, т.е найдётся клетка, где сидят не менее двух кроликов . Таким образом, чтобы применить принцип Дирихле к решению задач, надо указать, что принимать за "клетки", а что за "кроликов", а также указать способ, которым надо усаживать "кроликов" в "клетки
Задача № 1
В классе 40 человек. Найдется ли такой месяц в году, в котором отмечают свой день рождения не меньше, чем 4 ученика этого класса?
Решение.
Предположим, что не найдутся. Тогда 12*3 = 36 человек, а у нас 40 человек. Следовательно, найдётся месяц, в котором родились не менее 4 одноклассников.
Задача 2. В пяти классах школы учатся 160 человек. Доказать, что найдутся 4 человека, у которых день рождения приходится на одну и туже неделю.
Решение. В году может быть максимально 53 недели. Их и примем за "клетки" а, за "кроликов" приме ребят. Рассаживаем "кроликов" по тем "клеткам", которые соответствуют их дням рождения. В силу принципа Дирихле найдётся "клетка" по меньшей мере с четырьмя "кроликами", а это и означает, что найдётся неделя, когда день рождения сразу у четырёх человек
Задача № 3На площадке 20 собак восьми разных пород. Докажите, что среди них есть не менее трех собак одной породы.
Решение: 20:8=2(ост. 4), 20=8*2+4. к=2,N=8, М>N, то по принципу Дирихле найдутся хотя бы три собаки одной породы.
Задача 4. В ящике лежат 10 пар чёрных и 10 пар красных перчаток одного размера. Сколько перчаток надо вытащить из ящика наугад, чтобы наверняка среди них были:
а) Две перчатки одного цвета;
б) Одна пара перчаток одного цвета;
в) Одна пара перчаток разных цветов?
Решение.:
а) Если за "клетки" принять цвета перчаток, то, взяв любые три печатки, получится, что в одной из "клеток" находятся два "кролика"- перчатки. А это и требуется.
б) Можно взять 20 перчаток на одну руку и из них нельзя будет выбрать одноцветную пару перчаток, поэтому искомое число не меньше 21. Доказать, что число 21 является искомым. Примем за "клетки" цвета перчаток (их два). В качестве "кроликов" возьмём перчатки. Согласно обобщённому принципу Дирихле в одной из "клеток" будет не меньше 11 "кроликов". Это означает, что найдётся 11 перчаток одного цвета. Но имеется только 10 пар перчаток одного цвета, поэтому все они не могут быть на одну руку. Значит, среди этих 11 перчаток найдётся одна пара перчаток одного цвета.
в) Можно взять 20 перчаток на одну руку и из них нельзя будет выбрать разноцветную пару перчаток, поэтому искомое число не меньше 21. Доказать, что число 21 является искомым. Из всех перчаток можно составить разноцветные пары. Разделим пары на две группы. В первую группу будут входить пары у в которых правая перчатка чёрная, а левая красная. Во вторую группу - пары у в которых правая перчатка красная, а левая чёрная. Эти группы и будут "клетками", а "кроликами" будут перчатки. Согласно обобщённому принципу Дирихле в одной из "клеток" будет не меньше 11 "кроликов". Это означает, что найдётся 11 перчаток из одной группы. Но имеется только 10 пар перчаток данной группы, поэтому все они не могут быть на одну руку или одного цвета. Значит среди этих 11 перчаток найдётся пара перчаток разных цветов
Задача № 1 .Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это.
Задача № 2. В коробке лежат карандаши: 7 красных и 5 синих. В темноте берут карандаши. Сколько карандашей надо взять, чтобы среди них было не менее 2 красных и не менее 3 синих?
Задача № 3 В доме живут 5 кошек. У них 16 котят. Докажите, что хотя бы у одной кошки не менее четырех котят.
Задача № 4 В классе 27 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем три ученика этого класса?
Комментариев нет:
Отправить комментарий