Printsip_Dirikhle

Задачи для самостоятельного решения.

Задача 1.

Докажите, что никакая прямая не может пересекать все три стороны треугольника.

Задача 2.

В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.

Задача 3.

В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка — точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

Задача 4.

В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну.

Задача 5.

Пятеро молодых рабочих получили на всех зарплату – 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты.

Задача 6.

В клетках таблицы 3 ? 3 расставлены числа – 1, 0, 1. Докажите, что какие-то две из 8 сумм по всем строкам, всем столбцам и двум главным диагоналям будут равны.

Ответы.

Задача 1.

Прямая делит плоскость на две полуплоскости, которые мы назовем «клетками».

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

Задача 2.

По условию задачи, наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2, ..., 13 ошибок. Эти варианты будут «клетками», а ученики станут «кроликами». Тогда по принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну «клетку», то есть сделавших одинаковое число ошибок.

Задача 3.

Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.

Задача 4.

Так как перевезено всего 10m + 1 футболистов, то, рассадив их по клеткам-командам, получаем, что в какой-то клетке сидит 11 футболистов.

Задача 5.

Если бы каждый из рабочих мог купить магнитофон, то у них в сумме было бы не менее 5 • 320 = 1600 рублей.

Задача 6.

Эти суммы могут принимать лишь 7 разных значений: от – 3 до 3.

Контактная информация.

Создатели: Волков Владислав, Огурлиев Анзор

Контактные телефоны:8-920-024-29-26, 258-18-34

Наши сайты: http://vk.com/id155195626, http://vk.com/id136239566

Принцип Дирихле.

Лицей №180

2013-2014г.

г. Нижний Новгород

Причина выбора темы

Мы решили выбрать эту тему потому что задачи на принцип Дирихле встречаются на школьных, районных, и городских олимпиадах. Эта тема очень познавательна, потому что принцип Дирихле встречает во многих задачах. К тому же эта тема развивает логику, потому что в задачах на принцип Дирихле нужно проявлять логическое мышление. Их решать всегда очень интересно. Поэтому мы выбрали эту тему.

Теория

Утверждение «среди любых трех целых чисел найдутся два числа одной четности» кажется очевидным, также как и утверждение «среди 13 человек найдутся двое, родившиеся в один месяц». И то, и другое можно обосновать разбором случаев. Но более грамотным будет построить рассуждение от противного. Для второго утверждения это будет выглядеть так:«Предположим, что не найдется двух таких человек. Тогда в

каждый из 12 месяцев родилось не более одного человека. Значит, имеется всего не более 12 человек, что противоречит условию задачи: 12 < 13.»

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

Задачи на принцип Дирихле

1) Каждый из 10 участников форума послал по его окончании поздравительные открытки пятерым другим участникам. Докажите, что какие-то двое послали открытки друг другу. Ответ: Всего было отправлено 50 открыток. Значит, существует участник, который получил не менее пяти открыток (если бы каждый получил не более четырёх, то всего было бы отправлено не более 40 открыток). Таким образом, он послал открытки пятерым участникам форума и получил открытки не менее чем от пяти участников. Поскольку, кроме него, имеется лишь 9 участников, то хотя бы один другой участник входит в обе пятёрки.

2)В ящике лежат носки: 10 чёрных, 10 синих, 10 белых. Какое наименьшее количество носков надо вынуть не глядя, чтобы среди вынутых оказалось два носка одного цвета; Ответ: 4 носка. Допустим что 1 носок мы

достали белого цвета 2 носок черного а 3 носок синий, то получается что если мы достанем следующий носок он совпадёт с одним из предыдущих носков.

3)Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной из них был угадан хоть один номер?

Ответ:8 карточек. Можно будет закрыть 48 карточек и останется только 1 следовательно можно будет угадать как минимум 5 чисел.

4)В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта. Решение.25 ящиков- «кроликов» рассадим по 3 «клеткам»-сортам. Так как 25 = 3 * 8 + 1, то применим обобщенный принцип Дирихле (для N=3, k=8) и получим, что в какой-то «клетке»-сорте не менее 9 ящиков.

5) В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

Решение. Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 «клетка» с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в «клетку» с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем «клеток», то в какой-то «клетке» сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной «клетке», то количество иголок у них одинаково. 6)Несколько футбольных команд проводят турнир в один круг. Докажите, что в любой момент турнира найдутся две команды, сыгравшие к этому моменту одинаковое число матчей.

Решение: Пусть всего n шахматистов. Тогда каждый мог сыграть от 0 до n – 1 партий: всего n вариантов. Казалось бы, что принцип

Дирихле не работает: у нас имеется n различных шахматистов и n различных количеств сыгранных партий.

Заметим, однако, что если какой-то шахматист не сыграл ни одной партии, то не найдется шахматиста, сыгравшего все партии. То есть не может быть ситуации, когда есть игрок, сыгравший 0 партий, и игрок, сыгравший n – 1 партию. Значит, различных количеств сыгранных партий в любой момент турнира может быть не более n – 1 (от 0 до n – 2 или от 1 до n – 1). По принципу Дирихле в любой момент турнира найдется два игрока, сыгравших одинаковое количество партий.