Двадцатый международный математический Турнир Городов, 1998-1999

Осенний тур

Редактор текста В. О. Бугаенко (bugaenko@mccme.ru), составитель HTML-версии А. К. Кулыгин (kuligin@mccme.ru). Просим сообщать все Ваши замечания и предложения.

Содержание

Весенний тур 1999 года состоится:

• тренировочный вариант - 21 февраля 1999 года
• основной вариант - 28 февраля 1999 года

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

Задача 1.(3)
Куб со стороной 20 разбит на 8000 единичных кубиков, и в каждом кубике записано число. Известно, что в каждом столбике из 20 кубиков, параллельном ребру куба, сумма чисел равна 1 (рассматриваются столбики всех трех направлений). В некотором кубике записано число 10. Через этот кубик проходит три слоя 1*20*20, параллельных граням куба. Найдите сумму всех чисел вне этих слоев.

Решение.

Куб состоит из 400 столбиков, поэтому сумма всех чисел равна 400. Любой слой состоит из 20 столбиков, поэтому сумма чисел в нем равна 20.

Чтобы получить искомую сумму, следует из суммы чисел во всём кубе вычесть суммы чисел в трёх слоях, проходящих через данный кубик, затем прибавить суммы чисел в трёх проходящих через него столбиках, являющихся попарными пересечениями этих слоёв (поскольку мы их вычли дважды - с каждым из двух слоёв), и, наконец, вычесть число, стоящее в данном кубике (так как мы его учли изначально, затем трижды вычли и трижды прибавили).
Итого имеем: 400-3*20+3*1-10=333.

Задача 2.(3)
Квадрат целого числа имеет вид ...09 (оканчивается цифрами 0 и 9).
Докажите, что третья справа цифра - четная.

Решение.

Данный квадрат при делении на 200 даёт остаток 9, если третья справа цифра чётная, или 109, если она нечётная. Докажем, что квадрат целого числа не может при делении на 8 давать в остатке 5, тем самым, второй случай невозможен. Ясно, что такое число должно быть нечётным и поэтому иметь вид либо 8k+1, либо 8k+3.

Однако, (8k+1)²=8(8k²+2k)+1, а (8k+3)²=8(8k²+6k+1)+1. Поэтому квадрат любого нечётного числа при делении на 8 даёт остаток 1.

Задача 3.(4)
В треугольнике ABC точки A', B', C' лежат внутри сторон BC, CA и AB соответственно. Известно, что угол AC'B' = углу B'A'C, угол CB'A' = углу A'C'B, угол BA'C' = углу C'B'A.
Докажите, что точки A', B', C' - середины сторон.

Решение.

Углы AC'A' и AB'A' равны, так как дополняют до 180^o равные углы CB'A' и A'C'B. Углы B'AC' и B'A'C' равны, так как дополняют до 180^o равные суммы C'B'A+AC'B' и BA'C'+B'A'C. Значит, AB'A'C' - параллелограмм, следовательно, AC'=B'A'. Аналогично доказывается, что BA'B'C' - параллелограмм, и C'B=B'A'. Отсюда следует, что AC'=C'B, т.е. C' - середина AB. Для точек B' и A' доказательство аналогично.

Задача 4.(4)
12 кандидатов в мэры рассказывали о себе. Через некоторое время один сказал: "До меня соврали один раз". Другой сказал: "А теперь - дважды". "А теперь - трижды" - сказал третий, и так далее до 12-го, который сказал: "А теперь соврали 12 раз". Тут ведущий прервал дискуссию. Оказалось, что по крайней мере один кандидат правильно посчитал, сколько раз соврали до него. Так сколько же раз всего соврали кандидаты?

Решение.

Предположим, что первый кандидат соврал. Это значит, что до его утверждения количество ложных высказываний не равнялось 1. После его высказывания это количество увеличилось на 1, поэтому стало не равным 2. Следовательно, второй кандидат тоже соврал. Продолжая такие же рассуждения, получаем, что все кандидаты соврали, а это противоречит условию задачи.

