Автор: Павел Жуков

Задача из журнала «Квант» (2000 год, 3 выпуск) М1707*

Условие

Квадрат клетчатой бумаги, состоящий из $n\times n$ клеток, разрезан на $2n$ прямоугольников. При этом каждый прямоугольник расположен либо целиком ниже, либо выше ступенчатой ломаной, разделяющей квадрат (рис.1). Докажите, что найдется клетка клетчатой бумаги, являющаяся одним из названных прямоугольников.

Рис. 1

Решение

Ступенчатая ломанная разрезает квадрат на два ступенчатых треугольника $T_1$ и $T_2$, при этом основание $T_1$ состоит из $n$ клеток, а основание $T_2$ – из $n – 1$ клетки. В силу условия задачи, один из них разрезан на $m$, а другой – на $k$ прямоугольников, причем $m + k = 2n$. Пока что фиксируем внимание на отдельно взятом ступенчатом треугольнике $T$, в основании которого $s$ клеток (рис.2). Так как при разрезании $T$ на прямоугольники любые две точки из набора $A_1, A_2, \ldots, A_s$ должны принадлежать разным прямоугольникам, можно заключить, что $T$ нельзя разрезать на менее чем $s$ прямоугольников.

Рис. 2

Разберем далее тот случай, когда $T$ разрезан в точности на s прямоугольников; тогда каждая из точек $A_1, A_2 , \ldots, A_s$ принадлежит только одному из них и, более того, каждая из $s$ закрашенных клеток принадлежит целиком только одному из $s$ прямоугольников. Не закрашенных клеток, примыкающих по сторонам к закрашенным, на единицу меньше, чем закрашенных, поэтому хотя бы один из $s$ прямоугольников не выйдет за пределы своей заштрихованной клетки, т.е. будет с ней совпадать. Возвращаясь к ступенчатым треугольникам $T_1$ и $T_2$, можно сказать, что $m \geq n$, а $k \geq n-1$. Но так как $m + k = 2n$, то либо $m = n$, либо $k = n – 1$. Значит, либо в $T_1$, либо в $T_2$ найдется прямоугольник, совпадающий с клеткой клетчатой бумаги.

В.Произволов

6.3 Интегрирование рациональных функций.

Рациональной функцией (или дробью) называется функция вида
$$f(x) = \displaystyle\frac{P(x)}{Q(x)},$$
где $P(x)$ и $Q(x)$ – многочлены. Если степень числителя меньше степени знаменателя, то рациональная дробь называется правильной. Ясно, что каждая рациональная дробь может быть представлена в виде
$$\displaystyle\frac{P(x)}{Q(x)} = R(x) + \displaystyle\frac{P_{1}(x)}{Q(x)},$$
где $R(x)$ – многочлен, а дробь $\displaystyle\frac{P_{1}(x)}{Q(x)}$ – правильная. Поскольку интегралы от многочленов вычисляются совсем просто, то мы будем рассматривать методы интегрирования правильных дробей.

Будем различать следующие четыре вида дробей:

  • $\displaystyle\frac{A}{x-a}$, где $A$, $a$ — постоянные.
  • $\displaystyle\frac{A}{(x-a)^k}$, где $A$, $a$ — постоянные, $k = 2,3 \ldots$
  • $\displaystyle\frac{Mx + N}{x^2 + px + q}$, где $M$, $N$, $p$, $q$ – постоянные, квадратный трехчлен в знаменателе не имеет действительных корней.
  • $\displaystyle\frac{Mx + N}{(x^2 + px + q)^k}$, где $M$, $N$, $p$, $q$ – постоянные, квадратный трехчлен в знаменателе не имеет действительных корней.

