Принцип Дирихле
Немного теории
Этот принцип достаточно прост и очевиден, иногда им пользуются из соображений логики, даже не зная его формулировки. Но, зная этот принцип, легче догадаться в каких случаях его применять. Проще всего принцип Дирихле выражается в такой шуточной форме: «Если в n клетках больше чем n+1 зайцев, то хотя бы в одной клетке сидят не меньше двух зайцев».
А теперь так: «Если множество, состоящее из nk+1 элементов, разбить на k подмножеств, то хотя бы в одном подмножестве найдётся не менее чем n+1 элементов».
Доказательство принципа Дирихле можно провести, применив метод от противного. Приведем еще несколько похожих на принцип Дирихле (и столь же очевидных) утверждений, используемых в геометрических и аналитических задачах:
а) если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S;
б) если на отрезке длины 1 расположено несколько отрезков с суммой длин L, то найдется точка, покрытая не более чем [L] этими отрезками;
в) если тело с объёмом V разбили на n частей (которые не имеют общих внутренних точек), то объём наибольшей части не меньше V/n, а объём наименьшей – не больше V/n;
г) если среднее арифметическое нескольких чисел больше А, то хотя бы одно из этих чисел больше А.
Задачи с решениями
1. Доказать, что среди 101 целого числа всегда можно выбрать два таких, что их разность делится на 100.
Отметим сразу, что при делении на 100 возможны 100 остатков: 0, 1, 2, ... , 99. Среди 101 остатка, которые мы получим после деления данных 101 числа на 100, по крайней мере, два одинаковых. Разность этих двух чисел при делении на 100 имеет остаток 0, а значит делится на 100.
2. В розыгрыше первенства по футболу участвуют 30 команд. Каждые две команды должны сыграть между собой один матч. Доказать, что в любой момент состязаний имеются две команды, сыгравшие к этому моменту одинаковое число матчей.
Воспользуемся методом от противного. Предположим, что к некоторому моменту времени все команды сыграли разное число матчей. Количество матчей, сыгранных некоторой командой, может принимать одно из 30 значений: 0, 1, 2, ... , 29. Все эти значения разные, поэтому, согласно предположению, все они должны встретиться. Но этого не может быть, потому что тогда есть команда, которая не сыграла ни одного матча, и есть команда, сыгравшая со всеми остальными командами. Предположение не верно. Доказательство окончено.
3. Задача Рамсея. Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
Выберем одного произвольного человека из шести. Среди оставшихся пяти обязательно найдутся либо трое (как минимум) знакомых с ним, либо трое (как минимум) незнакомых с выбранным. Разберем, например, первый случай. Среди этих троих людей либо найдутся двое знакомых – тогда они вместе с выбранным нами человеком образуют нужную тройку, либо они все трое попарно незнакомы. Другой случай разбирается аналогично.
4. Имеется n целых чисел. Доказать, что среди них найдутся несколько (или, быть может, одно), сумма которых делится на n.
Пусть а1, а2, …, аn – данные числа. Рассмотрим n сумм:
а1,
а1 + а2,
а1 + а2 + а3,
…
а1 + а2 + а3 + … + аn.
Либо одна из этих сумм делится на n и значит является искомой, либо ни одна не делится на n. Во втором случае найдутся две суммы с одинаковым остатком, ведь сумм n, а ненулевых остатков только n–1. Разность этих сумм
(а1 + а2 + а3 + … + аk + ak+1 + ... +am) – (а1 + а2 + а3 + … + аk) = ak+1 + ... +am
– тоже сумма и делится на n.
5. Ежедневно на протяжении года ученик решал не менее одной задачи, причём еженедельно он решал не более 12 задач. Доказать, что найдётся несколько последовательных дней, за которые он решил ровно 20 задач.
Будем считать, что год имеет ровно 52 недели. Введём обозначения:
a1 – количество задач, решённых за один первый день;
a2 – количество задач, решённых за два первых дня;
a3 – количество задач, решённых с первого по третий день;
…
a364 – количество задач, решённых за год, т.е. 52 недели.
Понятно, что все числа a1, a2, a3, … , a364 различны, и каждое не превосходит максимально возможного числа задач, решённых учеником за год, которое равно 12·52=624. Рассмотрим ещё 364 числа: a1+20, a2+20, a3+20, … , a364+20. Среди этих чисел нет ни одной пары равных, и каждое из них не превосходит 624+20=644.
Итак, среди 728 целых положительных чисел a1, a2, a3, … , a364, a1+20, … , a364+20, каждое из которых не превосходит 644, найдётся пара равных. Пусть ak=ai+20, тогда ak–ai=20. А это и означает, что с (i+1)-го по k-й день ученик решил ровно 20 задач.
Замечание 1. На протяжении года было 84 таких промежутков времени, когда ученик решал по 84 задачи.
Замечание 2. В данной задаче достаточно ограничится промежутком времени гораздо меньшим, чем год. Можно показать, например, что на протяжении 77 дней тоже найдётся несколько последовательных дней за которые было решено ровно 20 задач.
6. Каждая из девяти прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2:3. Докажите, что, по крайней мере, три из этих прямых проходят через одну точку.
Каждая прямая, разбивающая квадрат на два четырёхугольника, (либо две трапеции, либо два прямоугольника) с отношением площадей 2:3, в таком же отношении делит среднюю линию квадрата. Докажем это. Пусть дан квадрат АВСD (рис. 1).
Его пересекает прямая МN. Пусть РQ – средняя линия квадрата (Р – середина АВ, Q – середина СD) и К – точка пересечения РQ и МN. Площади трапеций АВМN и MNDС равны соответственно АВ·РК/2 и АВ·КQ/2. Поэтому если они относятся как 2:3, то и РК:КQ = 2:3.
Таких точек, которые делят средние линии квадрата в отношении 2:3, всего четыре (рис. 2), а прямых – девять. Согласно принципу Дирихле найдется точка, через которую проходят, по крайней мере, три прямые, что и требовалось доказать.
7. «Король-самоубийца». На шахматной доске размером 1000 на 1000 стоит чёрный король и 499 белых ладей. Докажите, что при произвольном первоначальном расположении фигур король может стать под удар белой ладьи, как бы не играли белые.
Пошлём короля сначала в левый нижний угол доски и затем по диагонали вправо вверх. Можно считать, что после первого хода короля по диагонали и ответа белых три нижние горизонтали и три левые вертикали свободны от белых ладей, иначе либо король уже под ударом ладьи, либо следующим ходом сможет стать под удар (рис. 1; конкретная расстановка видимых ладей на обоих рисунках условна). Таким образом, все ладьи находятся выше и правее короля.
Рассмотрим момент, когда король сделал ещё 997 ходов по диагонали, оказавшись на предпоследней её клетке, и белые ответили на его последний ход (рис. 2). В этот момент все ладьи должны быть левее и ниже короля. При этом каждая ладья должна была сделать два хода: поменять вертикаль и стать слева от короля, и поменять горизонталь, опустившись ниже короля. Для этого белым понадобиться 499·2=998 ходов. Так как белые уже сделали ход, то осуществить 998-й ход они не успеют и, следующим ходом чёрный король сможет стать под удар, даже если раньше это ему не удавалось.
8. Каждая точка плоскости окрашена в один из двух цветов. Доказать:
а) на этой плоскости существует равнобедренный треугольник, все три вершины которого окрашены в один и тот же цвет;
б) на этой плоскости существует равносторонний треугольник, все три вершины которого окрашены в один и тот же цвет;
в) на этой плоскости найдётся треугольник с углами 30°, 60°, 90° и гипотенузой n, вершины которого окрашены в один и тот же цвет.
а) Рассмотрим пять точек, расположенных в вершинах правильного пятиугольника.
Среди них, согласно принципу Дирихле, есть, как минимум, три точки одинакового цвета. Поскольку расстояния между этими тремя точками принимают лишь два значения (длина стороны и длина диагонали пятиугольника), то одно из них, опять же по принципу Дирихле, встречается дважды, и треугольник с вершинами в этих точках – равнобедренный.
б) Для доказательства можно использовать, например, девять точек, которые расположены так, как показано на рисунке ниже (точки расположены в вершинах восьми равных равносторонних треугольников) и провести рассуждения аналогичные тем, которые были приведены в задаче а).
в) Сначала найдём две одноцветные точки, расстояние между которым n. Для этого достаточно рассмотреть равносторонний треугольник со стороной n. По крайней мере, две его вершины окрашены в один цвет. Пусть они красные, обозначим их А и В. Построим правильный шестиугольник AKLBMN.
Если из точек K, L, M, N хоть одна красная, то А, В и эта точка являются вершинами искомого треугольника. Если же K, L, M, N синие, то искомым является, например, треугольник KLM.
9. Пусть у выпуклого 24-угольника все стороны и диагонали окрашены либо в красный, либо в синий цвет. Можно ли выбрать 4 вершины так, чтобы все стороны и диагонали образованного четырехугольника имели одинаковый цвет?
Докажем, что это возможно. Соединим некоторую вершину данного многоугольника с другими его вершинами. Таких отрезков 23. Согласно принципу Дирихле, среди них можно выбрать 12 отрезков одного цвета. Обозначим эти 12 отрезков: А1А13, А2А13, А3А13, ... , А12А13 и будем считать их, например, красными.
Из точки А1 к точкам А2, А3, ... , А12 можно провести 11 отрезков, из которых не менее 6 одного цвета. Пусть шестеркой отрезков одного цвета будут отрезки А1А2, А1А3, А1А4, А1А5, А1А6, А1А7. Эти отрезки изображены крупным пунктиром.
Из точки А2 к точкам А3, А4, ... , А7 можно провести 5 отрезков, из которых не менее 3 одного цвета. Пусть тройкой отрезков одного цвета будут отрезки А2А3, А2А4, А2А5. Эти отрезки изображены мелким пунктиром.
Возможные варианты:
1) крупный и мелкий пунктиры красные;
2) крупный пунктир красный, мелкий – синий;
3) мелкий пунктир красный, крупный – синий;
4) крупный и мелкий пунктиры синие.
Рассмотрим каждый из случаев.
Случай 1. А1А2А3А13, например, – красный четырехугольник, т.е. такой, все стороны и диагонали которого окрашены в красный цвет.
Случай 2. Если какой-то из отрезков А4А5, А5А6, А6А7, А4А6, А5А7, А4А7 красный, то четырехугольник, имеющий противоположными сторонами этот отрезок и отрезок А1А13, является красным. Если же все эти шесть отрезков синие, то синий – четырехугольник А4А5А6А7.
Случай 3. Если какой-то из отрезков А3А4, А4А5, А3А5 является красным, то четырехугольник, имеющий противоположными сторонами этот отрезок и отрезок А2А13, является красным. Если же все эти три отрезка синие, то синим является четырехугольник А1А3А4А5.
Случай 4. Если какой-то из отрезков А3А4, А4А5, А3А5 является синим, то четырехугольник, имеющий противоположными сторонами этот отрезок и отрезок А1А2, является синим. Если же три названные отрезки красные, то четырехугольник А3А4А5А13 – красный.
Доказательство окончено.
10. Ограниченная плоская фигура имеет площадь S > 1. Докажите, что её можно “перенести” на вектор с целыми коэффициентами так, чтобы начальная фигура и образ пересекались.
Пусть данная фигура F содержится в квадрате со стороной d. Выберем систему координат так, чтобы точка О(0;0) была внутренней точкой данной фигуры. При произвольном натуральном k рассмотрим все возможные образы фигуры F при параллельных переносах на вектор a(m;n), где m,n – натуральные и принадлежат отрезку [0;k].
Очевидно, что каждый из таких образов расположен внутри квадрата Q, каждая точка которого имеет координаты (хQ;уQ) и при этом хQ и уQ – числа из отрезка [–d;k+d].
Допустим, что никакие два образа не пересекаются. Тогда их общая площадь не превышает площади квадрата Q, то есть (k+1)2S–(k+2d)2 – неположительное число, или (S–1)k2+2(S–2d)k+S–4d2 – не больше нуля.
Но вследствие условия S–1 > 0 и свойств квадратичной функции это невозможно при достаточно больших k. Значит некоторые два образа F1и F2, которые получаются при параллельном переносе фигуры F на векторы а1 и а2, соответственно, пересекаются. Очевидно, что параллельный перенос на вектор а = а1 – а2 отображает фигуру F1 в фигуру F2.
Задачи без решений
11. Группа людей состоит из 40 человек. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 человека из этой группы?
12. Дано n+1 различных натуральных чисел, меньших 2n. Доказать, что из них можно выбрать три таких числа, что одно из них равно сумме двух других.
13. Можно ли найти такой натуральный показатель степени числа 3, чтобы значение этой степени оканчивалось на 0001?
14. Каждая сторона и диагональ выпуклого 17-угольника окрашена в один из трёх цветов. Докажите, что всегда можно выбрать три вершины так, что получившийся треугольник будет иметь стороны одного цвета.
15. В пространстве расположено n точек так, что любые четыре из них являются вершинами тетраэдра с объёмом не большим k. Докажите, что все эти точки можно заключить в некоторый тетраэдр, объём которого равен 5k.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутка друзей вк