Решения задач М847—М850; Ф858—Ф861

45

Решения задач

M847—M850, Ф858—Ф861

М847. Квадрат расчерчен на n×n клеток. Двое церроков по очереди обводят по одному стороне одной клетки (дважды обводить одну и ту же сторону нельзя). Кто выдает при правильной церере, если
a) побеждает церрок, первый построящий замкнутую линию;
b) пройтивает церрок, который вынужден первым построить замкнутую линию.

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

Нам надо доказать, что при такой стратегии первого церрока. Допустим, что, напротив, после того, как он обведел неокоторую сторону a, впервые возник «почти-цикл», причем до цикла ему не достигнет одной стороны b; пусть x₁, …, xₙ — остальные стороны этого цикла. Эти стороны уже были обведены до последнего хода (a) второго церока, поэтому и симметричные им относительно диагонали сторон x’₁, …, x’ₙ, а также стороны a’, симметричная a, были обведены до этого хода. А так как x₁, …, xₙ и a образуют «почти-цикл», x’₁, …, x’ₙ и a’ тоже образуют «почти-цикл» (которому до цикла не достигнет стороны b’). Следовательно, «почти-цикл» возник последним ходом второго церока. Противоречие.

6. Ответ: при четном n выигравает второй церрок, при нечетном — первый; точнее, первый цикл обращаетсяровно через (n+1)² ходов (подразумевается, конечно, что церрок ходят правильно, то есть не замыкают цикл, пока это возможно).

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

1. любые два узла «игрового поля» в этой позиции можно соединить целочкой из обведенных сторон; другими словами, (разветвленная) ломана, составленная из всех обведенных сторон, проходит через все узлы и связна (из любой ее вершины можно пройти по ней в любую другую вершину);

2. любая связная ломана без циклов с k вершинами имеет k—1 звеньев.

Из этих утверждений вытекает, что в рассматриваемой позиции обведено (n+1)²—1 сторон, что нам и требуется.

Для доказательства первого утверждения возьмем любые два узла A и B и любую соединяющую обведенную сторона XY (см. рисунок). Если ее обведи, возникнет цикл. Очевидно, он должен содержать зено XY, поэтому узлы X и Y уже должны содержать «мостиком» из обведенных сторон. Заменив каждое необведенное зено церочки с таким «мостиком», мы получим ломанную из обведенных сторон, проходящую через A и B.

Перейдем к второму утверждению. Если ломана не содержит циклов, то у нее, оченьindo, имеется хотя бы одна вершина X, из которой выходит только одно зено XY. В силу связности, из точки Y выходит еще хотя бы одно зено. Удалим из ломанной зено XY; вместе с ним удаляется одна вершина — X, причем ломана остается связной. Поступая так же и дальше, мы в конце

46

М848. a) Построите график функции $f_0(x) = \|x-1\| - 2\|x\| - 3\|$.

б) На рисунке 1 изображены графики трех куссоно-линейных функций $f_1, f_2, f_3$. Запишите формулы для них в виде $y = kx + b + c_1|x - a_1| + \dots + c_m|x - a_m|$, где $k, b, c_i, a_i$ — некоторые числа, $m$ — количество точек излома графика ($a_i$ — абсциссы точек излома, $i=1, 2, \dots, m$).

в) Запишите в таком же виде функцию $f_0$ из пункта a)

e) * Некоторые функции являются комбинацией линейных функций, «модуля» и операции сложения, причем знак modular используется в ее записи $n$ раз (в примере a) $n=4$. Какое наиболее число изломов (при каждой n) может иметь ее график?

a) График функции $f_0$ изображен красным (рис. 2). Он является ломаной с конечным числом вершин — точек излома и двумя бесконечными крайными звеньями; функция с таким графиками называется куссоно-линейными. Хотя построение этого графика выполняет стандартно, мы останавемся на нем подробнее — это позволяет сделать несколько заменений, полезных при решении задачи г).

Пусть $f(x) = |x-1| - 2|x| - 3|$, тогда $f_0(x) = |f(x)|$, и потому график $f_0$ получается из графика $f$ (черная линия на рисунке 2) отражением его части, лежащей ниже оси абсцисс, относительно этой оси. Ясно, что это правило построения графика $|f|$ справедливо для любой функции $f$. В частности, из него следует, что:

1. если $m(f)$ — число изломов куссоно-линейной функции $f$, то

$$m(|f|) \leq 2m(f) + 1.$$

