M610. Об «интересных» наборах чисел

Задачa из журнала «Квант» (1980 год, 2 выпуск)

Условие

Фиксируем $k \in \mathbb N$.
$а)$ Рассмотрим множество всех наборов целых чисел $a_1, \ldots , a_k$ таких, что $0 \le a_1 \le a_2 \le \ldots \le a_k \le k$; обозначим число таких наборов через $N.$ Рассмотрим среди них те, для которых $a_k = k$; пусть их число равно $M$. Докажите, что $N=2M$.
$б)$ Наложим на рассматриваемые наборы дополнительное ограничение: сумма $a_1 + \ldots + a_k$ делится на $k$. Пусть соответствующие числа равны $N’$ и $M’$. Докажите, что $N’ = 2M’$ (Из рисунка 1 видно, что при $k=3$ эти числа равны $M=10$, $N=20$; $M’=4$, $N’=8$.)

Рис. 1.

Решение

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

Нам нужно доказать, что наборов, в которых $a_k = k$ ровно половина. Поэтому попробуем установить взаимно однозначное соответствие между этими наборами и оставшимися, теми, у которых $a_k < k$.

Сопоставить набору $(a_1, a_2, \ldots, a_k)$ набор $(a_k, a_{k-1}, \ldots, a_1)$ нельзя, так как новый набор — невозрастающий. Можно попробовать сопоставить набору $(a_1, \ldots, a_k)$ набор $k-a_k, k-a_{k-1}, \ldots, k-a_1)$: он уже — неубывающий, но… $k-a_1$ не обязательно быть меньше $k$. Поэтому это соответствие не решает задачу.

Значит, необходимо более сложное соответствие. Для его построения нам понадобится понятие диаграммы Юнга данного набора.

Рис. 2

Что это такое, проще всего объяснить на примере: набору $(0, 0, 2, 3, 5)$ соответствует диаграмма, изображенная на рисунке 2 — в каждой строке столько соответствующее число.

Дополним диаграмму Юнга до квадрата (рис. 3). Тогда становится ясно, что наша первоначальная идея заключалась в том, что отсчитывать диаграмму не из красных, а из белых квадратиков (и, соответственно, не слева-снизу, а справа-сверху).

Рис. 3

Попытаемся теперь дополнить рисунок 3 вертикальной диаграммой — как на рисунке 4. Отсчитывая эту диаграмму снизу-слева, получим набор $(2, 2, 3, 4, 4)$. Назовем этот набор дополнительным к набору $(0, 0 , 2, 3, 5)$. Еще один пример изображен на рисунке 5.

Ясно, что если исходный набор $(a_1, \ldots, a_k)$, а дополнительный — $(b_1, \ldots, b_k)$, то $(a_k = k)$ тогда и только тогда, когда $b_k < k$. В самом деле, $a_k = k$, если верхняя правая клетка входит в основную диаграмму Юнга, и $a_k < k$, если она входит в дополнительную.

Рис. 4

Установленное нами соответствие между наборами, у которых $a_k = k$, и наборами, у которых $a_k < k$, очевидно, взаимно однозначно. Тем самым мы решили $a)$. Кроме того, сумма чисел исходного и дополнительного наборов равна $k^2$ (в наших примерах — 25). Поэтому сумма чисел дополнительного набора делится на $k$ тогда и только тогда, когда делится на $k$ сумма чисел исходного набора. Это решает $б)$.

Рис. 5

Замечание. Задача $a)$ имеет и другое решение: можно непосредственно посчитать числа $N$ и $M$. Именно:

Лемма. Число наборов целых чисел $a_1, \ldots, a_m$ таких, что $0 \le a_1 \le \ldots \le a_m \le k$ равно $C^m_{k+m}$.

Доказательство. Рассмотрим набор $(b_1, \ldots, b_m)$ где $b_i = a_i + i : b_1 = a_1 +1, b_2 = a_2 +2 $ и т. д. Тогда, очевидно, $1 < b_1 < b_2 < \ldots < b_m \le k+m$, то есть $(b_1, \ldots, b_m)$ — произвольный возрастающий набор $m$ целых чисел их первых $k+m$ чисел. Число таких наборов равно $C^m_{k-m}$.

Поэтому число наборов, в которых $a_k \le k$, по лемме равно $C^k_{2k}$. Если же $a_k = k$, то нам остается выбрать числа $a_1, \ldots, a_{k-1}$ так, что $0 \le a_1 \le \ldots \le a_{k-1} \le k$; их число равно $C^{k-1}_{2k-1}$. Остается посчитать, что $2C^{k-1}_{2k-1}$ равно $C^k_{2k}$.

А. Толпыго

M1231. О разбиении плоскости графиками многочленов второй степени

Условие

На какое наибольшее число частей могут разбить плоскость Oxy графики n квадратных трехчленов вида y=ax^{2}+bx+c (n=1, 2, 3, ...)?

Ответ: n^{2}+1.

Решение

