МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 10 (декабрь 1993). Принцип Дирихле

Задача 1. У человека на голове не более 3-х миллионов волос, в Москве более 9-ти миллионов жителей. Докажите, что найдутся
а) 2;
б) 3
москвича с одинаковым числом волос.

Задача 2. Петя хочет написать на доске 55 различных двузначных чисел так, чтобы среди них не было двух чисел, дающих в сумме 100. Сможет ли он это сделать?

Задача 3. Плоскость раскрашена в 2 цвета. Докажите, что найдутся 2 точки на расстоянии 1 метр друг от друга, окрашенные
а) в одинаковый цвет;
б) в разные цвета.

Задача 4. В ковре 4 м на 4 м моль проела 15 дырок. Докажите, что из него можно вырезать коврик 1 м на 1 м, не содержащий внутри себя дырок. (Дырки можно считать точечными).

Задача 5. Докажите, что в Вашем классе найдутся два человека, имеющие одинаковое число друзей среди своих одноклассников.

Задача 6. Из полосок размером
а) 1*5;
б) 1*6
клеток сложен прямоугольник. Докажите, что одна из его сторон делится
а) на 5;
б) на 6.

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

О задачах следующего занятия будет рассказано в 17-50 в аудитории 12-04 (просьба всем преподавателям быть там в указанное время).

Указания для преподавателей

В начале занятия рекомендуется разобрать задачу 4 из прошлого занятия. Можно разобрать задачу 3 про депутатов из прошлого занятия.

Основная тема сегодняшнего занятия - принцип Дирихле. Все задачи, кроме последней, решаются с помощью этого принципа (иногда с использованием дополнительных идей).

Указания к задачам

Задача 2. Нет, не сможет. Разбейте числа на пары: (10,90), (11,89), ..., (49,51), (50,50), (91,91), ..., (99,99). Всего пар будет 59, а чисел мы берем 55. Значит, найдутся два числа из одной пары. Поскольку мы берем различные числа, то и в этой паре они будут различны. В сумме они будут давать 100, поскольку сумма чисел в каждой паре равна 100.

Задача 3.
а) Рассмотрите три точки в вершинах правильного треугольника.
б) Найдите две точки, раскрашенные в разные цвета, и соедините их ломанной, длина каждого из звеньев которой равна 1.

Задача 4. Разбейте ковер на 16 ковриков 1*1. Поскольку всего дырок 15, один из этих ковриков будет без дырок.

Задача 5. Пусть в классе всего N человек. Каждый школьник может иметь в классе от 0 до N-1 друзей. Если все имеют разное число друзей, то найдется человек, имеющий 0 знакомых, и найдется человек, имеющий N-1 знакомых, т. е. знакомый со всеми - противоречие.

Задача 6. В пункте а) можно заметить, что площадь прямоугольника делится на 5, а так как 5 - простое, то и одна из его сторон делится на 5.

В пункте б) приходится красить прямоугольник в 6 цветов (по диагонали) и считать: одного из цветов будет больше, чем другого.