Значит, первый кандидат сказал правду. Тем самым, как до, так и после его высказывания количество ложных утверждений равнялось 1. Поэтому второй кандидат соврал. Далее, рассуждая аналогично получаем, что и все последующие тоже соврали. Итак, соврали все кандидаты, кроме первого, и ещё одна ложь прозвучала до описываемой дискуссии. Поэтому всего кандидаты соврали 12 раз.

Задача 5.(5)
Назовем крокодилом шахматную фигуру, ход которой заключается в прыжке на m клеток по вертикали или по горизонтали, и потом на n клеток в перпендикулярном направлении.
Докажите что для любых m и n можно так раскрасить бесконечную клетчатую доску в 2 цвета (для каждых конкретных m и n своя раскраска), что всегда 2 клетки, соединенные одним ходом крокодила, будут покрашены в разные цвета.

Решение.

Предположим сначала, что числа m и n взаимно простые. Рассмотрим два случая. Первый случай: числа m и n разной чётности, т. е. одно чётное, а другое нечётное. Тогда искомой будет обычная шахматная раскраска. Второй случай: числа m и n оба нечётные. Тогда раскрашивать доску нужно полосами шириной в одну клетку, чередуя цвета полос.

Пусть теперь m и n имеют наибольший общий делитель d > 1. Разобьем доску на квадратные блоки размером d*d клеток. Будем закрашивать доску блоками, считая каждый такой блок за отдельную клетку, для случая хода крокодила на m/d клеток в одном направлении, и на n/d клеток - в перпендикулярном. Поскольку числа m/d и n/d взаимно простые, мы это делать уже умеем.

Задача 1.(3)
Имеется 19 гирек весом 1г, 2г, 3г, ... , 19 г. Девять из них - железные, девять - бронзовые и одна - золотая. Известно, что общий вес всех железных гирек на 90 г больше, чем общий вес бронзовых.
Найдите вес золотой гирьки.

Решение.

Бронзовые гирьки весят не меньше, чем 1+2+...+9=45 г, а железные - не больше, чем 11+12+...+19=135 г. Если бы хотя бы одно из этих неравенств было строгим, то вес железных гирек превышал бы вес бронзовых гирек более, чем на 90 г. Значит, бронзовые гирьки весят 45 г, а железные - 135 г, а это возможно только если девять самых легких гирек - бронзовые, а девять самых тяжелых - железные. Поэтому золотая гирька весит 10 г.

Задача 2.(3)
n бумажных кругов радиуса 1 уложены на плоскость таким образом, что их границы проходят через одну точку, причем эта точка находится внутри всей области плоскости, покрытой кругами. Эта область представляет собой многоугольник с криволинейными сторонами.
Найдите его периметр.

Решение.

Обозначим точку пересечения окружностей через O. Проведём отрезки из точки O в вершины получившегося криволинейного многоугольника. Стороны многоугольника представляют собой дуги окружностей; по теореме о вписанном угле, величина каждой дуги равна удвоенному углу между отрезками, проведёнными из точки O в её концы. В сумме все эти углы составляют 360^o, поэтому сумма величин всех дуг равна 720^o, т. е. двум полным окружностям. Значит, сумма длин дуг равна 4p; это и есть искомый периметр.

Задача 3.(4)
На шахматной доске размером 8*8 отметили 17 клеток.
Докажите, что из них можно выбрать две так, что коню нужно не менее трех ходов для попадания с одной из них на другую.

Первое решение.

Рассмотрим фигуру, изображённую на рис. 1.

Рисунок 1.
Легко проверить, что путь коня от любой из четырёх клеток этой фигуры до любой другой состоит не менее, чем из трёх ходов. Шестнадцатью такими фигурами можно замостить всю доску (рис. 2).

Рисунок 2.
По принципу Дирихле одна из этих шестнадцати фигур содержит по крайней мере две отмеченные клетки. Они и будут искомыми.

Второе решение.

Пусть на доске отмечены несколько клеток так, что шахматный конь может пройти с любой из них на любую, затратив не более двух ходов. Разобьем множество чёрных клеток на 8 частей по 4 клетки, как на рис. 3 (при разбиении получаются фигуры двух типов, причём, чтобы пройти из любой клетки в любую другую клетку той же фигуры, требуется не менее трёх ходов коня).

