Презентация на тему принцип дирихле. Принцип Дирихле. Задачи и решения. а) геометрические задачи


Наш проект - учебный, практического применения. В школьном туре олимпиады встретилась задача. Мы решили изучить подробнее этот вопрос: - Познакомились с литературой по этой теме. - Рассмотрели исторический материал. - Изучили принцип Дирихле. - Подготовили реферат и презентацию. - Научились применять его при решении задач. - Планируем выступить перед учащимися 6 классов.


Дирихле родился в вестфальском городе Дюрене в семье почтмейстера. В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом. С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье. Биография


В 1827г. устраивается на должность приватдоцента университета Бреслау (Вроцлав). - В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент. - Затем с 1831 г. как экстраординарный профессор. - С 1839 г. как ординарный профессор Берлинского университета. В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. Биография




Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца. n, то хотя бы в одной клетке сидят, по крайней мере, два зайца."> n, то хотя бы в одной клетке сидят, по крайней мере, два зайца."> n, то хотя бы в одной клетке сидят, по крайней мере, два зайца." title="Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца."> title="Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят, по крайней мере, два зайца.">




Если в n клетках сидит m голубей, причем m


N, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев." title="Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев." class="link_thumb"> 9 Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев. n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев."> n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев."> n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев." title="Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев."> title="Обобщенный принцип Дирихле Предположим, m зайцев рассажены в n клетках. Тогда если m > n, то хотя бы в одной клетке содержится не менее m:n зайцев, а также хотя бы в одной другой клетке содержится не более m:n зайцев.">


12, то, по принципу Дирихле, найдется, как миним" title="В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как миним" class="link_thumb"> 10 В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как минимум, одна «клетка», в которой будет сидеть, по крайней мере, 2 «зайца». Ответ: Найдется месяц, в котором будут отмечать дни рождения не менее 2 учеников класса. Задача 1. 12, то, по принципу Дирихле, найдется, как миним"> 12, то, по принципу Дирихле, найдется, как минимум, одна «клетка», в которой будет сидеть, по крайней мере, 2 «зайца». Ответ: Найдется месяц, в котором будут отмечать дни рождения не менее 2 учеников класса. Задача 1."> 12, то, по принципу Дирихле, найдется, как миним" title="В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как миним"> title="В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающих дни рождения в один месяц. Решение: Пусть 15 учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Так как 15>12, то, по принципу Дирихле, найдется, как миним">


В ковре размером 3х3 метра Коля проделал 8 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок. Решение: Разрежем ковер на 9 ковриков размерами 1х1 метр, Так как ковриков - «клеток» - 9, а дырок - «голубей» - 8. Ответ: Найдется коврик без дырок внутри. Задача 2.


В 3А классе учится 27 школьников, знающих всего 109 стихотворений. Докажите, что найдется школьник, знающий не менее 5 стихотворений. Решение: Предположим, что каждый школьник знает не более 4 стихотворений. Значит, 27 школьников знают не более 427=108(стихотворений) Ответ: Значит найдется школьник, знающий не менее 5 стихотворений. Задача 3.


В городе 15 школ. В них обучается 6015 школьников. В концертном зале городского Дворца культуры 400 мест. Доказать, что найдётся школа, ученики которой не поместятся в этот зал. Решение: Предположим, что в каждой школе не более 400 учеников. Значит во всех школах = 6000(школьников). Ответ: Поэтому ученики этой школы не поместятся в зал на 400 мест. Задача 4.


В школе 5 восьмых классов: 8А, …, 8Д. В каждом из них учится по 32 человека. Докажите, что найдутся 14 человек, родившихся в один месяц. Решение: Предположим, что в каждом месяце родилось не более 13 учеников. Значит за 12 месяцев родилось 1213=156(школьников). Но по условию в школе обучается 532=160(человек). Ответ: Значит, найдется месяц, в котором родилось больше, чем 13 учеников, то есть хотя бы 14. Задача 5.


