Элементы комбинаторики. Принцип Дирихле

Страница 3

Теперь применим принцип Дирихле,докажем утверждение задачи от противного. Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из клеток 0, 1, ., 12 попало меньше трех школьников. Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не больше 26 человек. Добавив Стаса Иванова, все равно не наберем 30 ребят. Противоречие. Можно ли утверждать, что ровно трое сделали поровну ошибок? Нет, конечно. Возможно, что все ребята, кроме Стаса, написали диктант без единой ошибки, то есть, все сделали по 0 ошибок. Можно ли считать, что по крайней мере четверо попали в одну "клетку" ? Нет, нельзя. Класс, в котором по 3 человека сделали 0, 1, 2 ошибки, по 2 человека - 3, 4, ., 12 ошибок и один - 13, удовлетворяет условию задачи.

2).

В одном доме живут 13 учеников одной и той же школы. В этой школе 12 классов. Докажите, что хотя бы два ученика, живущие в этом доме, учатся в одном и том же классе

Решение. В данной задаче классы – это клетки, а учащиеся – кролики. У нас имеется 13 «кроликов» и 12 «клеток». Учитывая принцип Дирихле, мы получаем, что хотя бы в одной клетке «кроликов» два. То есть, если в школе 12 классов, то максимум в них может учиться 12 учеников. А 13 ученик все равно будет учиться в одном из этих 12 классов.

Задачи для самостоятельного решения:

1).

В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?2).

Сколько существует 6-значных чисел, все цифры которых имеют одинаковую четность?3).

У Васи на куртке 3 кармана. Каким числом способов он может положить в эти карманы две одинаковые монетки?

4).

В корзине сидят котята — 2 черных, 2 рыжих и 1 полосатый. Сколькими способами можно выбрать трех котят так, чтобы они все были разной окраски?

5).

В корзине лежат яблоки двух сортов. Наугад берут из этой корзины несколько яблок. Какое наименьшее число яблок нужно взять, чтобы среди них оказались хотя бы два яблока одного сорта?

6).

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

Страницы: 1 2 3 


Новое в образовании:

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

Л.П. Стрелкова «Печальная история о том, как оторвали Мишке лапу»
Проснулся Данилка рано. Солнечный Зайчик был рядом. Настроение прекрасное, можно сказать, праздничное. Хотелось скорей поговорить с мамой, позавтракать и отправиться гулять. Данилка прислушался: в квартире было тихо. «Неужели еще спят?» — расстроился мальчик. Сейчас я подниму всех, — обратился он к ...

Компетенция военных вузов как субъектов образовательной деятельности
Так какова же конкретно компетенция военных вузов (в частности вузов Федеральной пограничной службы России) как образовательных учреждений? К их компетенции, в этом качестве, согласно Закону Российской Федерации «Об образовании» относятся: - материально-техническое обеспечение и оснащение образоват ...

Меню сайта

Copyright © 2022 - All Rights Reserved - www.powereducator.ru