Решение олимпиадных задач ,используя принцип Дирихле второе занятие
олимпиадные задания по алгебре (7 класс) на тему
Данный материал можно использовать в рамках подготовки учащихся к олимпиаде, как дополнительный материал на кружках и элективных занятиях.
Скачать:
Вложение | Размер |
---|---|
![]() | 764.39 КБ |
Предварительный просмотр:
Принцип Дирихле 1-й год обучения. 6 класс
Принцип Дирихле, как вам уже известно – утверждение, которое устанавливает связь между объектами («кроликами») и контейнерами («клетками») при выполнении определенных условий. Названо оно так по имени немецкого математика Дирихле Петер Август Лежён, который его сформулировал и доказал.
Если в N клетках сидят не менее N + 1 кролик, то в какой-то клетке сидит не менее двух кроликов.
В простейшем виде Принцип Дирихле выражается так:
Если десять кроликов сидят в девяти клетках, то в какой-то клетке сидят не меньше двух кроликов.
Есть также общая формулировка:
Если N кроликов сидят в К клетках, то найдётся клетка, в которой сидят не меньше чем N/K кроликов, и найдётся клетка, в которой сидят не больше чем N/K кроликов.
Рассмотрим выполнение данного принципа на примерах.
Пример 1. 4 кролика рассаживают в 3 клетки (N>K).
Пример 2. 3 кролика рассаживают в 4 клетки (N
Пусть вас не смущает дробное число кроликов – если получится, что в клетке не меньше 7/3 кроликов, значит, их не меньше трех.
Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, ни клетки.
Пример 3. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение: В году 365 (или 366) дней. Пусть дни – «клетки», ученики – «кролики». Тогда в некоторой клетке 400/366 кроликов, т.е. больше одного. Следовательно, не меньше двух.
Иногда при решении задач используют обобщенный принцип Дирихле:
Если kN+1 кроликов размещены в N клетках, то найдутся k+1 кроликов, которые посажены в одну клетку.
Пример 4
Решим еще несколько задач.
Задача 1.
Задача 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6×6 из чисел +1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.
Решение: Допустим, что квадрат составлен. Тогда суммы чисел могут меняться от - 6 до 6. Всего 13 значений (кролики). Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем: 6 + 6 + 2 = 14 различных мест (клетки). Получили противоречие, значит, составить такой квадрат невозможно.
Задача 3. На зачет пришли 65 школьников. Им предложили 3 контрольные работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на контрольных?
Решение: Имеет 65 школьников – «кролики». Рассмотрим множество наборов из трёх оценок за соответствующие контрольные. Количество таких наборов 4 ⋅ 4 ⋅ 4 = 43 или 64 (4 возможности за каждую из трёх работ) – «клетки». Поскольку 65>64, то по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.
Задача 4. В школе 735 учащихся. Можно ли утверждать, что, по крайней мере, 3 ученика должны отмечать день своего рождения в один день?
Решение: Да. Так как даже с учетом високосного года: 735/366 > 2 или 735 = 366 × 2 + 3.
Задача 5. Верно ли, что из 6-ти любых целых чисел, найдутся два числа, разность которых делиться на 5?
Решение: Пусть любые 6 чисел – это кролики. Остатки от деления на 5: 0, 1, 2, 3, 4, т.е. их всего 5 – это клетки, в каждую из которых будем помещать числа, дающие одинаковый остаток при делении на 5. Имеем 6 кроликов в 5 клетках. Значит, обязательно найдется два числа, дающих одинаковые остатки при делении на 5. Значит, их разность делится на 5.
Задача 6. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.
Решение: По условию задачи наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2, ..., 13 ошибок. Эти варианты будут "клетками", а ученики станут "кроликами". Тогда по (обобщенному) принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну "клетку", то есть сделавших одинаковое число ошибок.
Задача 7. В мешке лежат шарики 2-х разных цветов (много белых и много черных). Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.
Решение: Это - просто применение принципа Дирихле: кроликами будут взятые шарики, а клетками - черный и белый цвета. Клеток две, поэтому если кроликов хотя бы три, то какие-то два попадут в одну клетку (будет 2 одноцветных шарика). С другой стороны, взять два шарика мало, потому что они могут быть двух разных цветов. Ответ: 3 шарика.
Задача 8. В коробке лежат 10 красных карандашей, 8 синих, 8 зеленых и 4 желтых. Наугад (произвольно) из коробки вынимают n карандашей. Определить наименьшее число карандашей, которые необходимо вынуть, чтобы среди них было:
1) не менее 4 карандашей одного цвета;
2) по одному карандашу каждого цвета;
3) хотя бы 6 карандашей синего цвета.
Решение: 1) Так как у нас всего 4 цвета, согласно принципу Дирихле (карандаши будут "кроликами", а цвета - "клетками"), по крайней мере, 4 карандаша будут одинакового цвета, если вынуть 13 карандашей.
Докажем, что n = 13 является наименьшим числом. С этой целью покажем ситуацию, при которой условия задачи не выполняются. Например, когда вынуто по 3 карандаша каждого цвета (12 карандашей). Отметим, что эта ситуация возможна, так как в коробке находится не менее 3 карандашей каждого цвета.
Случаи 2) и 3) решаются аналогично.
Ответ: 1) 13; 2) 10+8+8+1=27; 3) 10+8+4+6=28.
Задача 9. Внутри равностороннего треугольника со стороной 1 лежат 5 точек. Доказать, что найдутся две точки из пяти, расстояние между которыми меньше 0,5.
Решение: Пусть 5 точек – «зайцы». Так как «клеток» должно быть меньше, то пусть их будет 4. Чтобы получить 4 «клетки», разобьем равносторонний треугольник с помощью средних линий на 4 равных треугольника – «клетки». Так как «зайцев» - 5, «клеток» - 4 и 5>4, то по принципу Дирихле найдется клетка – равносторонний треугольник со стороной 0,5см, в который попадут не менее 2 зайцев – точек. А так как все 4 треугольника равны и расстояние между точками в любом треугольнике будет меньше, чем 0,5см, то мы доказали, что между некоторыми 2 точками из 5 расстояние будет меньше, чем 0,5 см.
Задача 10. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка - точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.
Решение: Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок, так как 51=25*2+1.
Задания для малой олимпиады.
Задача №1: В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы 2 ученика, фамилии которых начинаются с одной буквы?
Решение: Обозначим 35 учеников за кроликов, а буквы за клетки. В русском алфавите 33 буквы. Фамилии не могут начинаться на твердый и мягкий знак. Так как 35>31, то по принципу Дирихле найдется 2 ученика, у которых фамилия начинается с одной буквы.
Задача №2: В классе 37 учеников. Докажите, что среди них найдутся 4 ученика, отмечающие день рождения в одном месяце.
Решение:
1 способ: Пусть 37 учеников – «зайцы», а 12 месяцев – «клетки». Так как 37 12*3+1, то, применяя обобщенный принцип Дирихле, мы получаем, что найдется 4 ученика, родившиеся в один месяц
2 способ: Если в каждый месяц родилось не более 3 учеников, то всего учеников будет 36. А по условию задачи их 37, значит, такого быть не может. Поэтому найдется 4 ученика, отмечающие день рождения в один месяц.
Задача №3: Дано 9 целых чисел. Докажите, что из них можно выбрать 2, разность которых делится на 8.
Решение: Обозначим за «клетки» 0 остатки от деления на 8: 0, 1, 2, 3, 4, 5, 6, 7. «Клеток» будет 8. За «зайцев» обозначим 9 целых чисел. Так 9>8, то 2 целых числа будут иметь одинаковый остаток при делении на 8, а поэтому их разность будет делиться на 8.
Задания для заочной олимпиады
Задача № 1: В ящике комода, который стоит в темной комнате, лежат 10 коричневых и 10 красных носков одного качества и размера. Сколько носков нужно взять из ящика комода, не глядя, что бы среди них обязательно оказалась пара носков одного цвета?
Решение: Хорошо, что на левую и правую ногу носки одинаковые, поэтому достаточно побеспокоится только о цвете.
Задача № 2: В ящике комода, который стоит в темной комнате, лежат 10 пар коричневых и 10 пар черных перчаток одного качества и размера. Сколько перчаток нужно взять из ящика комода, не глядя, что бы среди них обязательно оказалась пара перчаток одного цвета?
Решение: Можно вытащить 10 черных перчаток на левую руку и 10 коричневых – на правую. А 21-я обязательно образует пару
Задача № 3 Внутри правильного шестиугольника со стороной 1см расположено 7 точек. Докажите, что расстояние между двумя точками меньше, чем 1см.
Решение: Примем 7 точек за зайцев. Построим 6 клеток. Для этого разобьем правильный шестиугольник на 6 правильных треугольников, как на рисунке. Так как 7>6, то по принципу Дирихле хотя бы в один треугольник попадут не менее 2 точек. А расстояние между любыми 2 точками в правильном треугольнике со стороной 1см меньше 1см.
Задача № 4: Петя хочет написать на доске 55 различных двузначных чисел так, чтобы среди них не было 2-х, чисел, дающих в сумме 100. Сможет ли он это сделать?
Решение: Двузначных чисел всего 90. Нет среди них пары (в смысле получения 100 в сумме) у чисел 50,91,92,…,99. т.е. десяти чисел. Оставшиеся 80 чисел образуют 40 «пар». Эти 40 «пар» и 10 чисел без «пары» можно обозначить за клетки. Тогда зайцами будут 55 чисел. Т.к. 55 >50, то найдется 2 числа, которые или совпадают, или в сумме дают 100. Значит, Петя не может осуществить свой план.
По теме: методические разработки, презентации и конспекты
Методика решения олимпиадных задач
Методика решения олимпиадных задач (презентация)...
Общие приемы решения олимпиадных задач
Олимпиадные задачи под частую ставят в тупик не только школьников, но и учителей. Трудно подобрать какой-либо способ их решения. Поэтому я постаралась выделить основные способы решеия олимпиадных зада...
Методическая разработка по решению олимпиадных задач по информатике на тему "Системы счисления"
Решение олимпиадных задач по теме "Системы счисления"...
![](/sites/default/files/pictures/2015/01/24/picture-572222-1422113843.jpg)
Принцип Дирихле. Решение олимпиадных задач. Первое занятие
Материал предназначен для подготовке к олимпиаде....
![](/sites/default/files/pictures/2013/06/10/picture-232356-1370839042.jpg)
Программа "Решение олимпиадных задач по физике. 7 класс".Программа "Решение олимпиадных задач по физике. 8 класс".
С 2013 года участвую в работе инновационной площадки «Центр дополнительного образования – интегрирующая образовательная среда по работе с одарёнными детьми».Решение задач способствует более глубокому ...
![](/sites/default/files/pictures/2013/02/24/picture-210523-1361691869.jpg)
Дидактические материалы для занятий математического кружка "Математика +" 7 класс. Занятие36-38. Решение олимпиадных задач
Математический кружок- одна из наиболее эффективных форм внеклассных занятий. Для меня, как учителя, важно иметь под рукой пособие, в котором представлены идеи решений и которое позволило бы провести ...
![](/sites/default/files/pictures/2012/12/08/picture-160482-1354992668.jpg)
Рабочая программа индивидуальных занятий по курсу «Практикум по решению олимпиадных задач по математике» для 7 класса
Рекомендуется для профильных классов...