Внутри равностороннего треугольника со стороной 1см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5см. Решение: Можно получить 4 «клетки», разбив равносторонний треугольник с помощью проведения отрезков, соединяющих середину сторон. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками». Задача 6.


4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек." title="2 1 4 3 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек." class="link_thumb"> 16 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек. 4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> 4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> 4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек." title="2 1 4 3 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> title="2 1 4 3 Треугольники – «клетки», 5 точек – 5 «зайцев». 5>4, по принципу Дирихле, найдется равносторонний треугольник со стороной 0,5см, в который попадут не менее двух точек."> Выводы: Таким образом, применяя данный метод, надо: Определить, что удобно в задаче принять за «клетки», а что за «зайцев». Получить «клетки»; чаще всего «клеток» меньше (больше), чем «зайцев» на одну (или более). Выбрать для решения требуемую формулировку принципа Дирихле. Принцип Дирихле важен, интересен, полезен. Его можно применять в повседневной жизни, что развивает логическое мышление. Многие олимпиадные задачи решаются, используя это специальный метод. Он дает возможность обобщать.

Принцип Дирихле. Задачи и решения


Основные сведения. Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца». Принцип Дирихле настолько простой и очевидный, что можно применять его не зная его формулировки.


Обобщенная формулировка принципа: «Если множество, которое состоит из Nk+1 элементов разбить на k множеств, то хотя бы в одном подмножестве окажется не меньше N+1 элементов» или «Если множество, которое состоит из m элементов, разбить на k подмножеств, то хотя бы в одном подмножестве окажется не менее m/k элементов»


Принцип Дирихле имеет геометрическую формулировку: А) если отрезок длиной l разбить на n отрезков (которые не имеют общих внутренних точек), то длина наибольшего отрезка не менее l/n, а длина наименьшего отрезка не больше l/n Б) если фигуру площадью S разбить на n частей (которые не имеют общих внутренних точек), то площадь наибольшей фигуры не менее чес S/n, а площадь наименьшей не более чем S/n


Задачи и примеры решений Задача 1. На плоскости дано шесть точек общего положения (никакие три из них не лежат на одной прямой). Любые две точки соединены отрезком, каждый отрезок покрашено либо в красный, либо в синий цвет. Доказать, что найдется треугольник с вершинами в данных точках, все стороны которого имеют один цвет. Решение. Обозначим данные точки А1, А2, А3, А4, А5, А6. Из точки А1 выходит 5 отрезков двух цветов. По принципу Дирихле среди этих отрезков есть 3 отрезка одного цвета. Пускай для конкретности это отрезки А1 А2, А1 А3 , А1 А4 красного цвета. Рассмотрим отрезки А2 А3, А3 А4, А2 А4. Возможные случаи: А) среди этих отрезков есть красный, например А2 А3. Тогда в треугольнике А1 А2 А3 все стороны красные; Б) среди этих отрезков нет красных. Тогда в треугольнике А2, А3, А4 все стороны синие.


Задача 2. В квадрате, сторона которого равна 6 см, размещена 1991 точка. Доказать, что квадратом, сторона которого равна 5 см, можно покрыть хотя бы 664 из этих точек. Решение. Нетрудно заметить, что 664 составляет приблизительно треть от 1991, а именно 1991 = 3*663+2. Поэтому при любом разбитии множества, состоящего из 1991 точки, на три подмножества, хотя бы в одно из этих подмножеств попадет 664 или более точек. Значит, для решения задачи достаточно показать, что квадрат со стороной 6 см можно разбить на три части, каждую из которых можно покрыть квадратом со стороной 5 см. Это видно по рисунку, в котором AK=5см, BO=3v2cм