(Действительно, при переходе от $f$ к $|f|$ новые изломы появляются там, где график функции $f$ пересекает ось $Ox$, то есть не более чем по одному на каждой звенье, а число звеньев на 1 больше числа изломов $m(f)$.)

Далее, функция $f$ есть сумма функций $g(x) = |x-1|$ и $h(x) = -2|x| - 3|$, поэтому она может иметь изломы только там, где есть излом хотя у одного из слагаемых, то есть в точках, где обращаются в нуль выражения, стоящие под модель: $x-1$, $x$ или $|x|-3$; это точки $-3, 0, 1$ и $3$. Точно так же вообще

2. для любых куссоно-линейных функций $g$ и $h$

$$m(g+h) \leq m(g) + m(h).$$

На каждом из промежутков $] -\infty; -3]$, $[-3; 0]$, $[0; 1]$, $[1; 3]$ и $[3; \infty[$ функций $g, h$ и следовательно, $f$ линейны. «Раскрывая модель», получим, что $f(x) = -x+1$ при $x \leq -3$, $f(x) = -3x-5$ при $-3 \leq x \leq 0$ и т. д., после чего можно построить каждое звенье графика. (Впрочем, «Раскрывать модель» необязательно. Для построения графика, оченьindo, достаточно построить его точки

47

излома и по точке на бесконечных звеньях, то есть найти значения $f(-3), f(0), f(1), f(3)$ и, скажем, $f(4)$ и $f(-4)$.

6. Ответ: $f_1(x) = \frac{1}{2}x + \frac{1}{2}|x|$, $f_2(x) = f_1(-x-1) + f_1(x-1) = -1 + \frac{1}{2}|x+1| + \frac{1}{2}|x-1|$, $f_3(x) = 1 - |x| + f_2(x) = \frac{1}{2}|x+1| - |x| + \frac{1}{2}|x-1|$.

b) Ответ: $f_0(x) = -6 + |x+7| - 2|x+3| + 3|x| + \frac{5}{3}|-2|x| - |x-1| + 3|x-\frac{7}{3}| - 2|x-3| + |x-5|$.

Решим задачу сразу в обшем виде. Пусть $f$ — кусочно-линейная функция с изломами в точках с абсциссами $a_1, \dots, a_m$ и путь $k_0, k_1, \dots, k_m$ — угловые коэффициенты звеньев ее графика на промежутках $] -\infty; a_1]$, $[a_1; a_2]$, …, $[a_m; \infty$ [. Показем, что ее можно единственным образом представить в виде

$$f(x) = kx + b + c_1|x-a_1| + \dots + c_m|x-a_m|.$$

(1)

Это можно сделать, «раскрыв модели» на каждом из $m+1$ промежутков, приравнять коэффициент при $x$ в получившемся выражении для $f(x)$ к соответствующему $k_i$ и решив возникшую систему уравнения относительно $k, c_1, \dots, c_m$. Но можно сразу найти значения $c_1, \dots, c_m$.

Пусть $l_i(x)$ — линейная функция, совпадающая с $f(x)$ на $i$-м промежутке; ее угловой коэффициент равен $k_i$. Если функция $f(x)$ представима в виде (1), то есть $f(x) = c_i|x-a_i| + h(x)$, где $h(x)$ — линейная на промежутке $[a_{i-1}; a_{i+1}]$ функция, то на этом промежутке $l_{i-1}(x) = c_i(a_i-x)+h(x)$, $l_i(x) = c_i(x-a_i)+h(x)$, а угловой коэффициент разности $l_i(x) - l_{i-1}(x) = 2c_i x$ равен $k_i - k_{i-1}$. Следовательно, должны выполняться равенства $c_i = (k_i - k_{i-1})/2, i=1, 2, \dots, m$. Обратно, если они выполнются, то функция $c_1|x-a_1| + \dots + c_m|x-a_m|$ имеет изломы в тех же точках, что и $f$, и изменение углового коэффициента при переходе через любую из этих точек для обихих функций будет одинаковым. Поэтому разность этих функций — линейная функция $kx+b$. Угловые коэффициенты левой и правой части (1) при $x>a_m$ равны $k_m$ и $k+c_1+...+c_m=k+(k_m-k_1)/2$ соответственно, поэтому $k=(k_1+k_m)/2$. Значение $b$ можно найти, подставляя в (1) любое конкретное значение $x$, например $x=0$.

Коэффициенты $k_0, \dots, k_9$ для функции $f_0$ выписаны над ее графиком (рис. 2). Подставляя их в полученные формулы, найдем приведенный выше ответ.

г) Ответ: Если в запись функции $f$, рассматриваем в задаче, знак модели входит $n$ раз, то число изломов $m(f)$ её графика не превыходит $2^n-1$.

Это утверждение мы доказем индукцией по $n$. При $n=0$ оно очевидно (у линейной функции изломов нет). Пусть оно верно, если число модели меньше $n$, а в запись функции $f$ входит $n$ модели. Тогда эту функцию можно представить в виде $f=|g|+h$, причем функция $g$ записьается с $n_1$ модулями, а $h$ — с $n_2$ модулями, где $n_1+n_2=n-1$. В силу утверждения (1) и (2) пункту а) и предположения индукции

