Тема: Делимость и остатки
4. Принцип Дирихле
Продолжаем решать задачи с помощью принципа Дирихле. Одна из основных трудностей - научиться выделять клетки и кроликов. Вот еще 2 задачи для тренировки.
Не страшно, если не получается решить самому. Главное. не отступайте, читайте внимательно решение, которое появляется через неделю, разбирайтесь с ним до конца, рассказывайте кому-нибудь решение так, чтобы человек его понял. Постепенно начнет получаться...
Не забывайте про дополнительные соображения, которые влияют либо на количество клеток, либо на количество кроликов, которые могут сидеть в той или иной клетке.
Задачи для самостоятельного решения
Задача 8. Несколько футбольных команд проводят турнир в один круг. Докажите, что в любой момент турнира найдутся две команды, сыгравшие к этому моменту одинаковое число матчей.
Задача 9. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно две задачи и школьники, решившие ровно три задачи. Докажите. что есть школьник, решивший не менее пяти задач.
Алгоритм решения
1. Выделение клеток и кроликов
2. Поиск дополнительного соображения
3. Применение принципа Дирихле или обобщенного принципа Дирихле
Решения и ответы
Задача 8. Пусть количество команд будет n - это наши "кролики". Возможное количество сыгранных матчей - это "клетки". Поскольку команда сама с собою играть не может, то максимальное количество сыгранных матчей - это n-1. Минимальное же количество - это 0. Но, как и в задаче про компанию, варианты о и n-1 взаимно исключают друг друга. Если есть команда, не сыгравшая ни одного матча, то не может быть команды, сыгравшей уже все n-1 матч, и наоборот. Получается, что всего матчей может быть от 0 до n-2 (это равно n - 1) или от 1 до n-1 (и это равно n - 1). При любом раскладе получается n-1 клетка для n кроликов.
По принципу Дирихле всегда найдутся две команды, сыгравшие одинаковое количество матчей.
Задача 9. Если 1, 2 и 3 задачи решили хотя бы по одному школьнику, то оставшимся семи школьникам требуется решить 35 - 6 = 29 задач. Применим обобщенный принцип Дирихле:
29 = 7 * 4 + 1. Да, действительно, найдется хотя бы 1 школьник, решивший 5 задач.
Комментариев нет:
Отправить комментарий