Решение. Допустим, что в некотором выпуклом 2n-угольнике каждая диагональ параллельна некоторой стороне. Идея получения противоречия такова: выберем наибольшую группу взаимно параллельных диагоналей и покажем, что такое количество диагоналей нельзя разместить внутри выпуклого 2n-угольника. Значит, разобьем все диагонали на группы взаимно параллельных диагоналей. Таких групп не более чем 2n (некоторые стороны могут быть параллельны между собой). Количество всех диагоналей равно = 2n*(n – 1,5), поэтому в некоторой группе есть не менее чем (n - 1) диагоналей. Эти (n - 1) диагонали параллельны некоторой стороне А1 А2 и лежат относительно нее в одной полуплоскости. Но тогда на эту сторону и на эти (n - 1) диагоналей приходиться 2n вершин, т.е. та из диагоналей, которая лежит как можно дальше от стороны А1 А2 , должна быть стороной 2n-угольника. Противоречие. значит, предположение неверное, поэтому найдется диагональ, которая не параллельна ни одной из сторон. Задача 3. Доказать, что в произвольном выпуклом 2n-угольнике найдется диагональ, которая не параллельна ни одной из сторон.


Решение. Разобьем квадрат на 50 прямоугольников со сторонами 1 см и 2 см. тогда хотя бы в один из этих прямоугольников не попадет менее чем 3 точки. Эти три точки образуют треугольник, площадь которого не превышает половины площади прямоугольника, в котором этот треугольник находится. Задача 4. Внутрь квадрата со стороной 10 см «брошено» 101 точку (ни какие три не лежат на одной прямой). Доказать, что среди этих точек есть три, которые образуют треугольник, площадь которого не превышает 1 см2.


Задачи для самостоятельного решения. Задача 1. Доказать, что из произвольных 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100. Задача 2. Доказать, что существует натуральное число, последние четыре цифры которого 1972 и которое делится на 1971. Задача 3. Можно ли найти такой натуральный показатель степени числа 3, который заканчивается на 0001?


Задача 4. В ящике лежат носки: 10 черных, 10 синих, 10 белых. Какое наименьшее количество носков нужно вытянуть, не смотря, чтоб среди вытянутых оказалось два носка: а) одного цвета; б) разных цветов; в) черного цвета? Задача 5.В классе 25 учеников. Известно, что среди любых трех из них есть двое друзей. Доказать, что есть ученик, у которого не менее чем 12 друзей. Задача 6. Комиссия из 60 человек провела 40 заседаний, причем на каждом присутствовали ровно 10 членов комиссии. Доказать, что какие-то 2 члена комиссии встретились на заседаниях хотя бы дважды.


Задача 7. Внутри правильного шестиугольника со стороной 3 см произвольным образом размещено 55 точек, никакие три из которых не лежат на одной прямой. Доказать, что среди них найдутся три точки, образующие треугольник, площадь которого не превышает v3/4см2. Задача 8. Дано n+1 разное натуральное число, каждое из которых меньше чем 2n. Доказать, что из них можно выбрать 3 таких числа, одно из которых равняется сумме двух других. Задача 9. Доказать, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100.


Задача 10. 11 учеников занимаются в 5 кружках дома культуры. Доказать, что найдется два ученика A и B такие, что все кружки, которые посещает А, посещает и В. Задача 11. Доказать, что среди любых 10 целых чисел найдется несколько (возможно одно), сумма которых делится на 10. Задача 12. На плоскости дано 17 точек, никакие три из которых не лежат на одной прямой. Любые две точки соединены отрезком. Каждый отрезок покрашено либо в красный, либо в синий, либо в зеленый цвет. Доказать, что найдется треугольник с вершинами в данных точках, все стороны которого имеют одинаковый цвет.


Задача 13. Каждая точка плоскости покрашена в белый или черный цвет. Доказать, что на этой плоскости найдется треугольник с углами 300, 600, 900 и гипотенузой 2, вершины которого одноцветные Задача 14. В квадрате, сторона которого равна 1, взято 51 точку. Доказать, что некоторые три из этих точек обязательно находятся внутри круга радиуса 1/7. Задача 15. На плоскости дано 25 точек, причем среди произвольных трех найдутся две на расстоянии меньше 1. Доказать, что существует круг радиуса 1, который вмещает не менее чем 13 данных точек.


