Задача 1: В шеренгу стоят 1995 новобранцев. По Уставу, в наряд на чистку сортира можно отправить либо каждого третьего, либо каждого четвертого (то есть, первого, четвертого, седьмого и т. д., либо первого, пятого, девятого и т. д.). Сформированный наряд сразу приступает к делу. Старшина собирается сформировать три наряда. Докажите, что по крайней мере один новобранец может быть уверен, что не попадет ни в один из нарядов.

(А.~Голованов; рис.~Т.~Кохась)

Решение: Проверьте, например, что 1728-й новобранец не попадет ни в один из нарядов (1728 = 12³).

Задача 2: a₁,a₂, … ,a_n – натуральные числа, N – их произведение. Известно, что N делится на квадрат каждого из чисел a₁, … ,a_n. Для каждой пары (i,j), i < j вычислили наибольший общий делитель чисел a_i и a_j; M – произведение всех этих наибольших общих делителей. Докажите, что M² делится на N.

(С.~Берлов, С.~Иванов)

Решение: Наибольший общий делитель чисел a_i и a_j будем, как обычно, обозначать (a_i,a_j). Условие задачи означает, что каждое a_i делит произведение . Это произведение будет делиться на a_i, даже если каждый множитель a_j заменить на (a_j,a_i). Действительно, отбрасываемые при этом части разложения a_j на простые сомножители не влияют на делимость на a_i (в число входят простые множители либо не входящие в a_i, либо такие, количество которых в разложении (a_j,a_i) уже равно количеству в разложении a_i). Таким образом, для каждого фиксированного i делится на a_i. Перемножая по всем i, получаем, что делится на .

Задача 3: Внутри параллелограмма ABCD выбрана точка O так, что  ∠ OAD =  ∠ OCD. Докажите, что  ∠ OBC =  ∠ ODC.

(С.~Берлов)

Решение: Эта задача имеет много решений. Мы приведем лишь некоторые.

Решение 1. Построим отрезок OE, равный по длине и параллельный отрезку AD. Тогда AOED – параллелограмм, следовательно,  ∠ OED =  ∠ OAD =  ∠ OCD, и четырехугольник OCED – вписанный. Значит,  ∠ ODC =  ∠ OEC, как опирающиеся на одну и ту же хорду. Но четырехугольник OBCE – тоже параллелограмм. Поэтому  ∠ OEC =  ∠ OBC, откуда и следует утверждение задачи.

Решение 2. Заметим, что  ∠ BAO =  ∠ BCO. Обозначим  ∠ OAD =  ∠ OED =  α ,  ∠ ODC =  β ,  ∠ OBC =  δ ,  ∠ ADC =  ∠ ABC =  γ . Тогда  ∠ ADO =  γ  –  β ,  ∠ ABO =  γ  –  δ . Напишем теоремы синусов для треугольников AOD и OED:

Отсюда . Аналогично из теорем синусов для треугольников AOB и BOC получаем, что . Значит, . Это равенство легко приводится к виду

 sin ( β  –  δ ) = 0. Значит,  β  =  δ .

Решение 3. Проведем через точку O прямые, параллельные сторонам параллелограмма. Пусть K, L, M, N – точки пересечения этих прямых со сторонами параллелограмма (см. рисунок). Прямые разбивают исходный параллелограмм на четыре параллелограмма, так что на полученной картинке образовалось много равных отрезков и углов. Заметим, что треугольники AON и COM подобны, поэтому . В треугольниках BLO и OMD  ∠ L =  ∠ M, и при этом . Значит, эти треугольники подобны, и  ∠ LBO =  ∠ ODM, что и требовалось доказать.

Задача 4: Шахматная фигура «пулеметчик» бьет в каком-то одном направлении по вертикали или горизонтали (например, по горизонтали влево) на любое число клеток. Какое наибольшее количество не бьющих друг друга пулеметчиков можно расставить на шахматной доске 20 × 20?

(А.~Пастор)

Решение: Ответ: 76 пулеметчиков. Пример расстановки: пулеметчики стоят по периметру доски и «стреляют наружу».

Докажем, что большее количество пулеметчиков расставить нельзя. Рассмотрим произвольную расстановку пулеметчиков, не бьющих друг друга. Внесем в нее следующие изменения: всех пулеметчиков, стоящих на краю доски, «развернем» так, чтобы они «стреляли» наружу; после этого каждого пулеметчика, стоящего не на краю доски, сдвинем на край в направлении его стрельбы. Ясно, что после этого пулеметчики будут стоять на разных клетках и не будут бить друг друга. Теперь все пулеметчики стоят на краю доски, значит, их не более 76.