Рисунок 3.
Значит, каждая фигура содержит не более одной отмеченной клетки, поэтому среди отмеченных клеток не более 8 чёрных. Аналогично доказываем, что отмечено не более 8 белых. Поэтому, общее количество отмеченных клеток не больше 16.

Оказывается, условие задачи остаётся верным, если заменить число 17 на 9. Докажем это. Если белых клеток не отмечено совсем или отмечена только одна, то, поскольку чёрных клеток не больше 8, утверждение доказано. Пусть отмечено две белых клетки. Выберем любую из них. Тогда все чёрные клетки лежат на расстоянии одного хода коня от неё, так как от чёрной клетки до белой конь может дойти только за нечётное количество ходов. Поэтому центры всех чёрных клеток находятся на одной окружности с центром в выбранной белой клетке. То же самое верно и для второй отмеченной белой клетки. Так как две окружности пересекаются не более, чем в двух точках, то чёрных клеток не более двух. Получаем всего четыре отмеченных клетки. Наконец, если отмечено более двух белых клеток, то чёрных клеток можно отметить только одну, поскольку три окружности могут пересекаться только в одной точке. И в этом случае общее количество отмеченных точек не больше 9.

Заметим, что если заменить число 9 меньшим, то условие перестанет быть верным. Действительно, отметив одну из клеток центрального квадрата 4*4 и 8 клеток, находящихся от нее на расстоянии хода коня, получим, что коню нужно не более двух ходов, чтобы попасть из любой отмеченной клетки в любую другую.

Задача 4.(4)
Рассматриваются такие наборы действительных чисел {x₁, x₂, x₃, ... x₂₀}, заключенных между 0 и 1, что
x₁*x₂*x₃*...*x₂₀ = (1-x₁)*(1-x₂)*(1-x₃)*...*(1-x₂₀).
Найдите среди этих наборов такой набор, для которого значение
x₁*x₂*x₃*...*x₂₀ максимально.

Решение.

Для любого числа 0 < x < 1 выполняется неравенство x(1-x)< 1/4 (это неравенство Коши о среднем арифметическом и среднем геометрическом, примененное к числам x и 1-x), причём равенство выполняется только при x=1/2. Записав это неравенство для
x = x₁, x₂, ..., x₂₀ и перемножив полученные неравенства, имеем

x₁x₂...x₂₀(1-x₁)(1-x₂)...(1-x₂₀)< 4^-20, откуда, принимая во внимание условие, получаем
(x₁x₂...x₂₀)²< 4^-20, или
x₁x₂...x₂₀< 2^-20. Равенство выполнено при x₁=x₂=...=x₂₀=1/2, это и есть искомый набор.

Задача 5.(1+3+2)
Группа психологов разработала тест, пройдя который, каждый человек получает оценку - число Q - показатель его умственных способностей (чем больше Q, тем больше способности). За рейтинг страны принимается среднее арифметическое значений Q всех жителей этой страны.
а).(1) Группа граждан страны А эмигрировала в страну Б.
Покажите, что при этом у обеих стран мог вырасти рейтинг.
б).(3) После этого группа граждан страны Б (в числе которых могут быть и бывшие эмигранты из А) эмигрировала в страну А.
Возможно ли, что рейтинги обеих стран опять выросли?
в).(2) Группа граждан страны А эмигрировала в страну Б, а группа граждан Б - в страну В. В результате этого рейтинги каждой страны оказались выше первоначальных. После этого направление миграционных потоков изменилось на противоположное - часть жителей В переехала в Б, а часть жителей Б - в А. Оказалось, что в результате рейтинги всех трех стран опять выросли (по сравнению с теми, которые были после первого переезда, но до начала второго). (Так, во всяком случае, утверждают информационные агентства этих стран.)
Может ли такое быть (если да, то как, если нет, то почему)?
(Предполагается, что за рассматриваемое время Q граждан не изменилось, никто не умер и не родился).

Решение. Докажем следующее интуитивно очевидное утверждение.

Лемма. Если объединить две группы людей с рейтингами R₁ и R₂ (R₁< R₂), то рейтинг R получившейся группы будет удовлетворять условию R₁< R< R₂.