Задача 16. На отрезке длиной 1 закрашено несколько отрезков так, что расстояние между произвольными двумя закрашенными точками не равно 0,1. Доказать, что сумма длин всех закрашенных отрезков не превышает 0,5. Задача 18. Дано бесконечная бумага в клето чку и фигура, площадь которой меньше площади клето чки. Доказать, что эту фигуру можно положить на бумагу так, чтобы она не накрыла ни одной вершины клето чек. Задача 17. Дано числа 21 – 1,22 – 1,23 – 1,…,2n-1, где n3 – непарное число. Доказать, что хотя бы одно из данных чисел делится на n.


Спасибо за внимание!


Гипотеза: применение соответствующих формулировок принципа Дирихле – наиболее рациональный подход при решении задач. Наиболее применяема формулировка: "Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов " Гипотеза: применение соответствующих формулировок принципа Дирихле – наиболее рациональный подход при решении задач. Наиболее применяема формулировка: "Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов " Цель: изучить, один из основных методов математики, принцип Дирихле


Этот принцип утверждает, что, если множество из N элементов разбито на п непересекающихся частей, не имеющих общих элементов, где N>n то, по крайней мере, в одной части будет более одного элемента Наиболее часто принцип Дирихле формулируется в одной из следующих форм: Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов"


У1. "Если в n клетках сидят не более n-1 "кроликов", то есть пустая клетка" У1. "Если в n клетках сидят не более n-1 "кроликов", то есть пустая клетка" У2. "Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х "кроликов" " У3. "Если в n клетках сидят не более nk-1 "кроликов", то в какой-то из клеток сидят не более k-1 "кроликов " У4. "Если в n клетках сидят не менее n k+1 "кроликов", то в какой-то из клеток сидят не менее k+1 "кроликов""


У5. "Непрерывный принцип Дирихле. "Если среднее арифметическое нескольких чисел больше a, то, хотя бы одно из этих чисел больше a"; У6. "Если сумма n чисел меньше S, то по крайней мере одно из этих чисел меньше S/n". У7. "Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".


Задача. В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголок. Научная классификация Царство: Растения Отдел: Голосеменные Класс: Хвойные Семейство: Сосновые Вид: Ели


Геометрическая задача Внутри равнобедренной трапеции со стороной 2 расположено 4 точки. Доказать, что расстояние между некоторыми двумя из них меньше 1. Решение. Разобьем трапецию со стороной 2 на три треугольника со стороной 1. Назовем их "клетками", а точки – "кроликами". По принципу Дирихле из четырех точек хотя бы две окажутся в одном из трех треугольников. Расстояние между этими точками меньше 1, поскольку точки не лежат в вершинах треугольников


Задача на комбинаторику В коробке лежат шарики 4-х разных цветов (много белых, много черных, много синих, много красных). Какое наименьшее количество шариков надо наощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета? Решение Возьмем за «кроликов» шары, а за «клетки» - черный, белый, синий, красный цвета. Клеток 4, поэтому если кроликов, хотя бы 5, то какие-то два попадут в одну клетку (будет 2 одноцветных шарика).


Задача Дано n+1 различных натуральных чисел. Доказать, что из них можно выбрать два числа А и В, разность которых делится на n Задача Докажите, что среди n+1 различных натуральных чисел найдутся хотя бы два числа А и В такие что, число А2 - В2 делится на n. Докажем, что (А – B)(A+B) кратно n Задача Докажите, что среди n+1 различных натуральных чисел найдутся хотя бы два числа А и В такие что, число А3 – В3 делится на n. Докажем, что (А – B)(A2+AB +B2) кратно n