Задача 5: f(x) – многочлен третьей степени. Докажите, что существует такое натуральное k, что многочлен f(x) + f(x + 1) +  …  + f(x + k) имеет ровно один вещественный корень.

(С.~Берлов, К.~Кохась)

Решение: Не умаляя общности, можно считать, что старший коэффициент многочлена положителен. Достаточно проверить, что существует k, для которого f′(x) + f′(x + 1) +  …  + f′(x + k) ≥ 0 при всех . Заметим, что f′(x) – это некоторый квадратный трехчлен с положительным коэффициентом при x². Если всех x, то утверждение задачи очевидно, поэтому будем считать, что f′ имеет два вещественных корня. Пусть s – расстояние между корнями этого трехчлена, m – модуль его наименьшего (отрицательного) значения, t – число настолько большое, что при |x| > t f′(x) > m(s + 1). В качестве k можно взять любое натуральное число, большее, чем 2t + s + 1. В самом деле, среди чисел x,x + 1, … ,x + k в этом случае отрицательных – не больше s + 1, следовательно, сумма отрицательных слагаемых в выражении f′(x) + f′(x + 1) +  …  + f′(x + k) по модулю не превосходит (s + 1)m. С другой стороны, хотя бы одно из чисел x,x + 1, … ,x + k по модулю больше t, поэтому сумма положительных слагаемых в выражении f′(x) + f′(x + 1) +  …  + f′(x + k) больше (s + 1)m. Это доказывает неравенство.

Задача 6: Вокруг остроугольного треугольника ABC описана окружность. Высоты треугольника из вершин A и C пересекают окружность в точках E и F соответственно, D – произвольная точка на (меньшей) дуге AC, K – точка пересечения DF и AB, L – точка пересечения DE и BC. Докажите, что прямая KL проходит через ортоцентр треугольника ABC.

(С.~Берлов)

Решение: Обозначим через H ортоцентр  ∆ ABC. Тогда  ∠ AHF =  ∠ EHC =  ∠ ABC – как углы между высотами треугольника,  ∠ AFC =  ∠ HEC =  ∠ ABC – как углы, опирающиеся на одну дугу. Значит, треугольники AFH и CHE равнобедренные (и подобные). Так как точки K и L лежат на высотах этих треугольников, то FK = KH и HL = LE, и, следовательно,  ∠ KFH =  ∠ KHF,  ∠ LEH =  ∠ LHE. Заметим еще, что  ∠ AFD =  ∠ AED как опирающиеся на одну дугу. Теперь осталось подвести итог всем нашим наблюдениям:  ∠ KHF =  ∠ AFC –  ∠ AFD =  ∠ EHC –  ∠ EHL =  ∠ LHC, т. е. углы FHK и LHC вертикальные. Значит, отрезки KH и HL лежат на одной прямой, что и требовалось доказать.

Задача 7: Докажите, что в любой компании, состоящей из четного числа людей, найдутся два человека, у которых в этой компании четное число общих знакомых.

(М.~Антипов)

Решение: Допустим, что это не так, т. е. любые два человека имеют нечетное число общих знакомых. Разобьем всех людей на три группы. В первую группу возьмем произвольного человека, пусть это будет Вася. Во вторую группу возьмем всех Васиных знакомых, в третью – всех, кто с Васей незнаком. Рассмотрим подробнее вторую группу. Каждый человек из второй группы имеет нечетное число общих знакомых с Васей, причем все эти знакомые, конечно, находятся тоже во второй группе. Таким образом, каждый человек из второй группы знает нечетное число людей из второй группы. Отсюда следует, что во второй группе четное число людей. Кстати, мы установили, что у Васи четное число знакомых, а поскольку Вася – произвольно взятый человек, то у каждого человека в этой компании четное число знакомых.

Рассмотрим теперь подробнее третью группу. Каждый человек из третьей группы имеет нечетное число общих знакомых с Васей, и, разумеется, все эти общие знакомые находятся во второй группе. Таким образом, каждый человек из третьей группы знаком с нечетным числом людей из второй группы (и незнаком с Васей). Поскольку у каждого человека четное число знакомых, мы можем заключить, что каждый человек из третьей группы знаком с нечетным числом людей из третьей группы. Значит, в третьей группе число людей тоже четно. Но тогда число людей во всех трех группах нечетно. Противоречие.