Действительно, если Q'₁, Q'₂, ..., Q'_n - показатели людей из первой группы, а Q''₁, Q''₂, ..., Q''_m - показатели людей из второй группы, то

(n+m)R=Q'₁+...+Q'_n+Q''₁+...+Q''_m=nR₁+mR₂

Так как R₁< R₂, то R=(n/(n+m))R₁+(m/(n+m))R₂< (n/(n+m))R₂+(m/(n+m))R₂=R₂, и аналогично R>R₁, причём равенство в обоих случаях достигается тогда и только тогда, когда R₁=R₂.
Лемма доказана.

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

Аналогично, если рейтинг страны ниже (соответственно, равен или выше) рейтинга группы иммигрантов, то после иммиграции он повышается (соответственно, остается прежним или понижается), но по прежнему остается ниже (соответственно, равен или выше) рейтинга группы иммигрантов.

Пример для пункта а) теперь строится просто. Достаточно, чтобы из А в Б эмигрировал всего один человек, имеющий показатель Q ниже, чем рейтинг страны А, но выше, чем рейтинг страны Б.

Такая ситуация возможна только если рейтинг страны А выше рейтинга страны Б, причём это же остается справедливым и после миграции. Но тогда, согласно лемме, невозможно, чтобы после обратной миграции из Б в А рейтинги обеих стран снова повысились. Поэтому, ответ в пункте б) отрицательный.

В пункте в) ответ положительный. Приведем пример такой ситуации. Пусть в стране А всего два жителя с показателями (Q=1 и 3), в стране Б - пять жителей (Q=4, 4, 6, 6 и 55), в стране В - один житель (Q=1). При первой волне эмиграции из А в Б эмигрировал один человек с Q=1, а из Б в В - двое с Q=4. При второй волне из В в Б переехал один человек с Q=1, а из Б в А - двое с Q=6. Рейтинги стран при этом менялись так: А - 1->3->5; Б - 15->17->19; С - 1->3->4.

Заметим, что для промежуточной страны Б рейтинг группы иммигрантов ниже рейтинга группы эмигрантов, однако, рейтинг самой страны Б при миграции все равно повышается.

Задача 1.(2+3)

а)(2) Докажите, что если НОК(a,a+5)=HOK(b,b+5) (a,b - натуральные), то a=b.
б)(3) Может ли НОК(a,b)=НОК(а+с,b+с) (a,b,c - натуральные)?

Решение.

a) Решение следует из решения пункта б). Действительно, пусть такие числа a не равно b существуют; без ограничения общности считаем, что a < b. Тогда тройка чисел a, a+5 и b-a, будет удовлетворять условиям пункта б) (если подставить их вместо a, b и c соответственно), невозможность чего доказывается ниже.

Другой способ см. в решении задачи 1 для 8-9 классов.

б) Предположим, что НОК(a,b)=НОК(а+с,b+с). Если числа a, b и c имеют общий делитель d, то сократим на него. При этом обе части рассматриваемого равенства тоже сократятся на d. Поэтому можно считать, что a, b и c взаимно просты. Тогда числа a+c и b+c тоже взаимно просты. Действительно, если они имеют общий простой делитель p, то на p делится также их разность a-b и НОК(а+с,b+с)=НОК(a,b). Значит на p делится одно из чисел a или b, тем самым, они оба (т. к. на p делится их разность). Но тогда и c делится на p, что противоречит взаимной простоте чисел a, b и c. Следовательно, НОК(a+c,b+c)=(a+c)(b+c)>ab>НОК(a,b). Противоречие доказывает, что указанное равенство невозможно.

Задача 2.(4)
Отрезок AB пересекает две равные окружности и параллелен их линии центров, причем все точки пересечения прямой AB с окружностями лежат между A и B. Через точку A проводятся касательные к окружности, ближайшей к A, через точку B - касательные к окружности, ближайшей к B. Оказалось, что эти четыре касательные образуют четырехугольник, содержащий внутри себя обе окружности.
Докажите, что в этот четырехугольник можно вписать окружность.

Решение. Смотрите решение задачи 3 для 8-9 классов (основной вариант).

Задача 3.(5)
В таблицу записано девять чисел:

a1	a2	a3
b1	b2	b3
c1	c2	c3