$$m(f) \leq m(|g|)+m(h) \leq 2m(g)+1+m(h) \leq 2 \cdot (2^{n_1}-1)+1+2^{n_2}-1=2^{n_1+1}+2^{n_2}-2 \leq 2^{n_1+n_2+1}-1=2^{n}-1,$$

поскольку $2^{n_1+n_2+1}-2^{n_1+1}-2^{n_2}+1=(2^{n_1+1}-1)(2^{n_2}-1) \geq 0$.

График функции $y=|...||x|-2^{n-2}|-2^{n-3}|...-1|$ (см. рис. 3 для $n=3$) имеетровно $2^n-1$ излом (при $n$ модулях в записи функций), поэтому оценка в задаче точная.

П. Г. Сатьянов

◆ Каждое из рассматриваемых чисел при делении на 9 дает остаток, равный остатку от деления суммы его цифр $1+2+...+7=28$ на 9, то есть 1. Такой же остаток дает при делении на 9 и седьмы степени

48

Чисел не может равнять сумме сельых стеленей остальных чисел.

М850*. Через точку пересечения биссектрисы уела А треугольника ABC и отрезка, соединяющего основания двух других биссектрис, проведена прямая, параллельная стороне BC. Докажите, что длина меньшего основания образованшейся трапецей равна получиме длин ее боковых сторон.

Рис. 1.

Введем следующие обозначения: $a, b, c$ — длины сторон данного треугольника $ABC, A_1, B_1, C_1$ — основания его биссектрис, $K$ — точка пересечения биссектрисы $AA_1$ с отрезком $B_1C_1$, $MN$ — проведенный через нее параллельно стороне BC отрезок (см. рис. 1). Поскольку треугольники AMN и ABC готовятся, справедливые следующее:

$$|MN|:|BC|=|AK|:|AA_1|,$$
$$|BM|:|AB|=|CN|:|AC|=|A_1K|:|AA_1|.$$

Выражая отсюда $|BM|, |CN|$ и $|MN|$, получим

$$\frac{|BM|+|CN|}{|MN|}=\frac{(|AB|+|AC|)\cdot|A_1K|/|AA_1|}{|BC| \cdot |AK|/|AA_1|}=\frac{b+c}{a} \cdot \frac{|A_1K|}{|AK|}.$$

Тепер остается доказать, что $|A_1K|:|AK|=2a/(b+c)$.

Самое короткое доказательство дает метод центров масс, о котором подробно расссказываюсь в статье М. Б. Балка и В. Г. Болтянского («Квант», 1984, № 4, с. 18). Поместим в точку $A$ массу 2$a$, в точки $B$ и $C$ — массы $b$ и $c$. (рис. 2). Центр двух масс — массы $b$ в точке $B$ и массы $a$ в точке $A$ — находится в точке $C_1$ (поскольку по известному свойству биссектрисы треугольника$^*$) $|AC_1|:|C_1B|=b:a$); аналогично, центр массы $c$ в точке $C$ и оставшейся массы $a$ в точке $A$ находится в $B_1$. Следовательно, общий центр масс лежит на отрезке $B_1C_1$. С другой стороны, центр масс $b$ и $c$ — это точка $A_1(|BA_1|:|A_1C|=c:b)$, поэтому общий центр масс лежит на отрезке $AA_1$, а значит, в точке $K$, и делит его в отношении $|A_1K|:|KA|=2c:(a+b)$, что и требовалось доказать.

Приведем еще одно, векторное, доказательство. Выразим вектор $\vec{A}_1$ через векторы $\vec{b}=\vec{A}C$ и $c=\vec{A}B$ и их длины, пользовясь свойством биссектрисы:

$$\vec{A}_1=\vec{AB}+\vec{BA}=\vec{AB}+\frac{|BA_1|}{|BC|} \cdot \vec{BC}=\vec{c}+\frac{c}{b+c} \cdot (\vec{b}-\vec{c})=\frac{b\vec{c}+c\vec{b}}{b+c}.$$

Аналогично выражается вектор $\vec{A}K$ через $\vec{b}_1=\vec{A}B_1$ и $\vec{c}_1=\vec{A}C_1$ и длины векторов $b_1$ и $c_1$:

$$\vec{A}K=\frac{b_1\vec{c}_1+c_1\vec{b}_1}{b_1+c_1}.$$

Но $\vec{b}_1=\frac{cb}{a+c}, \vec{c}_1=\frac{bc}{a+b}$, а $\vec{A}K=k\vec{A}_1$, где $k=|AK|:|AA_1|$.

49

Отсюда легко получить, что

$$\overrightarrow{AK} = \frac{b\vec{c} + c\vec{b}}{2a + b + c} = k \frac{b\vec{c} + c\vec{b}}{b + c},$$

то есть $k = (b + c) / (2a + b + c)$. Следовательно, $|A_1K|:|KA| = (1/k) - 1 = 2a / (b + c)$.

Из решения задачи вытекает, что каждый из отрезков $MK$ и $KN$ вдвое короче прилежащий к нему стороны трапеции.

В. Н. Дубровский

Ф858. После удара футболиста мяч полетел в направлении ворот, находящемся на расстоянии $L = 32$ м, со скоростью $v = 25$ м/с под углом $\alpha$ к горизонту ($\cos \alpha = 0,8$). Из-за бокового ветра, душицего вдоль воот перендикулярно скорости $\vec{v}$, горизонтальное смещение мяча в плоскости ворот оказалось равным $s = 2$ м. Найти время полета мяча до плоскости ворот. Мяч не врачается; скорость ветра $u = 10$ м/с.

♦ Рассмотрим движение мяча в системе отчета $K$, движущейся со скоростью $\vec{u}$. Свяжем с $K$ прямогольную систему координат $XYZ$ с началом в точке удара $A$ такую, что плоскость $XY$ горизонтальная, а ось $X$ параллельна плоскости ворот $P$ (см. рисунок).

Начальная скорость мяча в этой системе

$$\vec{v}_1 = \vec{v} - \vec{u}.$$

В системе $K$ воздух неподвижен, и траектория мяча $ABC$ будет находиться в вертикальной плоскости, в которой лежит вектор $\vec{v}_1$, причем траектория не будет параболой, поскольку на мяч действует кроме силы тяжестей еще и сила сопротивления со стороны воздуха, направленная против мгновенной скорости мяча. Заметим сразу, что характер зависимости силы сопротивления от скорости в задаче не дан и для решения не потребуется.

За время полета $t$ до плоскости ворот мяч переместится в системе $K$ вдоль оси $Y$ на расстояние $L$, а вдоль оси $X$ — на расстояние $s_1$, причем (см. рисунок; точка $C$ лежит на плоскости $P$)

$$\frac{s_1}{L} = \frac{u}{v \cos \alpha},$$

откуда

$$s_1 = \frac{Lu}{v \cos \alpha}.$$

(1)

За это же время $t$ система $K$ сместится вдоль оси $X$ в противоположном направлении на расстояние

$$s_2 = ut.$$

(2)

Реальное горизонтальное смещение мяча (в непод-

50

вижной системе отчета) проинсходит в отрицательном направлении оси $X$ и равно
$$s = s_2 - s_1.$$
Учитывая (1) и (2), получаем уравнение для нахождения $t$:
$$s = ut - \frac{Lu}{v \cos \alpha},$$
откуда
$$t = \frac{L}{v \cos \alpha} + \frac{s}{u}.$$
Подстановка численных значений дает $t = 1,8$ с.
В. И. Чивилёв

Ф859. Шар радиуса $R$ и массы $m$ движется по горизонтальной поверхности под действием постоянной силы натяжения $F$ легкой нерактижимой нити. Точка закрепления нити находится на высоте $h$ над поверхности (см. рис.1), нить все время горизонтальная, шар движется поступательно. При каждом максимальном коэффициенте треня это возможно?
Чему равно ускорение шара?

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

