Правило «крайнего»

57

Если вы хотите научиться решать математические задачи, вам надо попытаться овладеть более или менее общими подходами, приемами и методами математических рассуждений. Расмотрим один весна общий подход, который мы будем назвать правилом «крайнего».

Правило «крайнего» может быть кратко выражено словами «Расмотите крайнее!». Это правило есть попросту рекомендация рассмотреть объект, обладающий какими-либо «крайними», или, как говорят математики, экстремальными свойствами. Если речь в задаче идет о множество точек на прямой, то правilo «Расмотри крайнее!» советует нам содействить свое внимание на самый крайней точке множество (самой левой или самой правой). Если в задаче фигурирует некоторый набор чисел, то правilo «крайнего» рекомендует рассмотреть наиболее или наиболее из этих чисел. Вот несколько примеров.

Задача 1. На плоскости задано некоморое множество точек М макое, что каждая точка из М является серединой отрезка, соединяющего какую-либо пару точки можно же множество М. Докажите, что множество М содержит бесконечную множество точки.

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

Задача 2. На прямой задано множество точек М макое, что каждая точка из М является серединой отрезка, соединяющего две другие точки М; значит, она не принадлежит М. Полученное противоречие и доказывает, что множество М не может быть конечным.

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

58

к нему нашей правило в форме: «Рассмотри наиболее!» — рассмотрим отрезок BC наиболее длины. Ясно, что вне отрезка BC нет точек из M, иначе существовали бы отрезки с большими длинами. Таким образом, все точки множества M лежат на отрезке BC и, значит, ни B, ни C не удовлетворяют условия, то есть не принадлежат множеству M. Противоречие.

Вернемся теперь к задаче 1. Допустим, что множество M конечно. Снова применим правило «крайнего». Для этого зафиксируем положение плоскости и рассмотрим самую leyую точку множества M, а если «самых левых» точек несколько, то возьмем самую нижнюю из них. Легко убедиться, что эта точка, обозначим ее через A, не может лежать внутри отрезка, соединяющего две точки множества M. Действительно, если бы такой отрезок существовал, то один из его концов находится бы либо левое A, либо на одной вертикали с точкой A, но ниже ее. Ни того, ни другого не может быть в силу выбора точки A.

Здесь, как и в задаче 2, тоже существует решение, основанное на рассмотрении попарных расстояний между точками множества M. Если множество M конечно, то и попарных расстояний конечное число, и среди них, руководствуясь правлением «крайнего», можно отыскать наиболее. Пусть это будет расстояние между точками A и B. Но точка B является серединой некоторого отрезка CD, концы которого по условию принадлежат множеству M (рис. 1). Тогда легко доказать, что либо |AD|, либо |AC| больше |AB| (сделайте это самострелно, воспользоваться тем, что медиана m, проведенная к одной из сторон треугольника, меньше полусуммы двух других сторон).

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

Решить эту задачу нам помогет правило «крайнего» в форме «Рассмотри наиболее!». Среди натуральных чисел, записанных на полях шахматной доски, непреемно существуют наименьшее. В этом нетрудно убедиться. Пусть k — одно из данных чисел. Если среди чисел, записанных на доске, имеется единица, то она и является таким наименьшим числом (не существует наименьшим числом, меньше единицы). Если единица на доске нет, посмотрим, нет ли там двойки. Если есть, то она и является наименьшим числом, если же нет, то попцем на доске тройку, и т. д. Не более чем за k шагов мы ответим таким образом наименьшее число m. Рассмотрим поле P, на котором оно записано. Обозначим числа, записанные на соседних полях, буквами a, b, c и d. По условию m=(a+b+c+d)/4. Отсюда a+b+c+d=4 m. В силу выбора числа m имеем a≥m, b≥m, c≥m, d≥m. Если хотя одно из этих неравенств было строго, то мы имеем a+b+c+d>4 m, что противоречит условия. Значит, a=b=c=d=m.

Таким образом, если на некотором поле записано число m, то и на соседних полях записано число m. Отсюда следует, что на горизонтали,

59

содержащей поле $P$, записаны один только числа $m$. Но любая вертикаль пересекает эту горизонталь, то есть она содержит число $m$, и, значит, все числа на вертикальных равны $m$. Значит, вообще все числа на доске равны $m$.