Докажем по индукции, что число частей не превосходит n^{2}+1. Для n=1 это ясно: парабола делит плоскость на две части.
Пусть доказано, что n-1 графиков делят плоскость не более, чем на (n-1)^{2}+1 частей. Проведем последний, n-й график. Он пересекается с каждым из n-1 предыдущих максимум в двух точках, т.е. он будет разбит не более чем на 2(n-1)+1=2n+1 кусков (включая два крайних, уходящих в бесконечность). Каждый из этих кусков параболы делит одну из имеющихся частей плоскости на две. Таким образом, при проведении последней параболы число частей увеличится не более чем на 2n+1, т.е. не превзойдет (n-1)^{2}+1+2n+1=n^{2}+1.
К задаче M1231
Легко строится пример, когда все графики попарно пересекаются в двух точках (см. рисунок) — при этом получится максимальное число частей, указанное в ответе.
Точно такие же образом можно подсчитать максимальное число частей, на которые делят плоскость n прямых, n окружностей и т.п.

Н.Васильев

M1518. Высоты тетраэдра пересекаются в одной точке

Задачи из журнала «Квант» (1995 год, выпуск 5)

Условие

Высоты тетраэдра пересекаются в одной точке. Докажите, что эта точка — основание одной из высот и три точки, делящие другие высоты в отношении 2:1, считая от вершин, лежат на одной сфере.

Доказательство

Пусть M — точка пересечения медиан треугольника ABC, P— точка пересечения высот тетраэдра, AA_{1} — высота тетраэдра из вершины A.

MA_{2}||A_{3}A_{1} и AA_{2}:A_{2}A_{1}=2:1.

Угол MA_{2}P — прямой, так что точка A_{2} лежит на сфере с диаметром MP. Аналогично рассматриваются остальные случаи.

Д.Терешин

M1515. О целых корнях суперпозиции трех квадратных трехчленов

Задача из журнала «Квант» (1995 год, выпуск 5)

Условие

Известно, что f(x),g(x),h(x) — квадратные трехчлены. Может ли уравнение f(g(h(x)))=0 иметь корни 1, 2, 3, 4, 5, 6, 7 и 8?

Решение

Предположим, что числа 1, 2, 3, 4, 5, 6, 7 и 8 — корни уравнения f(g(h(x)))=0.

Если прямая x=a — ось параболы, задаваемой уравнением y=h(x), то h(x_{1})=h(x_{2}) тогда и только тогда, когда x_{1}+x_{2}=2a.

Многочлен f(g(x)) имеет не более четырех корней, но числа h(1), h(2),..., h(8) являются его корнями, следовательно, a=4.5 и h(4)=h(5),h(3)=h(6),h(2)=h(7),h(1)=h(8). Кроме того, мы попутно доказали, что числа h(1),h(2),h(3),h(4) образуют монотонную последовательность. Аналогично, рассматривая трехчлен f(x) и его корни g(h(1)), g(h(2)), g(h(3)), g(h(4)), получаем, что h(1)+h(4)=2b, h(2)+h(3)=2b, где прямая x=b — ось параболы, задаваемой уравнением y=g(x). Но из уравнения h(1)+h(4)=h(2)+h(3) для h(x)=Ax^{2}+Bx+C следует, что A=0. Противоречие.

Ответ: уравнение f(g(h(x)))=0 не может иметь корни 1, 2, 3, 4, 5, 6, 7 и 8.

С.Токарев

M1452. Общая касательная к касающимся внешним образом окружностям

Условие

Окружности S_1 и S_2 касаются внешним образом в точке F. Прямая l касается S_1 и S_2 в точках A и B соответственно. Прямая, параллельная прямой l, касается S_2 в точке C и пересекает S_1 в точках D и E. Докажите, что а) точки A, F и C лежат на одной прямой; б) общая хорда окружностей, описанных около треугольников ABC и BDE, проходит через точку F.

К задаче M1452

Решение а) Первое решение

Так как касательные к окружности S_2 в точках B и C параллельны, то BC — ее диаметр, и ∠BFC=90°. Докажем, что и ∠AFB=90°. Проведем через точку F общую касательную к окружностям, пусть она пересекает прямую l в точке K. Из равенства отрезков касательных, проведенных к окружности из одной точки, следует, что треугольники AKF и BKF равнобедренные. Следовательно,
∠AFB=∠AFK+∠KFB=∠FAB+∠FBA=180°/2=90°

Решение а) Второе решение

Рассмотрим гомотетию с центром F и коэффициентом, равным -r_2/r_1, где r_1 и r_2 — радиусы окружностей S_1 и S_2. При этой гомотении S_1 переходит в S_2, а прямая l — касательная к S_1 — переходит в S_2. Следовательно, точка A переходит в точку C, поэтому точка F лежит на отрезке AC.

Решение б)

Ниже мы покажем, что центр окружности BDE находится в точке A. Поскольку центр окружности ABC есть середина AC (∠ABC=90°), а ∠BFC=90° (см. первое решение п. а)), отсюда будет следовать, что BF есть перпендикуляр, опущенный из общей точки окружностей BDE и ABC на прямую, соединяющею их центры. А это и значит, что прямая BF содержит их общую хорду.

Итак, нам достаточно доказать, что AD=AE=AB. Первое из этих равенств очевидно(ибо касательная к S_1 в точке A параллельна DE). Пусть r_1 и r_2 — радиусы S_1 и S_2. Опуская перпендикуляр AP на DE, найдем, что AP=BC=2r_2, и по теореме Пифагора для треугольников APD и O_1PD, где O_1 — центр S_1 PD^2=O_1D^2-O_1P^2=r_1^2-(2r_2-r_1)^2=4r_1r_2-4r_2^2 AD^2=AP^2+PD^2=4r_1r_2

Но легко найти, что общая касательная AB окружностей S_1 и S_2 равна 2\sqrt{r_1r_2}.

А. Калинин, В. Дубровский