Запишем условие поступательного движения шара (равенство нуля суммы моментов действияших на шар сил относительной точки $O$):
$$F_{\text{тр}} R = F(R - h).$$
Отсюда
$$F_{\text{тр}} = F \left(1 - \frac{h}{R}\right).$$
С другой стороны,
$$F_{\text{тр}} = \mu mg.$$
Из двух последних уравнений находим $\mu$:
$$\mu = \frac{F}{mg} \left(1 - \frac{h}{R}\right).$$
Ускорение шара найдем из П закона Ньютона:
$$ma = F - F_{\text{тр}} = F \frac{h}{R},$$
откуда
$$a = \frac{F}{m} \frac{h}{R}.$$
Л. Г. Маркович

Ф860. В конечской непроводящей лунке с углом 2α при вершине на глубине $h$ находится два небольших одинаково заряженных теля, связанных нитью (рис.1); масса каждого теля $m$. После пережIZания нити теля начинают скользить вверх по поверхности лунки и вылетают из лунки на высоте $H$ над ее основанием со скоростью $v$. Коэффициент треня теля по поверхности лунки $\mu = a \lg a (a < 1)$. Определить заряды теля.

◆ В начальной момент времени (в момент пережигания нити) всю энергию системы составляет электрическая энергия теля:
$$W_1 = E_1 = k \frac{Q^2}{2(H - h) \lg a}$$
(потенциальную энергию на глубине $h$ принимаем равной нуль). В момент вылета теля из лунки энергия системы складывается из электрической энергии
$$E_2 = k \frac{Q^2}{2H \lg a},$$ кинетическая энергия теля $K = mv^2$ и их потенциальной энергии $\Pi = 2mgh$:
$$W_2 = E_2 + K + \Pi.$$
Согласно закону сохранения энергии, $W_1 = W_2 + A,$

51

ИЛИ

$$E_1 = E_2 + K + \Pi + A \Rightarrow E_1 - E_2 = K + \Pi + A,$$

где $A$ — энергия, потраченная на преодоление сил трения. Найдем эту энергию.

Рассмотрим движение тела на малом участке $\Delta s$ поверхности лунки таком, что силу электростатического отталкивания $f_s$ на этом участке можно считать постоянной. Сила трения $f_{\tau p}$, действующая на тело, на этом участке постоянна и равна (рис. 2)

$$f_{\tau p} = \mu N = \mu (f_s \cos \alpha + mg \sin \alpha).$$

Работа силы трения на участке $\Delta s$ численно равна

$$\Delta a = f_{\tau p} \cdot \Delta s = \mu f_s \cos \alpha \cdot \Delta s + \mu mg \sin \alpha \cdot \Delta s =$$

$$= \mu ctg \alpha f_s (\sin \alpha \cdot \Delta s) + \mu tg \alpha mg (\cos \alpha \cdot \Delta s) =$$

$$= \mu ctg \alpha (f_s \cdot \Delta x) + \mu tg \alpha (mg \cdot \Delta h)$$

(см. рис. 3). Но $f_s \cdot \Delta x$ — это изменение электрической энергии тела, а $mg \cdot \Delta h$ — изменение его потенциальной энергии. Таким образом, полная работа силы трения при движении тела равна по абсцилной величины

$$A = \mu ctg \alpha \cdot (E_1 - E_2) + \mu tg \alpha \cdot \Pi.$$

Итак, согласно закону сохранения энергии,

$$E_1 - E_2 = K + \Pi + \mu ctg \alpha \cdot (E_1 - E_2) + \mu tg \alpha \cdot \Pi.$$

Подставляя выражения для $E_1, E_2, K, \Pi$ и $\mu = a tg \alpha$, получаем

$$\frac{kQ^2}{2(H - h)tg \alpha} - \frac{kQ^2}{2Htg \alpha} =$$

$$= mv^2 + 2mgh + a \left( \frac{kQ^2}{2(H - h)tg \alpha} - \frac{kQ^2}{2Htg \alpha} \right) + 2a tg^2 \alpha \cdot mgh.$$

Отсюда находится $Q$:

$$Q = \sqrt{\frac{2mH(H - h)tg \alpha \cdot (v^2 + 2gh(1 + a tg^2 \alpha))}{kh(1 - a)}}.$$

О. Я. Савченко

Ф861. В колебательном RLC контуре сопротивление невелико, так что колебания затухают в нем слабо. Для получения незначительной колебанной системы и должны быть не менее убили энергии из-за джоулевых потерь на сопротивлении.