Задача 4. На квадратной шахматной доске размером $n \times n$ расстояний ладьи с соблюдением следующей условия: если некоторое поле свободно, то общее количество ладей, стоящих на одной с этим полем горизонтали и на одной с ним вертикали, не меньше $n$. Доказите, что на доске находится не менее $n^2/2$ ладей.

Эта задача — трудная. Однако умелое применение правила «крайнего» может существенно облегчить поиск решения. Именно, правило «крайнего» наталкивает на мысль расстоять ту из $2n$ линейдокки — вертикалей и горизонталей, — на котором стоит меньше всего ладей. Можно служить, что есть несколько таких линей, «одинаково нагруженных» ладями. Тогда выберем любую из них. Пусть эта линяя — горизонталь (в противном случае поверхем доску на $90^\circ$ — вертикали станут горизонтальными). Число ладей на этой горизонтали обозначает через $k$. Если $k \geq \frac{n}{2}$, то на каждой из $n$ горизонталей не менее $\frac{n}{2}$ ладей, а всего на доске не менее $\frac{n^2}{2}$ ладей.

Пусть теперь $k < \frac{n}{2}$. На расстоянии горизонтали $n-k$ свободных полей, и каждая вертикаль, проходящая также свободное поле, содержит как видно из условия, не менее $n-k$ ладей, а все такие вертикали — не менее $(n-k)^2$ ладей. Остальные $k$ вертикалей содержат не менее чем по $k$ ладей каждой (в силу выбора числа $k$). Всего на доске стоит не менее чем $(n-k)^2+k^2$ ладей. Остая доказать, что $(n-k)^2+k^2 \geq \frac{n^2}{2}$. Это можно сделать разными способами, вот один из них:

$$[(n-k)^2+k^2] - \frac{n^2}{2} = \frac{n^2}{2} - 2nk + 2k^2 = 2\left(\frac{n^2}{4} - nk + k^2\right) = 2\left(\frac{n}{2} - k\right)^2 \geq 0.$$

Если $n$ — число четное, то можно найти удовлетворяющую условию расстоявку, содержащую в точности $\frac{n^2}{2}$ ладей — достаточно поставить ладьи на все черные поля (или на все белые). Если число $n$ — нечетное, то $\frac{n^2}{2}$ ладей расставить, соблюдая условия задачи, нельзя, так как число $\frac{n^2}{2}$ нецелое, но $\frac{n^2+1}{2}$ ладей расставить можно: одну ладью ставим на одно из угловых полей, а остальные — на поля того же цвета.

Аналогично решается следующая задача.

Задача 5. Пусть $n^2$ неотрицательных чисел расположены в виде таблицы, содержащей $n$ строк и $n$ столбцов. При этом выполняно следующие условия: если на некотором месте таблицы записан нуль, то сумма чисел столбца и строки, содержащих этом нуль, не меньше $n$. Доказите, что сумма всех $n^2$ чисел не меньше $n^2/2$.

Задача 6. На плоскости заданы $n$ точки. Никакие при из них не лежат на одной прямой. Доказите, что существует окружность, проходящая через при данные точки, не содержащая внутренний поле или дынные точки.

Проведем окружность через каждой тройky точек. Получим неотрицательное окружность (неотрицательное из них могут слиться в одну). Требуется доказать, что хотя бы

60

одна из этих окружностей не содержит внутри себя ни одной из данных точек. Правило «крайнего» может навести на мысль рассмотрить наиболее окружность (окружность наиболее радиуса), но это в данном случае ничего не дает (достаточно рассмотрить конфигурацию из таких точек: 4 вершины квадрата и его центр; наименшей будет окружность, описанная около квадрата, а она условия не удовлетворяет). Поступим наче. Попробуем решить более простую задачу, а именно, будем искать окружность, проходящую через две из данных точек и не содержащую точку внутри себя. Измерим расстояния между каждой двумя данныхми точками и, воспользовавшись правилом «крайнего» в форме «Рассмотри наиболее вышее!», возьмем пару точек $A$ и $B$, находящихся на наиболее расстоянии друг от друга. Легко убедиться, что окружность, построенная на отрезке $AB$ как на диаметре, удовлетворяет условияю: остальные $(n-2)$ данные точки удалены и от $A$, и от $B$ не менее чем $|AB|$, а потому расположены вне этой окружности. Теперь проведем окружности через точки $A$ и $B$ и через каждой из остальных $(n-2)$ точек. Вот среди этих окружностей выберем наиболее вышее!, так нам подсказывает правил «Рассмотри наиболее вышее!». Пусть это будет окружность, проходящая через точки $A$ и $B$ и некоротую точку $C'$ «серпа» (рис. 2), меньше окружности, проходящей через точки $A$, $B$, $C$ (доказите это самостояльно).