Покажем как вычисляются интегралы от каждой из этих дробей.

  • $\int \displaystyle\frac{a}{x-a}dx = A\ln\left | x — a \right | + C$.
  • $\int \displaystyle\frac{a}{(x-a)^k}dx = -\frac{A}{k-1}\cdot \displaystyle\frac{1}{(x-a)^{k-1}} + C$.
  • $\int \displaystyle\frac{Mx + N}{x^2 + px + q}dx$. Для вычисления этого интеграла представим подынтегральное выражение в виде
    $$\displaystyle\frac{Mx + N}{x^2 + px + q} = \displaystyle\frac{\frac{M}{2}(2x+p) + N — p\frac{M}{2}}{x^2 + px + q} = \displaystyle\frac{M}{2} \cdot \displaystyle\frac{2x+p}{x^2 + px + q} + \displaystyle\frac{N-p\displaystyle\frac{M}{2}}{x^2 + px + q}.$$
    Для вычисления интеграла от первого слагаемого справа, очевидно, достаточно выполнить замену $t = x^2 + px + q$. Тогда получим
    $$\int \displaystyle\frac{2x + p}{x^2 + px + q} = \ln(x^2 + px + q) + C.$$
    Для вычисления интеграла от второго слагаемого справа выделим полный квадрат в знаменателе, т.е. представим знаменатель в виде $x^2 + px + q = (x+\displaystyle\frac{p}{2})^2 + q — \displaystyle\frac{p^2}{4}$. Поскольку квадратный трехчлен в знаменателе не имеет действительных корней, то его дискриминант $\displaystyle\frac{p^2}{4} — q < 0$. Обозначим $a^2 = q — \displaystyle\frac{p^2}{4}$. Выполняя замену $x + \displaystyle\frac{p}{2} = t$, получим
    $$\int \displaystyle\frac{1}{x^2 + px + q}dx = \int \displaystyle\frac{1}{(x+\displaystyle\frac{p}{2})^2 + a^2}dx = \int \displaystyle\frac{dt}{t^2 + a^2} = \frac{1}{a^2} \int \displaystyle\frac{dt}{\displaystyle\frac{t^2}{a^2} + 1} =\\= \displaystyle\frac{1}{a} \int \displaystyle\frac{d(\displaystyle\frac{t}{a})}{(\displaystyle\frac{t}{a})^2 + 1} = \displaystyle\frac{1}{a} \text{arctg}\: \displaystyle\frac{t}{a} + C .$$
    Возвращаясь теперь к старой переменной, получим исходный интеграл.
  • $\displaystyle\frac{Mx + N}{(x^2 + px + q)^k}$. Для вычисления этого интеграла, как и в предыдущем случае, представим подынтегральное выражение в виде
    $$\displaystyle\frac{Mx + N}{(x^2 + px + q)^k} = \displaystyle\frac{\frac{M}{2}(2x + p) + N — p\displaystyle\frac{M}{2}}{(x^2 + px + q)^k} =\\=\displaystyle\frac{M}{2} \cdot \displaystyle\frac{2x+p}{(x^2 + px + q)^k} + \displaystyle\frac{N-p\frac{m}{2}}{(x^2 + px + q)^k}.$$
    Для вычисления интеграла от первого слагаемого справа, очевидно, достаточно выполнить замену $t = x^2 + px + q.$ Тогда получим
    $$\int \displaystyle\frac{2x + p}{(x^2 + px + q)^k}dx = \displaystyle\frac{1}{-k+1}(x^2+px+q)^{-k+1} +C.$$
    Для вычисления интеграла от второго слагаемого, как и в предыдущем случае, выделим полный квадрат из квадратного трехчлена в знаменателе. Тогда после замены переменной $t = x+\displaystyle\frac{p}{2}$ он сведется к интегралу вида $\int \displaystyle\frac{dt}{(t^2+a^2)^k}$. Обозначим этот интеграл через $I_{k}$ и выведем рекуррентную формулу для вычисления этого интеграла. Будем применять формулу интегрирования по частям. Имеем
    $$ I_{k} = \int \displaystyle\frac{dt}{(t^2 + a^2)^k} = \begin{bmatrix}u = \displaystyle\frac{1}{(t^2+a^2)^k}, & dv = dt \\ du = -\displaystyle\frac{2kt}{(t^2+a^2)^{k+1}}, & v = t \end{bmatrix} =\\=\displaystyle\frac{t}{(t^2 + a^2)^k} + 2k\int \displaystyle\frac{t^2}{(t^2 + a^2)^{k+1}}dt = \displaystyle\frac{t}{(t^2 + a^2)^k}+2k\int\displaystyle\frac{t^2 + a^2 — a^2}{(t^2 + a^2)^{k+1}}dt =\\= \displaystyle\frac{t}{(t^2 + a^2)^k} + 2k\int \displaystyle\frac{dt}{(t^2 + a^2)^k} — 2ka^2 \int \displaystyle\frac{dt}{(t^2 + a^2)^{k+1}} =\\= \displaystyle\frac{t}{(t^2 + a^2)^k} + 2kI_{k} — 2ka^2I_{k+1}.$$
    Отсюда находим
    $$I_{k+1} = \displaystyle\frac{1}{2ka^2}\begin{bmatrix} \displaystyle\frac{t}{(t^2 + a^2)^k} +(2k-1)I_k \end{bmatrix} (k = 1,2,\ldots).$$
    При этом, как мы уже вычислили ранее,
    $$I_{1} = \int \displaystyle\frac{dt}{t^2 + a^2} = \displaystyle\frac{1}{a} \text{arctg}\:\displaystyle\frac{t}{a} + C.$$
    Итак, и в этом случае мы получили правило вычисления интеграла от дроби четвертого вида.