Известно, что шесть чисел - суммы строк и суммы столбцов таблицы - равны между собой:
a₁+a₂+a₃=b₁+b₂+b₃=c₁+c₂+c₃=a₁+b₁+c₁=a₂+b₂+c₂=a₃+b₃+c₃.
Докажите, что сумма произведений строк таблицы равна сумме произведений ее столбцов:
a₁*b₁*c₁+a₂*b₂*c₂+a₃*b₃*c₃=a₁*a₂*a₃+b₁*b₂*b₃+c₁*c₂*c₃.

Первое решение.

Обозначим через s сумму чисел любой строки или любого столбца таблицы. Тогда справедливы следующие равенства: a₃=s-a₁-a₂, b₃=s-b₁-b₂, c₁=s-a₁-b₁, c₂=s-a₂-b₂, c₃=a₁+a₂+b₁+b₂-s. Подставив полученные выражения для a₃, b₃, c₁, c₂ и c₃ в равенство, которое требуется доказать, получим соотношение между a₁, a₂, b₁, b₂ и s. Раскрыв скобки убеждаемся, что полученное (хотя и довольно громоздкое) равенство является тождеством.

Второе решение.

Пусть s=x+y+z, тогда

6xyz=s³-3s(x²+y²+z²)+2(x³+y³+z³).

Записав это тождество для троек чисел, составляющих строки таблицы, и сложив три полученных равенства, получим, что левая часть доказываемого равенства равна (1/6)(s³-3sp+2sq), где p - сумма квадратов всех чисел в таблице, q - сумма кубов, s - сумма чисел в любой строке. Сделав то же самое со столбцами, получаем такое же выражение для правой части.

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

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

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

Поэтому количество способов рассадки такое же, как количество способов выбрать множество везучих из 10 членов жюри. Каждого из них можно отнести к одной из двух категорий, поэтому искомое число равно 2¹⁰=1024.

Задача 5.(7) ("Багаж в Московском метрополитене")
Будем называть "размером" прямоугольного параллелепипеда сумму трех его измерений - длины, ширины и высоты.
Может ли случиться, что в некотором прямоугольном параллелепипеде поместился больший по размеру прямоугольный параллелепипед?

Ответ: не может.

Первое решение.

Пусть мы имеем прямоугольный параллелепипед P', лежащий внутри прямоугольного параллелепипеда P. Оценим двумя способами сумму l длин проекций трёх взаимно перпендикулярных рёбер параллелепипеда P' на три прямых, параллельных рёбрам параллелепипеда P.

С одной стороны, сумма проекций трёх взаимно перпендикулярных рёбер параллелепипеда P' на любое ребро параллелепипеда P не превосходит длины этого ребра. Действительно, проекция внутреннего параллелепипеда на любое ребро внешнего есть отрезок, концы которого - это проекции двух противоположных вершин. От одной из них до другой можно пройти по трём взаимно перпендикулярным рёбрам. Поэтому рассматриваемая проекция равна сумме проекций этих трех рёбер, она, очевидно не больше, чем длина ребра, на которое мы проецируем. Значит, l не превосходит размера параллелепипеда P.

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

Тем самым, размер внутреннего параллелепипеда не больше размера внешнего.

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

Наденем на каждую грань внутреннего многогранника "шапку". Шапкой мы назовём объединение всех лучей с вершинами на грани, перпендикулярных ей и направленных наружу многогранника. Другими словами, шапка - это множество точек, проекции которых на плоскость грани лежит внутри грани, и расположенных по другую сторону от этой плоскости, чем многогранник. Из выпуклости многогранника следует, что любая точка пространства лежит не более, чем в одной шапке.

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

Пусть прямоугольный параллелепипед с рёбрами a', b' и c' содержится внутри прямоугольного параллелепипеда с рёбрами a, b и c. Тогда согласно доказанному

2(a'b'+a'c'+b'c')< 2(ab+ac+bc).

Кроме того, диаметр (т. е. расстояние между двумя наиболее удалёнными точками) внутреннего параллелепипеда не превосходит диаметра внешнего. Диаметром прямоугольного параллелепипеда является длина его диагонали, поэтому, сравнивая квадраты диагоналей, имеем

