v Добавить материал
v Справочник по математике
v Головоломки со спичками
v Вопросы посетителям

Главная

ЕГЭ 2015

ЧАТ

ПРИМЕРЫ

RSS
МАТЕРИАЛЫ

ОГЭ 2015

ТЕСТЫ

Связь



Привет, Гость

Ваша группа: Гости
Вход на сайт | Регистрация
Онлайн всего: 1
Гостей: 1
Пользователей: 0
Занимательная
математика
Высшая
математика
Школьная
математика
История
математики
Математика
для малышей
Реклама
Здесь может быть Ваша реклама, подробнее...

Разное

Принцип Дирихле или "клетки" и "зайцы"

При решении нестандартных задач, где требуется что-нибудь доказать, часто бывает полезен так называемый "принцип Дирихле".

Самый простой и понятный способ формулирования этого принципа выглядит так :

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




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

1. В классе 30 человек. В диктанте Стас Иванов сделал 13 ошибок, а остальные - меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну (может быть, по 9 ошибок).

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

В клетку 0 "посадим" всех, кто не сделал ни одной ошибки, в клетку 1 - тех, у кого одна ошибка, в клетку 2 - две, ... и так до клетки 13, куда попал один Стас Иванов.

Теперь применим принцип Дирихле (обратите внимание - это очень важное место).

Докажем утверждение задачи от противного.

Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из клеток 0, 1,..., 12 попало меньше трех школьников.

Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не больше 26 человек.

Добавив Стаса Иванова, все равно не наберем 30 ребят. Противоречие.

Можно ли утверждать, что ровно трое сделали поровну ошибок ? Нет, конечно.

Возможно, что все ребята, кроме Стаса, написали диктант без единой ошибки, то есть, все сделали по 0 ошибок.

Можно ли считать, что по крайней мере четверо попали в одну "клетку" ? Нет, нельзя.

Класс, в котором по 3 человека сделали 0, 1, 2 ошибки, по 2 человека - 3, 4, ..., 12 ошибок и один - 13, удовлетворяет условию задачи.

2. Пусть в классе 41 человек, а не 30. Докажите, что найдутся четверо, сделавшие одинаковое число ошибок. (Остальные условия - как в задаче 1).

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

Знакомства. Будем считать, что знакомство - "симметричное" отношение между людьми : если Комаров знаком с Жуковым, то и Жуков знаком с Комаровым.

4. Выберем любым образом 5 человек . Докажите, что по крайней мере двое из них имеют одинаковое число знакомых среди выбранных.

Просмотров: 15689 | Добавил: Mirinair (12.10.2010) | Коментариев: 0

Похожий материал

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Главная | Заработать | Авторские права | Наши партнеры | Обратная связь
Яндекс цитирования Яндекс.Метрика
http://free-math.ru (с) 2010-2017 гг. Дизайн от MirPS. Хостинг от uCoz.
Свободная Mатематика - сайт о математике, математиках и для математиков.
Олимпиады по математике, справочники по математике, занимательная математика, школьная математика, высшая математика, история математики, математика для малышей, математический форум для учащихся и преподавателей.