Из основной теоремы алгебры следует, что каждый многочлен с действительными коэффициентами может быть представлен в виде произведения конечного числа линейных сомножителей вида $x — a$ и квадратичных сомножителей вида $x^2 + px + q$, где $\displaystyle\frac{p^2}{4} — q < 0$. Именно, справедливо равенство
$$Q(x) = A(x-a_1)^{k_1}\ldots(x-a_r)^{k_r}(x^2+p_1x+q_1)^{m_1}\ldots(x^2+p_sx+q_s)^{m_s}, (1)$$
где $k_i$ и $m_i$ – целые неотрицательные числа.
С использованием этого представления можно показать, что справедлива следующая

Теорема. Пусть $\displaystyle\frac{P(x)}{Q(x)}$ – правильная дробь, знаменатель которой допускает разложение (1). Тогда эта дробь единственным образом может быть представлена в виде суммы простых дробей, т.е.
$$\displaystyle\frac{P(x)}{Q(x)} = \sum_{i=1}^{r}\sum_{j=1}^{k_i}\displaystyle\frac{A_{ij}}{(x-a_i)^j} + \sum_{i=1}^{r}\sum_{j=1}^{m_i}\displaystyle\frac{M_{ij}x + N_{ij}}{(x^2 + P_ix+q_i)^j}.$$

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

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

Метод Остроградского. Этот метод интегрирования рациональных дробей предназначен для выделения рациональной части из интеграла от рациональной функции. Именно, используя представление (1), интеграл от правильной дроби представляется в виде
$$\int \displaystyle\frac{P(x)}{Q(x)} =\\=\int \displaystyle\frac{P(x)}{A(x-a_1)^{k_1}\ldots(x-a_r)^{k_r}(x^2+p_1x +q_1)^{m_1}\ldots(x^2+p_sx+q_s)^{m_s}}dx =\\=\int \displaystyle\frac{R_{k_1 + \ldots + k_r + 2(m_1 + \ldots + m_s) — r — 2s — 1}(x)dx}{A(x-a_1)^{k_1-1}\ldots(x-a_r)^{k_r-1}(x^2+p_1x +q_1)^{m_1-1}\ldots(x^2+p_sx+q_s)^{m_s-1}} +\\+ \int \displaystyle\frac{S_{r+2r-1}(x)}{A(x-a_1)…(x-a_r)(x^2+p_1x +q_1)^{m_1-1}\ldots(x^2+p_sx+q_s)}dx,$$
где многочлены $R_{k_1+\ldots+k_r+2(m_1 + \ldots + m_s)-r-2s-1}(x)$ и $S_{r+2s-1}(x)$ степени $k_1+\ldots+k_r+2(m_1+\ldots+m_s)-r-2s-1$ и $r+2s-1$ соответственно имеют неопределенные коэффициенты. Эти коэффициенты находятся затем из условия равенства производных левой и правой частей записанного равенства. Таким образом, вычисление интеграла от правильной дроби сводится к вычислению интеграла от другой правильной дроби, у которой в знаменателе все множители в первой степени. Такой интеграл вычисляется, как указано выше, путем разложения подынтегрального выражения
на простые дроби. Тем самым отпадает необходимость в использовании полученной выше рекуррентной формулы для вычисления интегралов от простой дроби четвертого типа.

