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

Задачи с решениями по теме «Принцип Дирихле». 7 класс

1 часть. Классическая формулировка принципа Дирихле звучит так: «Пусть в n клетках сидит n+1 или больше кроликов, тогда найдётся клетка, в которой сидят по крайней мере два кролика».

Обобщенный принцип Дирихле: «Если nk+1 кроликов размещены в n клетках, то найдутся k+1 кроликов, которые посажены в одну клетку (n, k–натуральные числа)».

1.     Шесть школьников съели семь конфет.

а) Докажите, что один из них съел не менее двух конфет.

б) Верно ли, что кто-то съел ровно две конфеты?

Решение.

а) По принципу Дирихле, считая, что, "клетки" - это школьники, а "кролики" - это конфеты.

б) Не обязательно: например, все семь конфет мог съесть один школьник.

2.     В классе 15 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем два ученика этого класса ?

Решение.

Здесь "кролики" - это ученики, а "клетки" - это месяцы. Да, найдется: всего месяцев 12, а учеников 15.

3.     Для поездки на экскурсию заказали автобус с 22 местами, сблокированными по 2. На экскурсию едет 12 учеников 6 “Б” класса и 10 учеников 6 “Г” класса. Могут ли в одном блоке оказаться ученики одного класса?

Решение.

Определим, сколько блоков сидений в автобусе 22:2=11.

Возьмём 12 карточек с надписью 6 “Б” и 10 карточек с надписью “Г” и разложим по местам автобуса. Здесь "клетки" - это блоки, а "кролики" – карточки с надписью. Т.к. блоков 11, то в одном из них обязательно окажется две карточки одного класса.

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

Решение.

Разрежем ковер тремя вертикальными и тремя горизонтальными разрезами на 16 одинаковых ковриков размером 1 х 1 метр. Здесь "клетки" - это коврики, а "кролики" – дырки. Поскольку 16 > 15, то один из ковриков будет без дыр.

5.     В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

Решение.

Можно, доказательством от противного. Предположит, что нет 9-ти ящиков с яблоками одного сорта. Тогда ящиков каждого сорта не более 8-ми: 3x8=24 ящика, а по условию 25. Получили противоречие с условием. Значит, наше предположение неверно, и можно найти 9 ящиков с яблоками одного сорта.

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

Решение.

Разобьем все числа от 10 до 90 на пары (10, 90), (11, 89), ..., (49, 51),чтобы в каждой паре сумма чисел была равна 100. Таких пар 40, и еще есть 10 чисел без пары: это числа 50, 91, 92, ..., 99. Всего 50 "клеток". Так как Петя хочет написать 55 чисел, а 55 > 50, то он обязательно напишет два числа из одной пары. Их сумма и будет равна 100. Нет, не сможет.

7.     В шкафу лежат вперемешку 5 пар светлых ботинок и 5 пар темных ботинок одинаковых размера и фасона. Какое наименьшее количество ботинок надо взять наугад из шкафа, чтобы среди них была хоть одна пара (на правую и левую ноги) одинакового цвета?

Решение:

 В шкафу лежат вперемешку 5 пар светлых ботинок и 5 пар темных ботинок одинаковых размера и фасона. Какое наименьшее количество ботинок надо взять наугад из шкафа, чтобы среди них была хоть одна пара (на правую и левую ноги) одинакового цвета?

8.     В соревнованиях по вольной борьбе участвовало 12 человек. Каждый участник должен был встретиться с каждым из остальных по одному разу. Докажите, что в любой момент соревнования имеются два участника, проведшие одинаковое число схваток.

Решение.

Каждый участник должен провести 11 схваток. Распределим участников по группам. К 1-й группе отнесем тех, кто в данный момент не провел ни одной схватки; ко второй - тех, кто провел одну схватку, и т. д. К последней, 12-й группе, отнесем тех, кто провел все 11 схваток. Но одновременно не могут существовать 1-я и 12-я группы. Так, если хотя бы один участник провел все схватки, то не может быть участника, который не провел бы ни одной схватки. Отсюда число групп может быть только 11, а число участников - 12. По принципу Дирихле к одной из групп должно принадлежать, по крайней мере, два участника.

9.     Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 x 6 из чисел +1, - 1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

Решение. 

Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от - 6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит составить такой квадрат невозможно.

10. В школе учится 962 ученика. Доказать, что по крайне мере у двух учеников совпадают инициалы.

Решение.

   Из двух букв можно создать 2∙2=4 различных пары инициалов. (если это, например, буквы А и Б, то имеем А.А., А.Б., Б.А., Б.Б.)

   В русском алфавите 33 буквы. Т.к. инициалы не могут начинаться с ь и ъ, то существует только 31 буква, которая может входить в состав инициалов. Поэтому можно создать 31∙31=961 различных пар инициалов.

