Задача 1:

Существуют ли три квадратных трёхчлена, такие что каждый из них имеет два различных действительных корня, а сумма любых двух трёхчленов не имеет действительных корней?

(А. Канель)

Решение: =1

Ответ: да, существуют. Например, таковыми являются многочлены (x – 10)² – 1, x² – 1 и (x + 10)² – 1.

Задача 2:

Дана геометрическая прогрессия. Известно, что её первый, десятый и тридцатый члены являются натуральными числами. Верно ли, что её двадцатый член также является натуральным числом?

(Фольклор)

Решение: =2

Ответ: да, верно. Пусть a₁, a₂, …, a_n, … – данная геометрическая прогрессия, q – её знаменатель. По условию a₁, a₁₀ = a₁q⁹ и a₃₀ = a₁q₂₉ – натуральные числа. Поэтому q⁹ и q²⁹ – положительные рациональные числа. Отсюда следует, что  – положительное рациональное число и  – также положительное рациональное число.

Пусть , где m и n – натуральные взаимно простые числа. Число натуральное, m²⁹ и n²⁹ взаимно просты, следовательно, a₁ делится на n²⁹. Отсюда получаем, что  – число натуральное.

Задача 3:

В треугольнике ABC точка I – центр вписанной окружности, I′ – центр окружности, касающейся стороны AB и продолжений сторон CB и CA; L и L′ – точки, в которых сторона AB касается этих окружностей. Докажите, что прямые IL′, I′L и высота CH треугольника ABC пересекаются в одной точке.

(А. Заславский)

Решение: =3

Обозначим через M точку вписанной окружности, диаметрально противоположную точке L, через M′ – точку вневписанной окружности, диаметрально противоположную точке L′ (рис.). Таким образом, ML и M′L′ – диаметры, соответственно, вписанной и вневписанной окружностей, они параллельны высоте CH треугольника ABC. Вписанная окружность переходит во вневписанную при гомотетии с центром в точке C. При этой гомотетии диаметр ML переходит в параллельный ему диаметр, т.е. M′L′. Поэтому точки C, M, L′ лежат на одной прямой, а также точки C, M′, L лежат на одной прямой. Отсюда следует, что треугольники L′LM и L′HC совмещаются гомотетией с центром в точке L′. Поскольку L′I – медиана треугольника L′LM, прямая L′I пересекает отрезок CH в его середине.

Далее, треугольники LL′M′ и LHC совмещаются гомотетией с центром в точке L. Поскольку LI′ является медианой в треугольнике LL′M′, прямая LI′ также пересекает отрезок CH в его середине, откуда следует утверждение задачи.

Задача 4:

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

(А. Канель)

Решение: =4

Предположим, что такой многочлен Q(x) существует. Пусть Q(x) = a_nxⁿ + a_n – 1x^n – 1 +  …  + a₁x + a₀, где a₀, a₁, , a_n – целые неотрицательные числа, a_n не равно 0, n > 2.

Если a₀ = 0, то Q(x) = x(a_nx^n – 1 + a_n – 1x^n – 2 +  …  + a₁), следовательно, при простом p число Q(p) делится на p и больше p (здесь используется то, что степень Q не меньше 2), поэтому Q(p) – число составное. Допустим, a₀ ≥ 2. Обозначим через p некоторый простой делитель a₀. Тогда Q(p) = (a_np^n – 1 + a_n – 1p^n – 2 +  …  + a₁)p + a₀ делится на p и больше p, значит, Q(p) – число составное. Таким образом, имеется единственная возможность: a₀ = 1.

Если для любого простого p число Q(p) простое, то и число Q(Q(p)) является простым при любом простом p. Значит, свободный член многочлена Q(Q(x)) должен равняться 1. Однако, поскольку Q(0) = a₀ = 1, Q(Q(0)) = aⁿ + a^n – 1 +  …  + a₁ + 1 > 1. Мы получили противоречие, завершающее доказательство.

Задача 5:

Докажите, что в пространстве существует расположение 2001 выпуклого многогранника, такое что никакие три из многогранников не имеют общих точек, а любые два касаются друг друга (т. е. имеют хотя бы одну граничную точку, но не имеют общих внутренних точек).

(А. Канель)

Решение: =5

Положим N = 2001 и опишем построение расположения N выпуклых многогранников, из которых никакие три не пересекаются и любые два касаются.

Рассмотрим бесконечный круговой конус, вершина O которого находится в начале координат, а ось направлена вдоль оси Oz. На окружности, являющейся сечением конуса плоскостью z = 1, возьмём точки A₁, A₂, , A_N – вершины правильного N-угольника. Обозначим через B₁, B₂, , BN середины меньших дуг A₁A₂, A₂A₃, …, A_NA₁ соответственно. Через C(t) обозначим круг, являющийся сечением конуса плоскостью z = t, через O^t – центр этого круга, через ,  – точки пересечения образующих OA_i, OB_i с кругом C(t), где t > 0, 1 < i < N.

Докажем вспомогательное утверждение.

Лемма. Пусть выпуклый многоугольник M лежит внутри круга C(t₀), t₀ > 0. Рассмотрим бесконечную вверх «призму» P, основанием которой служит многоугольник M, а боковое «ребро» параллельно прямой OB_i для некоторого i. Многоугольник (равный M), который получается при пересечении призмы P и круга C(t), обозначим M(t) (таким образом, M(t₀) совпадает с M). Тогда найдётся такое положительное T > t₀, что при всех t > T многоугольник M(t) будет содержаться внутри сегмента круга C(t).

Доказательство. Многоугольник M(t) является образом M при параллельном переносе на вектор, параллельный образующей OB_i. Поэтому многоугольник M(t) содержится внутри круга, равного кругу C(t₀), который касается круга C(t) в точке . Расстояние от точки до прямой прямо пропорционально длине образующей OBt_i; следовательно, найдется такое T, что при всех t > T это расстояние больше диаметра окружности C(t₀). Это и означает, что многоугольник M(t) попадает внутрь сегмента S_i(t) круга C(t). Лемма доказана.

Переходим к индуктивному построению нашего расположения.

Выберем t₁ > 0. Возьмём выпуклый многоугольник M₁ внутри круга C(t₁). Рассмотрим бесконечную вверх «призму» P + 1, основанием которой служит многоугольник M₁, а боковое «ребро» параллельно прямой OB₁.

Пусть для некоторого n (1 < n < N) уже определены положительные числа t₁, t₂, …, tn – 1, t₁ < t₂ <  …  < t_n – 1, выпуклые многоугольники M₁, …, M_n – 1, лежащие внутри кругов C(t₁), C(t₂), …, C(t_n – 1), бесконечные «призмы» P₁, P₂, …, P_n – 1 с основаниями M₁, M₂, …, M_n – 1 и боковыми «рёбрами», параллельными OB₁, OB₂, …, OB_n – 1 соответственно.

Согласно лемме, существует число t_n > t_n – 1, такое что многоугольник M₁(t_n) содержится внутри сегмента S₁(t_n) круга C(t_n), многоугольник M₂(t_n) содержится внутри сегмента S₂(t_n) круга C(t_n), …, многоугольник M_n – 1(t_n) содержится внутри сегмента S_n – 1(t_n) круга C(t_n).

Сдвигаем каждую из прямых (1 < i < n – 1) в направлении вектора , пока она не совпадёт с прямой l_i(t_n), касающейся многоугольника M_i(t_n). Теперь построим выпуклый многоугольник M_n, который содержится в круге C(t_n), касается каждого многоугольника M_i(t_n) и лежит по разные с ним стороны от прямой l_i(t_n): возьмём для каждого i одну из точек касания многоугольника M_i(t_n) и прямой l_i(t_n); при n > 3 эти точки являются вершинами выпуклого (n – 1)-угольника, который и можно выбрать в качестве M_n; при n = 2,3 надо добавить ещё несколько точек).

Рассмотрим бесконечную вверх «призму» P_n, основанием которой является многоугольник M_n, а боковое «ребро» параллельно прямой OB_n. Построение будет закончено, когда мы получим призмы P₁, P₂, …, P_N. Наконец, «срежем» призмы плоскостью z = T, где T > t_N.