Примеры решения задач

  1. Найти неопределенный интеграл $I = \int \displaystyle\frac{2x^2 — 3x + 3}{x^3 — 2x^2 + x}dx$.
    Решение

    Разложим знаменатель на множители: $x^3 -2x^2 + x = x(x-1)^2$. Тогда подынтегральная функция представима в виде

    $$\displaystyle\frac{2x^2-3x+3}{x(x-1)^2} = \displaystyle\frac{A}{x} + \displaystyle\frac{B}{x-1} + \displaystyle\frac{C}{(x-1)^2},$$
    где $A$, $B$, $C $ – постоянные коэффициенты. Для их нахождения приведем выражение справа к общему знаменателю и, приравнивая числители полученных дробей, найдем

    $$2x^2-3x+3=A(x-1)^2 + Bx(x-1)+Cx.$$

    Поскольку это тождество имеет место при всех $x$, кроме $x=0,x=1,$ то коэффициенты этих многочленов при одинаковых степенях $x$ равны. Приравнивая их, получаем линейную систему уравнений

    $$\left.\begin{matrix}x^2 : & A+B=2\\ x : & -2A-B+C=-3\\ x^0 : & A=3\end{matrix}\right\}$$

    Решая эту систему, находим $A = 3$, $B = −1$, $C = 2.$ Подставляя эти значения в разложение подынтегральной функции и вычисляя соответствующие интегралы, получаем
    $$I=3\ln\left | x \right | — \ln \left | x-1 \right | — \displaystyle\frac{2}{x-1} + C = \ln \displaystyle\frac{\left | x \right |^3}{\left | x-1 \right |} — \displaystyle\frac{2}{x-1} +C.$$

  2. Найти неопределенный интеграл $I = \int \displaystyle\frac{x dx}{x^3 + 1}dx$.
    Решение

    Как и в предыдущем примере, разложим на множители знаменатель:

    $$x^3 + 1 = (x+1)(x^2-x+1).$$
    Раскладываем подынтегральное выражение с неопределнными коэффициентами
    $$\displaystyle\frac{x}{x^3 + 1} = \displaystyle\frac{A}{x+1} + \displaystyle\frac{Mx+N}{x^2-x+1},$$
    откуда $x = A(x^2−x+1)+(Mx+N)(x+1)$. Приравнивая коэффициенты при одинаковых степенях $x$, составляем линейную систему для нахождения чисел $A$, $M$, $N$:
    $$\left.\begin{matrix}x^2 : & 0+A+M,\\ x : & 1=-A+M+N,\\ x^0 : & 0=A+N.\end{matrix}\right\}$$
    Решая эту систему, находим $A = −\displaystyle\frac{1}{3}, M = N =\displaystyle\frac{1}{3}$. Поэтому
    $$I=-\displaystyle\frac{1}{3}\ln\left | x+1 \right | + \displaystyle\frac{1}{3}\int \displaystyle\frac{x+1}{x^2-x+1}dx=\\=-\displaystyle\frac{1}{3}\ln\left | x+1 \right | + \displaystyle\frac{1}{6}\int \displaystyle\frac{2x-1}{x^2-x+1}dx + \displaystyle\frac{1}{2}\int \displaystyle\frac{dx}{x^2-x+1}=\\=-\displaystyle\frac{1}{3}\ln\left | x+1 \right | + \displaystyle\frac{1}{6}\ln(x^2-x+1) + \displaystyle\frac{1}{2} \int \displaystyle\frac{dx}{(x — \displaystyle\frac{1}{2})^2 + \displaystyle\frac{3}{4}} =\\=-\displaystyle\frac{1}{3}\ln\left | x+1 \right | + \displaystyle\frac{1}{6}\ln(x^2-x+1) + \displaystyle\frac{1}{\sqrt{3}}\text{arctg}\:\displaystyle\frac{2}{\sqrt{3}}(x-\displaystyle\frac{1}{2}) + C.$$

  3. Найти неопределенный интеграл $\int \displaystyle\frac{(x^2 — 19x + 6)}{(x-1)(x^2 + 5x + 6)}dx$
    Решение

    Разложим знаменатель на множители: $(x-1)(x^2+5x+6) = (x-1)(x-2)(x-3).$ Тогда подынтегральная функция представима в виде:
    $$\displaystyle\frac{x^2-19x+6}{(x-1)(x^2+5x+6)} = \displaystyle\frac{A}{x-1} + \displaystyle\frac{B}{x+2} + \displaystyle\frac{C}{x+3}$$
    Для нахождения $A, B$ и $C$ приведем выражение справа к общему знаменателю и, приравнивая числители полученных дробей, найдем
    $$A(x^2 + 5x + 6) + B(x^2 + 2x — 3) + c(x^2 + x — 2) = x^2 -19x+6$$
    Приравнивая коэффициенты при одинаковых степенях $x$, составляем систему линейных уравнений для нахождения чисел $A, B, C$
    $$\left.\begin{matrix} x^2 : & 1=A+B+C \\ x : & -19 = 5A+2B+C \\ x^0 : & 6=6A-3B-2C \end{matrix}\right\}$$
    Решаем систему, получаем значения $A = -1; B = -16; C=18$. Возвращаемся к изначальному интегралу и находим окончательное решение
    $$\int (-\displaystyle\frac{1}{x-1}-\displaystyle\frac{16}{x+2}+\displaystyle\frac{18}{x+3})dx = -\ln\left | x-1 \right | — 16\ln\left | x+2 \right |+18\ln\left | x+3 \right | + C.$$

  4. Найти неопределенный интеграл $\int \displaystyle\frac{x^2-6x+8}{x^3+8}dx$
    Решение

    По формуле суммы кубов раскладываем знаменатель на множители, используя формулу сокращенного умножения $a^3 + b^3 = (a+b)(a^2-ab+b^2)$
    $$\int \displaystyle\frac{x^2-6x+8}{x^3+8}dx = \int \displaystyle\frac{x^2-6x+8}{(x+2)(x^2-2x+4)}dx.$$
    Методом неопределенных коэффициентов разложим подынтегральную функцию в сумму элементарных дробей
    $$\displaystyle\frac{A}{x+2} +\displaystyle\frac{Bx+C}{x^2-2x+4} = \displaystyle\frac{x^2-6x+8}{(x+2)(x^2-2x+4)}.$$
    Приводим дробь к общему знаменателю
    $$A(x^2 — 2x + 4) + B(x^2 + 2x) + C(x+2) = x^2-6x+8$$
    Составим и решим систему
    $$\left.\begin{matrix}x^2 : & A+B=1\\ x : & -2A+2B+C=-6\\ x^0 : & 4A+2C=8\end{matrix}\right\}$$
    Подставим значения $A = 2$, $B = -1$, $C = 0$ в функцию и найдем интеграл
    $$\int (\displaystyle\frac{2}{x+2} — \displaystyle\frac{x}{x^2-2x+4})dx = 2\int \displaystyle\frac{dx}{x+2} + \int \displaystyle\frac{-\displaystyle\frac{1}{2}d(x^2-2x+4) — dx}{x^2 -2x +4} =\\= 2\ln \left | x+2 \right | — \displaystyle\frac{1}{2}\int\displaystyle\frac{d(x^2-2x+4)}{x^2-2x+4} — \int\displaystyle\frac{dx}{x^2-2x+1 +3} = \\= 2\ln \left | x+2 \right | — \frac{1}{2}\ln(x^2 — 2x + 4) — \int \frac{d(x-1)}{(x-1)^2 + (\sqrt{3})^2} = \\= 2\ln \left | x+2 \right | — \frac{1}{2}\ln(x^2 — 2x + 4) — \frac{1}{\sqrt{3}}\text{arctg}\:(\frac{x-1}{\sqrt{3}}) + C.$$