Возьмём 961 «ящик» и на каждом из них нанесём пару инициалов. Напишем для каждого ученика его инициалы на карточке и каждую карточку положим в тот «ящик», на котором написаны именно эти инициалы. Поскольку раскладываем 962 карточки в 961 «ящик», то, соответственно принципу Дирихле, по крайне мере в одном «ящике» будет более одной карточки. Следовательно, по крайне мере у двух учеников совпадают инициалы.

11. В классе 29 учеников. Во время диктанта один ученик допустил 13 ошибок, а все остальные ученики – меньше. Доказать, что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.

Решение.

Создадим «ящики». На каждом «ящике» напишем число, соответствующее количеству ошибок, допущенных в диктанте. Таких «ящиков» будет 14. На каждом из них записано одно из чисел от 0(нет ошибок) до 13.

Запишем на карточках фамилии учеников (таких карточек будет 29) и будем опускать карточки в «ящики» номер которого соответствует количеству ошибок.

В «ящик» №14 положим только одну карточку. Остальные 28 карточек надо разложить в 13 ящиков.

Поскольку 28 = 13∙2 + 2, значит по крайне мере в одном из «ящиков» будет лежать не меньше 3 карточек, то есть что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.

12. Для команды лыжников было сшито 20 новых костюмов. 15 из них были мужскими, 14 синего цвета, у 12 костюмов шапочки белого цвета. Докажите, что среди всех костюмов найдется мужской костюм синего цвета с белой шапочкой.

Решение.

Возьмём 15 карточек и на каждой из них напишем мужской костюм. Еще на 14 карточках напишем – синий цвет, и на 12 – белая шапочка. Всего у нас окажется 15 + 14 + 12 = 41 карточка.

Пронумеруем костюмы от 1 до 20 и будем раскладывать карточки.

Так как 41 = 20∙2 + 1, значит по крайне мере на одном костюме будет три карточки. Следовательно, среди всех костюмов найдется мужской костюм синего цвета с белой шапочкой.

2 часть. Принцип Дирихле в задачах на делимость чисел.

Формулировка принципа Дирихле для решения задач на делимость чисел: «Среди p+1 целых чисел найдутся два числа,

 дающие при делении на p один и тот же остаток».

При делении с остатком на p может получиться конечное число остатков: 0, 1, 2,…, p-1. Остатки будут клетками, а сами целые числа – будут кроликами.

1.     Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.

Решение.

При делении целого числа на 10 могут получится остатки 0, 1, 2, …, 9. Их 10, а чисел 11, значит, по принципу Дирихле, по крайней мере два числа из 11 дают одинаковый остаток при делении на 10. Обозначим их A=10a+r и  B=10b+r. Найдем их разность A-B=10(a-b). Разность делится на 10.

2.     Верно ли, что среди любых семи натуральных чисел найдутся три, сумма которых делится на 3?

Решение.

При делении на 3 есть три остатка: 0, 1, 2.

Так как 7 = 3 ∙ 2 + 1, то найдутся три числа, дающие один остаток. Пусть эти числа A=3a+r ,  B=3b+r и C=3c+r. Их сумма A+B+C=3(a+b+c)+3r  будет делиться на 3.

3 часть. Принцип Дирихле в геометрических задачах.

При решении геометрических задач удобнее применять следующую формулировку принципа Дирихле: «Пусть множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов, где N>n. Тогда, по крайней мере, в одной части будет более одного элемента.»

1.     Прямая k проходит через плоскость треугольника ABC, однако не пересекает ни одну его вершину. Необходимо доказать, что она не может пересекать три его стороны.

Решение.

Представим, как прямая l разбивает треугольник на две плоскости, назовём их q1 и q2. В роли кроликов выступят вершины треугольника, а в роли клеток – полуплоскости. Поскольку проведенная прямая l не пересекает ни одну из вершин, то каждая из них находится в той или иной плоскости. Но поскольку вершины в треугольнике три, а плоскости у нас всего две, то одна из них будет содержать две вершины. Предположим, что это вершины A и B, и находятся они в полуплоскости q2 (то есть лежат по одну сторону от l). В таком случае отрезок АВ не пересекает прямую l. То есть в треугольнике есть сторона, которую прямая l не пересекает.

2.     Внутри равностороннего треугольника со стороной 2 см бросили 5 горошин. Доказать, что найдутся две горошины, расстояние между которыми меньше 1см.

Решение.

Разделим треугольник на 4 равных треугольника как показано на рисунке. Стороны новых треугольников будут равны 1см. Поскольку бросают 5 горошин, то в один из полученных треугольников попадет хотя бы 2 горошины, расстояние между которыми будет меньше стороны треугольника, то есть меньше 1см.

                         

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

