Решение олимпиадных задач ,используя принцип Дирихле второе занятие
олимпиадные задания по алгебре (7 класс) на тему

Принцип Дирихле 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. Значит, Петя не может осуществить свой план.