Малая теорема Ферма Если p - простое число, a - целое число, не делящееся на p, то a p-1 при делении на p даёт остаток 1 Доказательство Каждое из p - 1 чисел a, 2a, . . ., (p-1) a ("кроликов") даёт при делении на p ненулевой остаток (ведь a не делится на p)


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:
Содержание 1. Принцип Дирихле2. Задачи на принцип Дирихле3. Графы4. Задачи на графы5. Четность6. Задачи на четность7. Делимость и остатки8. Задачи на делимость9. Остатки10. Задачи на остатки11. Геометрические задачи Сформулируем принцип Дирихле: Пусть в n коробок помещены k предметов. Если количество предметов больше количества коробок (k > n), тогда существует хотя бы одна коробка, в которой бы находилось 2 предмета.Примечание. Отметим, что не важно, в какой именно коробке находятся по крайней мере два предмета. Также не имеет значение, сколько предметов в этой коробке, и сколько всего таких коробок. Важно то, что существует хотя бы одна коробка с не менее чем двумя предметами (два или более).Очевидно, слова «коробки» и «предметы» нужно понимать в обобщенном смысле; вовсе не обязательно, чтобы они означали реальные коробки и предметы Принцип Дирихле Часто это предложение формулируют в шуточной форме: Если по n клеткам рассадить зайцев, число которых больше n, то найдется клетка, в которой находится больше одного зайца. Доказательство принципа чрезвычайно просто, в нем используется тривиальный подсчет кроликов в клетках. Если бы в каждой клетке сидело не более одного кролика, то всего в наших n клетках сидело бы не более n кроликов, что противоречило бы условиям. Таким образом, мы доказали принцип Дирихле методом «от противного». Справедлив также обобщенный принцип Дирихле:Если по n ящикам разложить предметы, число которых больше n*k(где k – натуральное число), то найдется ящик, в котором находится больше k предметов. Задача 1. В мешке лежат шарики двух цветов: черного и белого. Какое наименьшее число шарикрв нужно достать из мешка вслепую, чтобы среди них заведомо оказались два шарика одного цветаРешение.Задача 2. В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголокРешение.Задача 3. В международном симпозиуме участвуют 17 человек. Каждый знает не более трех языков и любые два участника могут общаться между собой. Доказать, что хотя бы три участника, знают один и тот же язык.Решение.Задача 4. Доказать, что среди шести целых чисел найдутся два числа, разность которых делится на 5.собственным знакомым).Решение. Задача 5. В зале находятся n человек (n ≥ 2). Доказать, что среди них найдутся два человека с одинаковым числом знакомых (предполагается, что если человек A является знакомым человека B, то и B является знакомым A; никто не считается своимРешение.Задача 6. Доказать, что для любого натурального числа n ≥ 1, существует натуральное число, состоящее из цифр 0 и 5, делящееся на n.Решение.Задача 7. В доме живут 40 учеников. Существует ли такой месяц в году, когда хотя бы 4 ученика празднуют свой день рождения.Решение.Задача 8. Доказать, что из n+1 различных натуральных чисел, меньших 2n, можно выбрать 3 числа так, чтобы одно число было равно сумме двух других.Решение. Задача 9. В 500 коробках лежат яблоки. Известно, что в каждой коробке находятся не более 240 яблок. Доказать, что существуют хотя бы 3 коробки, которые содержат одинаковое количество яблок.Решение.Задача 10. В коробке лежат 10 красных карандашей, 8 синих, 8 зеленых и 4 желтых. Наугад (произвольно) из коробки вынимают n карандашей. Определить наименьшее число карандашей, которые необходимо вынуть, чтобы среди них было:a)не менее 4 карандашей одного цвета;b)по одному карандашу каждого цвета;c)хотя бы 6 карандашей синего цвета.Решение.Задача 11. 15 белок собрали 100 орехов. Докажите, что какие-то две из них собрали одинаковое количество орехов. Решение. Задача 12. Точки на плоскости раскрашены двумя цветами. Показать, что существуют две точки одинакового цвета, расположенные на расстоянии 1м.Решение.Задача 13. На плоскости даны 25 точек таким образом, что две точки из любых трех расположены на расстоянии меньше 1. Доказать, что существует круг радиуса 1, содержащий не менее 13 из данных точек.Решение.Задача 14. Пусть a1,a2, ... ,an - перестановка чисел 1,2,3,...,n. Доказать, что произведение (a1 - 1)(a2 - 2)...(an - n) будет четным, если n – нечетно.Решение. Решение. Достаем из мешка 3 шарика. Если среди этих шариков было не более одного шарика каждого из цветов – это очевидно, и противоречит тому, что мы достали три шарика. С другой стороны, понятно что двух шариков может и не хватить. Ясно, что кроликами в этой задаче являются шарики, а клетками – цвета: черный и белый. Решение. Решим эту задачу, используя принцип Дирихле. Пусть имеются 500000 коробок, соответственно пронумерованных 1,2,3,...,500000. Помещаем (мысленно) в эти коробки 800000 елей следующим образом: в ящик с номером s помещаем ели, на которых ровно s иголок. Поскольку елей, то есть "предметов", больше, чем коробок, следует, что по крайней мере одна коробка будет содержать не менее двух предметов, то есть, не менее двух елей. Так как в одной и той же коробке находятся ели с одинаковым числом иголок, приходим к выводу, что существуют хотя бы две ели с одинаковым числом иголок. Решение. Пусть A - один из участников. Он может общаться с каждым из 16 участников на не более одном из трех известных ему языков. Тогда существует язык, на который Aговорит с не менее чем шестью участниками. Пусть B - любой из них. Ясно, что среди остальных 5 участников есть 3, с которыми B может общаться на одном языке (назовем его "второй язык"). Если среди этих троих участников хотя бы два, скажем C и D, могут говорить на "втором языке", то B, C и D и есть те три человека, говорящие на одном языке. Решение. Рассмотрим 5 коробок, пронумерованных 0,1,2,3,4, - цифрами, представляющими собой остатки от деления на 5. Распределим в эти коробки шесть произвольных целых чисел в соответсвии с остатком от деления на 5, то есть, в одну и ту же коробку помещаем числа, имеющие одинаковый остаток от деления на 5. Поскольку чисел ("предметов") больше, чем коробок, согласно принципу Дирихле, существует одна коробка, содержащая более одного предмета. То есть, существуют (по крайней мере) два числа, помещенные в одну и ту же коробку. Следовательно, существуют два числа с одинаковым остатком от деления на 5. Тогда, разность этих чисел делится на 5. Решение. Обозначим через m количество человек, которые имеют хотя бы одно знакомство в зале (это и будут "предметы"). Каждый из этих m человек может иметь 1,2,...,m-1 знакомых ("коробки" - число знакомых).Согласно принципу Дирихле, сущетсвуют два человека с одинаковым числом знакомых. Решение. Рассмотрим натуральные числаи распределим эти "предметы" в "коробки" пронумерованные 0,1,...,n-1 (цифрами, представляющими собой остатки от деления на n). В коробку s помещаем число ak, которое имеет остаток от деления на n, равный s.Если в коробке с номером 0 находится один "предмет" (то есть, одно число), тогда задача решена. В противном случае n "предметов" находятся в n-1 "коробках". Согласно приципу Дирихле, существуют два "предмета" (числа), находящиеся в одной и той же коробке. То есть, существуют два числа, имеющие одинаковый остаток от деления на n. Их разность будет делится на n, и как легко заметить, разность чисел, состоящих из цифр 0 и 5, также будет числом, состоящим из 0 и 5. Решение. Пусть "коробками" будут месяцы, а "предметами" - ученики. Распределяем, "предметы" по "коробкам" в зависимости от месяца рождения. Так как число месяцев, то есть, коробок, равно 12, а число учеников, то есть, предметов 40 = 12·3+4, согласно принципу Дирихле существует коробка (месяц) с по крайней мере 3+1=4 предметами (учениками). Решение. Пусть a1

Похожие публикации