Решение.

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

4.     Какое наименьшее количество уголков               нужно разместить в квадрате 8x8 клеток, чтобы в него нельзя было больше поместить без наложения ни одной такой фигуры?

Решение.

В каждом квадрате 2x2 должно быть закрашено не менее двух клеток, иначе на три клетки всегда можно наложить данный уголок. Таких квадратов получится 16. Значит , должно быть закрашено 32 клетки. 10 уголков покрывают только 30 клеток. Поэтому, таких уголков как минимум 11. Пример на рис.

5.     В прямоугольнике 5x6 закрашено 19 клеток. Докажите, что в нем можно выбрать квадрат 2x2, в котором закрашено не менее трех клеток.

Решение.

Разделим прямоугольник на 6 частей по 5 клеток. По принципу Дирихле в одной из таких частей будет закрашено не менее 4 клеток. Тогда в квадрате 2x2 этой части будет закрашено либо 3, либо 4 клетки. Это и будет искомый квадрат.

Задачи для печати обучающимся.

1 часть. Классическая формулировка принципа Дирихле звучит так:

«Пусть в n клетках сидит n+1 или больше кроликов, тогда найдётся клетка, в которой сидят по крайней мере два кролика».

Обобщенный принцип Дирихле: «Если nk+1 кроликов размещены в n клетках, то найдутся k+1 кроликов, которые посажены в одну клетку (n, k–натуральные числа)».

1.    Шесть школьников съели семь конфет.

а) Докажите, что один из них съел не менее двух конфет.

б) Верно ли, что кто-то съел ровно две конфеты?

2.    В классе 15 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем два ученика этого класса ?

3.    Для поездки на экскурсию заказали автобус с 22 местами, сблокированными по 2. На экскурсию едет 12 учеников 6 “Б” класса и 10 учеников 6 “Г” класса. Могут ли в одном блоке оказаться ученики одного класса?

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

5.    В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

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

7.    В шкафу лежат вперемешку 5 пар светлых ботинок и 5 пар темных ботинок одинаковых размера и фасона. Какое наименьшее количество ботинок надо взять наугад из шкафа, чтобы среди них была хоть одна пара (на правую и левую ноги) одинакового цвета?

8.    В соревнованиях по вольной борьбе участвовало 12 человек. Каждый участник должен был встретиться с каждым из остальных по одному разу. Докажите, что в любой момент соревнования имеются два участника, проведшие одинаковое число схваток.

9.    Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 x 6 из чисел +1, - 1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

10.              В школе учится 962 ученика. Доказать, что по крайне мере у двух учеников совпадают инициалы.

11.              В классе 29 учеников. Во время диктанта один ученик допустил 13 ошибок, а все остальные ученики – меньше. Доказать, что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.

12.              Для команды лыжников было сшито 20 новых костюмов. 15 из них были мужскими, 14 синего цвета, у 12 костюмов шапочки белого цвета. Докажите, что среди всех костюмов найдется мужской костюм синего цвета с белой шапочкой.

2 часть. Принцип Дирихле в задачах на делимость чисел.

Формулировка принципа Дирихле для решения задач на делимость чисел: «Среди p+1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток».

При делении с остатком на p может получиться конечное число остатков: 0, 1, 2,…, p-1. Остатки будут клетками, а сами целые числа – будут кроликами.

1.    Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.

2.    Верно ли, что среди любых семи натуральных чисел найдутся три, сумма которых делится на 3?

3 часть. Принцип Дирихле в геометрических задачах.

При решении геометрических задач удобнее применять следующую формулировку принципа Дирихле: «Пусть множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов, где N>n. Тогда, по крайней мере, в одной части будет более одного элемента.»

1.    Прямая k проходит через плоскость треугольника ABC, однако не пересекает ни одну его вершину. Необходимо доказать, что она не может пересекать три его стороны.

2.    Внутри равностороннего треугольника со стороной 2 см бросили 5 горошин. Доказать, что найдутся две горошины, расстояние между которыми меньше 1см.

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

4.    Какое наименьшее количество уголков               нужно разместить в квадрате 8x8 клеток, чтобы в него нельзя было больше поместить без наложения ни одной такой фигуры?

5.    В прямоугольнике 5x6 закрашено 19 клеток. Докажите, что в нем можно выбрать квадрат 2x2, в котором закрашено не менее трех клеток.

Краткое описание документа:

Подборка задач с решениями по курсу специальной математики Математической Вертикали по тему "Принцип Дирихле" для 7 класса. Можно использовать на кружке по решению олимпиадных задач 6-7 классов.