Задача 7. На плоскости проведено $n$ прямых $(n \ge 3)$. Никакие две из них не паралельны, никакие при не пересекаются в одной точке. Эти прямые разрезают плоскость на части. Доказите, что какую бы из $n$ прямых мы ни взяли, хотя бы одна из прямыхающих к ней частей плоскости является преуедольником.

Пусть $l_1$ — одна из данных прямых. Руководствуясь правилом «крайнего», извес точек пересечения остальных прямых выберем ту, которая находится на наиболее вышеем расстоянии от прямой $l_1$. Пусть в этой точке, обозначим ее буквой $P$, пересекаются прямые $l_2$ и $l_3$. Нетрудно доказать (сделайте это самостояльно), что треугольник, образующий прямыми $l_1$, $l_2$ и $l_3$, составляет одну часть плоскости и, следовательно, удовлетворяет условияю.

Задача 8. Доказите, что не существует четырех намуральных чисел $x, y, z, u$, удовлетворяющих уравнению $x^2 + y^2 = 3(z^2 + u^2)$.

Допустим, что такие четырех существуют. Рассмотрим ту из них, для которой величины $x^2 + y^2$ минимальная (если есть несколько четырех, у которых эта величина одинакова и минимальная, расстоянием одну из них, любую). Пусть это будет четырех $a, b, c, d$. Из уравнения $a^2 + b^2 = 3(c^2 + d^2)$ видно, что $a^2 + b^2$ кратно trem. Но легко доказать, что $a^2 + b^2$ делится на три тогда и только тогда, когда $a$ и $b$ делятся на три, потому что квадрат числа, не делится на три, дает при делении на три в остатке единицу.

61

Следовательно, $a=3m, b=3n$, откуда
$$a^2+b^2=9m^2+9n^2=3(c^2+d^2).$$
Сокращая последнее равенство на 3, получим:
$$c^2+d^2=3(m^2+n^2).$$
Мы нашли четверку чисел $c, d, m, n$, удовлетворяющего данному уравнению, причем для этой четверки
$$c^2+d^2<a^2+b^2,$$
а это невозможно в силу выбора четверки $a, b, c, d$.

Задча 9. На плоскости расположены $n$ прямых ($n \ge 3$). Любые две прямые пересекаются и через какую точку пересечения проходят не менее трех из данных прямых. Доказите, что все прямые пересекаются в одной точке.

Пусть $M$ — одна из точек пересечения прямых. Допустим, что она — не единственная. Тогда найдется прямая $l$ данной системы, не проходящая через $M$. Множество точек пересечения прямых, не лежащих на $l$, непусто — оно содержит, например, точку $M$. Расмотите точку этого множества, близкойшую к $l$ (а если имеется несколько точек, находящихся на минимальном расстоянии от $l$, то выберите одну из них, любую), и получите противоречие.

Вот еще одна аналогичная задача.

Задча 10. На плоскости заданы $n$ точки ($n \ge 3$). Известно, что на всякой прямой, проходящей через 2 данные точки, расположена по крайней мере еще одна из данных точки. Доказите, что модель все $n$ точки лежат на одной прямой.

Развитием правил «крайнего» является «правило расположения», которое звучит так: «Расположите элементы исследуемого множества в порядке возрастания или в порядке убывания (или еще как-нибудь)!».

Задча 11. Семь грибников собрали вместе 100 грибов, причем ниже две не собрали одинаково числа грибов. Доказите, что есть трое грибников, собращих вместе не менее 50 грибов.

Составим «таблицу перевенства», помещив в ней грибников в порядке убывания числа собраных имги грибов. Ясно, что рассматривать надо грибников, занявших первые 3 места — они собрали грибов больше, чем любая другая тройка. Попробуем доказать, что они собрали не менее 50 грибов. Если грибник, занявший 3-е место, собрал 16 грибов или больше, то на 2-м месте — грибник, собращий не менее 17 грибов, а на первом — не менее 18 грибов. Вместе они собрали не менее 16+17+18=51 гриба. Если же грибник, занявший 3-е место, собрал не более 15 грибов, то грибники, занявшие места с 4-го по 7-е, собрали не более 14+13+12+11=50 грибов. На долю первой тройки и в этом случае остается не менее 50 грибов.