a'²+b'²+c'²< a²+b²+c².

Сложив эти два неравенства, получаем

(a'+b'+c')²< (a+b+c)².

Значит,

a'+b'+c'< a+b+c.

Третье решение.

Назовём e-окрестностью фигуры F фигуру F_e, состоящую из точек, отстоящих на расстояние не больше e от хотя-бы одной точки фигуры F (в частности, F₀=F). Любая точка M из e-окрестности P_e многогранника P имеет один из следующих четырёх типов в зависимости от того, какое из следующих условий выполняется:
0) M лежит внутри P;
1) Ближайшая к M точка многогранника P принадлежит его грани;
2) Ближайшая к M точка многогранника P принадлежит его ребру;
3) Ближайшая к M точка многогранника P является его вершиной.

Найдем объём vol P_e e-окрестности P_e прямоугольного параллелепипеда P с ребрами a, b и c. Для этого разрежем его на четыре части P⁰, P¹, P² и P³, являющихся множествами точек указанных выше типов соответственно.

Объём P⁰ равен abc.
P¹ представляет собой объединение шести прямоугольных параллелепипедов, основания которых являются гранями параллелепипеда P, а высоты равны e, поэтому vol P¹=2(ab+ac+bc)e.
P² - это двенадцать "четвертушек" цилиндров радиуса e, высоты которых суть ребра параллелепипеда. Значит, vol P²=(a+b+c)pe².
P³ - это восемь "осьмушек" шара радиуса e (каждая "осьмушка" представляет собой пересечение октанта с вершиной в вершине параллелепипеда и шара радиуса e с центром в ней же. Поэтому vol P³=(4/3)pe³ - это объём шара радиуса e.

Окончательно имеем

vol P_e= (4/3)pe³+(a+b+c)pe²+2(ab+ac+bc)e+abc.

Если F'cF, то F'_ecF_e для любого e. Пусть P - прямоугольный параллелепипед с ребрами a, b и c, а P' - содержащийся в нём прямоугольный параллелепипед с ребрами a', b' и c'. Тогда для любого e параллелепипед P'_e содержится внутри P_e, и поэтому vol P'_e < vol P_e. Обе части этого неравенства - многочлены третьей степени от e с равными коэффициентами при старшем члене. Значит, коэффициент при e² в левой части не больше, чем коэффициент при e² в правой части. Это означает, a'+b'+c' < a+b+c, т. е. размер параллелепипеда P' не превосходит размера параллелепипеда P.

Задача 6.(8)
Дана функция f(x) = (x² + a*x + b)/(x² + c*x + d), где трехчлены x² + a*x + b и x² + c*x + d не имеют общих корней. Докажите, что следующие два утверждения равносильны:
1) найдется числовой интервал, свободный от значений функции;
2) f(x) представима в виде: f(x)=f₁(f₂(...f_n-1(f_n(x))...)), где каждая из функций f_i(x) есть функция одного из видов: k_i*x+b_i, x^-1, x².

Первое решение.

Прежде всего докажем, что любая дробно-линейная (т. е. имеющая вид f(x)=(ax+b)/(cx+d) ) функция, не являющаяся константой, представляется в виде композиции функций двух первых видов (линейных и взятия обратной величины).

Если c=0, то утверждение очевидно (функция является линейной). Если ad=bc, то функция является константой. В остальных случаях

(ax+b)/(cx+d)=f₁(f₂(f₃(x))),

где
f₁(t)=t+(a/c),
f₂(t)=t^-1,
f₃(t)=(c²/(bc-ad))t+(cd/(bc-ad)).

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

Докажем, что 2) => 1). (из утверждения 2) следует утверждение 1) )
Пусть данная функция f(x) представима в виде композиции линейных функций, взятия обратной величины и возведения в квадрат. Так как f(x) не является дробно-линейной, то возведение в квадрат обязательно присутствует. Поскольку квадрат функции принимает только неотрицательные значения, появляется интервал, свободный от значений функции. С другой стороны, присутствие интервала, свободного от значений функции, сохраняется, если мы применяем к ней линейную функцию или взятие обратной величины.

Теперь докажем, что 1) => 2).
Пусть имеется функция f(x), для которой найдется интервал, не содержащий ее значений. Опять считаем, что f(x) не константа.