Докажем, что полученные (обычные) призмы удовлетворяют условию задачи. Для этого достаточно показать, что призма P_n пересекается с призмой P_i, i < n, только в плоскости круга C(t_n). Пусть, напротив, найдётся общая точка R ∈ C(t) двух призм, где t > t_n. Через точку R проведём прямые, параллельные OB_n и OB_i; обозначим их точки пересечения с плоскостью круга C(t_n) через R_n и R_i соответственно. Тогда точка R_n должна принадлежать многоугольнику M_n(t_n), а точка R_i должна принадлежать многоугольнику M_i(t_n). Ясно, что (ненулевые) векторы R_iR_n и противоположно направлены.

Однако это невозможно, поскольку точки R_i и B^tni лежат по одну сторону от прямой l_i(t_n), а точки R_n и  – по другую. Противоречие завершает доказательство.

Задача 6:

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

а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.

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

(В. Гуровиц)

Решение: =6

а) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в неё все собранные шарики и объявим её отмеченной. (Фактически мы дали описание операции, обратной к ходу, описанному в условии задачи.) Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое – стрелкой, соединяющей соответствующие точки (т. е. построить граф состояний системы), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнём двигаться по стрелкам, начиная с заданного состояния A₁. Получаем последовательность состояний A₂, A₃ …Поскольку число состояний конечно, в некоторый момент в последовательности A_i возникнет повторение. Пусть, например, A_k = A_n, где k < n. Поскольку в точку A_k входит ровно одна стрелка, из равенства A_k = A_n следует A_k – 1 = A_n – 1, ..., A₁ = A_{k – n + 1}. Тем самым, через n – k ходов мы вернулись в состояние A₁.

б) В отличие от задачи а) теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам. В каждый момент возможно несколько ходов, а именно столько, сколько в данный момент имеется непустых коробочек. Очевидно, имеется столько же возможностей выполнить обратную операцию, описанную в решении пункта а). В терминах графа состояний системы это означает, что из каждой точки выходит столько же стрелок, сколько в неё входит.

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

1) При любом начальном состоянии можно добиться того, чтобы все шарики оказались в одной наперёд заданной коробочке M.

В самом деле, если при каждой операции брать шарики из непустой коробочки, ближайшей к M при движении против часовой стрелки, то либо число шариков в M увеличится, либо ближайшая к M непустая коробочка станет ещё ближе, что не может продолжаться бесконечно. Утверждение доказано.

Обозначим через K состояние, при котором все шарики собраны в коробочке M, и через B некоторое произвольное состояние.

2) Из B можно пройти в K, двигаясь по стрелкам против их направления (по обратным стрелкам).

Действительно, согласно предыдущему утверждению, найдётся такая последовательность (различных) состояний B = A₁,A₂, … ,A_n = K, что точки A₁, A₂, …, A_n последовательно соединены стрелками. Будем двигаться по обратным стрелкам из A_n в A_n – 1, из A_n – 1 в A_n – 2, …, из A₂ в A₁ и далее из A₁, пока это возможно, выбирая на каждом шаге обратную стрелку, по которой мы ещё не проходили. Остановиться мы можем только в K. В самом деле, предположим, что при движении мы стираем стрелки. Cначала в каждую точку входило столько же стрелок, сколько выходило из неё. При стирании стрелок в каждый момент времени в каждую точку, за исключением начальной точки K, входит не меньше стрелок, чем выходит. Следовательно, если мы вошли в некоторую точку (кроме K) по обратной стрелке, то мы сможем и выйти из неё. Отсюда следует, что из B можно пройти в K по обратным стрелкам, т.е. из K можно пройти в B по обычным стрелкам.

Теперь нетрудно завершить доказательство. Пусть имеются два произвольных состояния A и B. Чтобы пройти, двигаясь по стрелкам, из A в B, можно вначале пройти из A в K, а затем из K в B. Как мы доказали, и то и другое возможно.