Интегрирование рациональных функций

Тест на тему: Интегрирование рациональных функций

Литература:

Смотрите также:

 

М1770. Игра с многочленом

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

Условие

Дан многочлен степени [latex]10[/latex] с буквенными коэффициентами. Двое поочередно заменяют какую-нибудь букву на число, пока не заменят все буквы. Обозначим полученный многочлен [latex]A(x)[/latex]. Пусть [latex]a_{1} = \max A(x)[/latex] при [latex]x[/latex] от [latex]-1[/latex] до [latex]0[/latex], [latex]a_{2} = \max A(x)[/latex] при [latex]x[/latex] от [latex]0[/latex] до [latex]+1[/latex]. Если [latex]a_1 > a_2[/latex], то выиграл первый игрок, если [latex]a_1 < a_2[/latex], то второй. Кто победит при правильной игре?

Решение

Результат игры в основном определяется тем, кто выберет последний коэффициент при нечетной степени. Это будет первый игрок, который может гарантировать свой не проигрыш. Говорить о выигрыше пока рано: может быть, за счет выбора коэффициентов при четных степенях второму игроку удастся добиться, чтобы [latex]\max A(x)[/latex] при [latex]x[/latex] от [latex]-1[/latex] до [latex]+1[/latex] был бы при [latex]x = 0[/latex] ([latex]a_{1} = a_{2}[/latex] – ничья). Однако если первый игрок сразу выберет коэффициент при первой степени равным единице, то он гарантирует, что максимума в нуле нет, так как производная не равна нулю. Затем правильным назначением последнего коэффициента при нечетной степени (это будет достаточно большое по модулю число) первый игрок решительно склонит «чашу весов» в свою сторону. Он обеспечит себе победу независимо от возможных последующих назначений коэффициентов при четных степенях.