По закону индукции Фарадя $\mathcal{E}_{\text{инд}} = -\frac{\Delta \phi}{\Delta t}$ и $I_{\text{инд}} = -\frac{1}{R} \frac{\Delta \phi}{\Delta t}$. При быстрое растяжении катушки $\Delta t \rightarrow 0$, а поскольку ток не может достигаться бесконечно больших значений, то в этом случае и $\Delta \phi \rightarrow 0$, то есть в этом процессе сохранения магнитный поток $\Phi$.

Работа, совершаемая при растяжении, идет только на увеличение энергии магнитного поля:

$$\Delta A = \Delta W_+ = \frac{L' I'^2}{2} - \frac{L I^2}{2} = \frac{L'^2 I'^2}{2L'} - \frac{L^2 I^2}{2L} =$$

$$= \frac{\phi^2}{2L} \left( \frac{L}{L'} - 1 \right) = \frac{\phi^2}{2L} \left( \frac{l + \Delta l}{l} - 1 \right) = \frac{\phi^2}{2L} \frac{\Delta l}{l} = \frac{L I^2_a}{2} \frac{\Delta l}{l},$$

52

где штрихи проставлены у величины, относихся к состоянию системы после растягивания катушки, $I_a$ — амплитудное значение силы тока (в момент растягивания ток максимален).

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

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

$$\Delta W_- = I_a^2 R \frac{T}{2} = \frac{1}{2} I_a^2 R \pi \sqrt{LC},$$

где $I_a$ — действующее значение тока.

Колебания будут незатухающими, если $\Delta W_+ \geqslant \Delta W_-$, то есть

$$\frac{LI_a^2}{2} \frac{\Delta l}{l} \geqslant \frac{1}{2} I_a^2 R \pi \sqrt{LC},$$

откуда

$$\frac{\Delta l}{l} \geqslant \pi R \sqrt{\frac{C}{L}}.$$

A. И. Киркинский

Metod
производящих
функции
(Начало см. на c. 11)

Указание. Воспользовитесь соотношениями (доказав их)

$$\frac{1}{1-z} \cdot \frac{1}{1-z^3} \cdot \frac{1}{1-z^5} \cdot \dots =$$

$$= (1+z+z^2+z^3+...) \cdot (1+z^3+z^6+z^9+...) \times$$

$$\times (1+z^5+z^{10}+...) \cdot ... = (1+z)(1+z^2) \times$$

$$\times (1+z^3)(1+z^4) \dots = (1-z^m)(1+z^m)(1+z^{2m}) \times$$

$$\times (1+z^{4m})(1+z^{8m}) \dots = 1.$$

4. Найдите явную формулу для общего члена последовательности $(u_n) = (0, 1, 5, 19, 65, ...)$, заданной рекуррентными соотношениями $u_0 = 0$, $u_1 = 1$, $u_{n+1} = 5u_n - 6u_{n-1}$.

Указание. Воспользовитесь тем, что ряд $u_0+u_1z+u_2z^2+...$ можно представить в виде

$$\frac{z}{6z^2-5z+1} = \frac{1}{1-3z} - \frac{1}{1-2z} =$$

$$= (1+2z+2^2z^2+2^3z^3+...) \times$$

$$\times (1+3z+3^2z^2+3^3z^3+...).$$

5. Пусть $n>2$ — фиксированное натуральное число. Рассмотите ряд

$$f(z) = z^n + z^{n^2} + z^{n^3} + ...;$$

$$[f(z)]^2 = c_1z + c_2z^2 + c_3z^3 + ...$$

и показите, что число цельх решений $(k_1; k_2; k_3)$ уравнения Ферма $k_1^n + k_2^n = k_3^n$ равно $c_m$ при $m=k_3^n$.

Замечание. К сожалению, к вычислению коэффициентов $c_m$ для любого $m$ подходов не видно!

6. Найдите $v_n$ — количество различных разбиений выпуклого $n$-угольника непересекающихся диагоналями на треугольники (например, $v_5=5$, $v_6=9$).

Указание. Положите $v_2=v_3=1$ и показите рекуррентное соотношение

$$v_n = v_2v_{n-1} + v_3 \cdot v_{n-2} + ... + v_{n-1}v_n, n \geqslant 3.$$

Воспользовитесь этим, чтобы доказать соотношение $(\alpha(z))^2 - \alpha(z) = z$, где $\alpha(z) = v_2z + v_3z^2 + v_4z^3 + ...$, найдите отсюда $\alpha(z)$ и дифференцирует.

Ответ. $v_n = \frac{(2n-4)!}{(n-2)!(n-1)!}$. Эти числа называются числами Каталана.