Функцией, обратной к j(t)=t^-1, является она сама, а обратная функция к линейной (но не являющейся константой) - тоже линейная. Поэтому достаточно доказать, что квадрат некоторой дробно-линейной функции, представляется как композиция нескольких линейных функций и взятий обратной величины с данной функцией f(x).

Прежде всего вычитаем из f(x) единицу и обращаем дробь, получаем функцию вида (x²+cx+d)/(px+q). Далее, если p=0, то применяем линейную функцию qt+(c²)/4-d) и получаем полный квадрат (x+(c/2))². Если же p не равно 0, то делаем линейную замену переменных x'=x+(q/p) и получаем x'²+rx'+(s/px'). При этом s не равно 0, так как по условию числитель и знаменатель не имеют общих корней. Рассмотрим два случая.

Первый случай: s > 0, можно считать, что s=u². Применим функцию (pёu)t-(r/u) и сделаем новую замену x''=(x'/u). Получим

(x''²+1)/x''= 4/(1/(x''-1)+2)²+1)+2.

Второй случай: s < 0. Аналогично, получаем функцию (x''²-1)/x''. Непосредственно проверяем, что при любом l
уравнение (x''²-1)/x''=l имеет решение. Значит, не существует интервала, свободного от значений функции.

Второе решение.

Докажем только импликацию 1) => 2).

Для начала сведём задачу к случаю, когда множество значений функции f(x) ограничено. В самом деле, пусть f(x) не принимает значений из интервала (x₁,x₂), тогда функция

(f(x)-(x₁+x₂)/2)^-1 < 2/(x₂-x₁)

ограничена.

Докажем, что если четыре точки с координатами (a,b), (c,d), (a',b') и (c',d') лежат на одной прямой, то

(x²+ax+b)/(x²+cx+d)=j((x²+a'x+b')/(x²+c'x+d')), где j - дробно-линейная функция.

Действительно,

a=ma'+(1-m)c', b=mb'+(1-m)d',

c=na'+(1-n)c', d=nb'+(1-n)d',

откуда

(x²+ax+b)/(x²+cx+d)= (m((x²+a'x+b')/(x²+c'x+d'))+(1-m)) / (n((x²+a'x+b')/(x²+c'x+d'))+(1-n)).

Пусть f(x)=(x²+ax+b)/(x²+cx+d) - ограниченная функция, удовлетворяющая условию 1). Из ограниченности следует, что знаменатель не обращается в нуль, следовательно квадратный трёхчлен имеет отрицательный дискриминант (c² < 4d). Это значит, что точка (c,d) лежит "внутри" параболы y=x²/4. Проведём на координатной плоскости прямую, проходящую через точки (a,b) и (c,d). Она должна пересечь параболу; точки пересечения обозначим (a',b') и (c',d'). Тогда по доказанному утверждению f(x) выражается в виде дробно-линейной функции от (x²+a'x+b')/(x²+c'x+d'), а последняя дробь является квадратом дробно-линейной функции, так как и в числителе, и в знаменателе содержит квадратный трёхчлен с нулевым дискриминантом.

Отдельно следует рассмотреть случай, когда проведённая прямая пересекает параболу лишь в одной точке, т. е. является вертикальной. Тогда a=c, и этот случай легко разбирается.

Замечание. Строго говоря, утверждение задачи не вполне корректно и требует некоторого уточнения. Мы предполагаем, что равенство

(P(x)/Q(x))^-1=Q(x)/P(x) (*)

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

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

2) дополнить множество действительных чисел еще одним "числом" oo (бесконечность), удовлетворяющим естественным арифметическим свойствам a/oo}=0 и a/0=oo (при a не равном 0 или oo), и считать встречающиеся в задаче функции определенными и принимающими значения в таком расширении множества действительных чисел;

3) считать встречающиеся в задаче дроби P(x)/Q(x) не функциями, а формальными записями, над которыми можно производить арифметические операции по естественным правилам, в частности, взятие обратной величины определяется формулой (*); равенство функций на их общей области определения влечет в этом случае равенство формальных записей с точностью до умножения числителя и знаменателя на один и тот же множитель.