Н.Васильев, Б.Гинзбург

М1768. Аэробус

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

Условие

а) Расположите первые [latex]100[/latex] натуральных чисел в таком порядке, чтобы для любых нескольких (но не всех) из этих чисел сумма номеров занятых ими мест не равнялась сумме самих этих чисел.

б*) При посадке в аэробус пассажиры сели куда попало. В итоге все места оказались заняты, а для любого множества, в котором не более [latex]100[/latex] пассажиров, среднее арифметическое номеров занятых ими мест не менее чем на [latex]1[/latex] отличается от среднего арифметического номеров мест, указанных в билетах. Каково наименьшее возможное число мест в таком аэробусе?

Решение

а) Укажем два способа: [latex]100, 1, 2, \ldots, 97, 98, 99[/latex] и [latex]2, 3,4, \ldots, 99, 100, 1[/latex]. Каждый из них дает требуемое расположение чисел, в чем легко непосредственно убедиться.

б) Ответ: [latex]301[/latex] место.
Каждый пассажир включен в один из циклов вида [latex]P_{1}, P_{2}, \ldots , P_{m}[/latex], где [latex]P_{1}, P_{2}, \ldots , P_{m}[/latex] – некоторые пассажиры, причем [latex]P_{i}[/latex]-й пассажир ([latex]i =  1, 2, \ldots , m — 1[/latex]) имеет билет на место, которое занимает [latex]P_{i+1}[/latex]-й пассажир, а [latex]P_{m}[/latex]-й пассажир – на место, которое занимает [latex]P_{1}[/latex]-й пассажир. Если в таком цикле [latex]100[/latex] пассажиров или менее, то все они могли составить одну рассматриваемую группу, для которой среднее арифметическое номеров занимаемых ими мест равно среднему арифметическому номеров мест, указанных в их билетах, что противоречит условию. Поэтому [latex]m \geq 101 + r \geq 202[/latex]. Значит, если число циклов не меньше [latex]3[/latex], то в аэробусе размещаются [latex]303[/latex] или более пассажиров. Заметим далее, что если [latex]P_{k}, P_{k+1}, \ldots , P_{k+r} [/latex]– цепочка пассажиров, последовательно включенных в некоторый цикл, причем номера билетов [latex]P_{k}[/latex]-го и [latex]P_{k+r}[/latex]-го отличаются на [latex]1[/latex], то [latex]r \geq 101[/latex]. Рассматривая цепочку [latex]P_{k+r}, P_{k+r+1} , \ldots , P_{m}, P_{1}, \ldots , P_{k}[/latex], получим неравенство [latex]m — (k + r) + k \geq 101[/latex]. Следовательно, [latex]m \geq 101 + r \geq 202[/latex] , и поэтому число мест в аэробусе может быть меньшим, чем [latex]303[/latex], только если выполняется одно из следующих условий:

  1. Все пассажиры включены в один цикл;
  2. Число циклов равно [latex]2[/latex], причем любые два билета на соседние (по номерам) места принадлежат пассажирам из разных циклов.

Пусть выполнено первое условие. Рассмотрим пассажиров [latex]A_{n}, A_{n+1}[/latex] и [latex]A_{n+2}[/latex] с билетами на [latex]n[/latex]-е, [latex](n + 1)[/latex]-е и [latex](n + 2)[/latex]-е места соответственно. Между [latex]A_{n}[/latex]-м и [latex]A_{n+1}[/latex]-м пассажирами в кратчайшей из цепочек, их соединяющих, имеется не менее [latex]100[/latex] пассажиров, между [latex]A_{n+1}[/latex]-м и [latex]A_{n+2}[/latex]-м также не менее [latex]100[/latex] пассажиров, а между [latex]A_{n+2}[/latex]-м и [latex]A_{n}[/latex]-м либо нет ни одного пассажира, либо имеется не менее [latex]100[/latex]. Значит, если общее число мест меньше [latex]303[/latex], то либо [latex]A_{n}[/latex] сидит на [latex](n + 2)[/latex]-м месте, либо [latex]A_{n+2}[/latex] сидит на [latex]n[/latex]-м месте. Ввиду произвольности номера [latex]n[/latex] имеем (с точностью до направления) цикл [latex]A_{1} A_{3} A_{5} \ldots A_{N}A_{2}A_{4} \ldots A_{N’}[/latex], где [latex]N[/latex] и [latex]N'[/latex] – наибольший нечетный и наибольший четный номера соответственно, а [latex]A_{i}[/latex]–пассажир, занимающий [latex]i[/latex]-е место, [latex]i = 1, 2, \ldots, max ( N, N’)[/latex].Пассажиры, сидящие на местах [latex]N, 2, 4, \ldots , 198[/latex], имеют билеты на места [latex]2, 4, 6, \ldots , 200[/latex], а разность соответствующих средних равна [latex](N — 200) : 100[/latex]. Так как эта разность больше [latex]1[/latex], получаем [latex]N \geq 301[/latex]. Нетрудно убедиться, что цикл [latex] A_{1}A_{3}A_{5} \ldots A_{301}A_{2}A_{4} \ldots A_{300}[/latex] удовлетворяет условиям задачи. Пусть теперь выполнено второе условие, т.е. имеются два цикла, каждый из которых включает всех пассажиров с билетами на места одной четности. Если в каком-нибудь из этих циклов пассажир [latex]A_{n}[/latex] сидит не на [latex](n + 2)[/latex]-м месте, а [latex]A_{n+2}[/latex]– не на [latex]n[/latex]-м месте, то в цикле не менее [latex]202[/latex] пассажиров, а в аэробусе – не менее [latex]403[/latex] мест. В противном же случае имеем (с точностью до направления) цикл [latex]A_{1}A_{3}A_{5} \ldots A_{N}[/latex] , где пассажиры с билетами на места [latex]1,3, 5, \ldots , 199[/latex] сидят на местах [latex]N, 1, 3, \ldots , 197[/latex]; разность соответствующих средних арифметических [latex] (N — 199) :100[/latex] больше [latex]1[/latex], откуда [latex]N \geq 301[/latex].

С.Токарев