Всего: 223 1–20 | 21–40 | 41–60 | 61–80 | 81–100 …
Добавить в вариант
2.3 Докажите, что если 
прямой, то C и D совпадают с точками касания окружностей и угла.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Выполним инверсию i относительно центра окружности с центром в A и радиусом AB. Имеем 
и наши две окружности превращаются в прямые BC, BD, образующие прямой угол, а стороны исходного угла — в пару окружностей, вписанных в этот угол, перпендикулярных друг другу (как и соответствующие прямые до инверсии) и пересекающихся в точках A, i(R). Вычислим отношение их радиусов — это легко делается применением теоремы Пифагора к треугольнику AO1O2 со сторонами r1, r2, 
(O1, O2 — центры новых окружностей, 
—
будем считать 
Введём связанную с нашим прямым углом систему координат, тогда центры имеют координаты (1, 1) и 
а точки касания:
Середина 
—
и считая расстояние от неё до O1, O2 убеждаемся, что это точка пересечения наших окружностей, как и середина 
Значит, эти середины — точки A, i(R). Поскольку A не лежит на биссектрисе угла, то прямая, из которой наш угол высекает отрезок с серединой A — единственна, так что соответствующая пара точек X, Yi совпадает с
Приведём другой способ (без инверсии).
Из условия легко следует, что радиусы окружностей перпендикулярны: отрезки AC и AD симметричны AB относительно соответствующих радиусов, а C, A, D лежат на одной прямой.
Кроме того, из этой симметричности ясно, что такие точки C и D единственны. Значит, если покажем, что точки касания подходят на их роль, мы победим. Пусть радиус маленькой окружности равен 1, большой — R. Тогда из теоремы Пифагора 
у этого уравнения ровно одно решение, где 
Пусть C′, D′ — точки касания первой и второй окружностей разных сторон угла. Введём систему координат параллельно сторонам угла, тогда 
Пусть A′ — середина этого отрезка, тогда не очень трудно проверить, что она лежит на обеих
То есть можно считать 
Осталось убедиться, что
Тогда
(последнее равенство можно проверить, возведя в квадрат). По симметрии точка B имеет координаты 
значит,
Ура!
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна 
а сумма соответствующих углов между хордой и касательной 
2.4 Какие значения может принимать угол RAO1, где O1 — центр меньшей окружности?
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Исполним ту же самую инверсию, что и в предыдущем пункте, вновь получим прямой угол и вписанную в него пару окружностей. Прямая AS пересекает стороны угла под 45 градусов, значит, то же делает эта же прямая 
с исходными окружностями. Поэтому и угол RAO (O — центр меньшей окружности) равен 
Ответ: 45°.
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
3.3. Докажите, что искомая пара найдётся при 
Сюжет 3.
В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа а и простого натурального числа p справедливо соотношение «a−a p делится на p без остатка».
Итак, 
—
значения, дающие одинаковые остатки от деления на p.
Случаи 
разбираются руками. Дальше, аналогично предыдущим пунктам, если 
то всё ясно. 
получаем
Если бы остатки не повторялись, каждый бы встречался по разу, и тогда их сумма была бы равна 0. Но тут, как мы видим, их сумма равна
3.1 Пусть a = 4, b = 9. Докажите, что искомая пара найдётся.
По МТФ 
но в то же время и
3.4 Докажите, что у него получится, если 
— простое, a = 2 и b = 3.
Сюжет 3.
В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа а и простого натурального числа p справедливо соотношение «a−a p делится на p без остатка».
Итак, —
значения, дающие одинаковые остатки от деления на p.
Лемма 1. Пусть 
простое 
таково, что для любого 
число xu остаток kx от деления на q имеют разную чётность. Тогда 
Доказательство леммы 1. Подставляя 
получаем, что k чётно, а значит kx всегда чётно, тогда остаток kx имеет ту же четность, что и неполное частное 
Теперь подставляем 
тогда 
и нечетно, то есть 
Теперь подставляем 
тогда 
и 
четно, то етсь 
Продолжая это, доходим до равенства
что невозможно при 
значит, 
Следствие 1. Пусть q простое, k нечётное, 
не кратно 2q. Тогда найдется l такое, что у обоих чисел l, kl остатки по модулю 2q строго между 0 и q.
Доказательство. Действительно, попробуем в качестве l все числа от 1 до 
Пусть все пары l, kl не подошли, то есть все kl имеют остатки по модулю 2q, большие q. Это значит, что чётность остатка kl по модулю q противоположна четности остатка kl по модулю 2q (q — нечётно), а она совпадает с четностью l (т. к. k нечётно) и мы попадаем в условия леммы.
Перейдём к решению задачи. Предположим, что все остатки различны. Посмотрим, на порядки 2 и 3 по модулю p. По МТФ они могут быть равны лишь 1, 2, q, 
(порядок a по модулю p — минимальное натуральное k такое, что 
(или числитель соответствующей несократимой дроби, если a — дробь) кратно p, это k мы будем обозначать 
Первые два случая проигнорируем, а случаи, когда хотя бы один из порядков равен q идентичны разобранным в пунктах 1 и 3. Пусть порядки 2q, в частности все остатки 
различны (иначе, если 2a и 2b дают одинаковые остатки, то 
а значит и 
кратно p, но 
и найдётся такое m, что 
Отметим также, что в этом случае 
так что если при некотором k имеем 
то и
так что нарушается условие различности остатков. Поэтому в нашей последовательности встречаются по разу все ненулевые остатки.
Подберём по следствию 1 такое 
что −ml при делении на 2q имеет остаток меньше q, назовём этот остаток r, 
делится на 2q.
Теперь изучим сумму
по модулю p. С одной стороны, выражение в скобках пробегает все ненулевые остатки, а число 
не 
и она равна нулю.
Посчитаем эту же сумму другим способом. Раскрыв все скобки по биному, перегруппировав слагаемые и переставив множители в показателях степеней, мы получим сумму геометрических прогрессий вида
Докажем, что ровно одна из этих прогрессий постоянна, а значит, ровно одно из указанных выражений ненулевое (тут надо отметить, что 
так что 
поэтому появляющиеся биномиальные коэффициенты не кратны p). Это даст требуемое противоречие.
Действительно, при 
получаем, учитывая 
что 
так как 
делится на 2q. С другой стороны, если 
при некотором 
то, деля, получаем 
то есть 
Получаем, что
значит, 
равен 1 или 2, что может быть лишь при 
этот случай проверяется непосредственно.
3.1 Пусть a = 4, b = 9. Докажите, что искомая пара найдётся.
По МТФ но в то же время и
1.1 Докажите, что в любой момент может произойти миграция.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меныше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
1.2 Пусть схема островов и коридоров устроена так, как показано на рисунке. Докажите, что при любом начальном расселении колоний существует способ организовать миграции так, что по итогам менее чем 1000 миграций на острове A появится колония. При решении этого пункта можно без доказательства пользоваться результатом пункта 1.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Сопоставим вершинам нижнего уровня вес 1, следующего уровня — 2, далее 5, 12, и наконец, 27. Заметим, что при каждом переселении не из вершины A суммарный вес всех колоний увеличивается (ровно на 1). Изначальный суммарный вес 
Значит, не более чем после 
миграций хотя бы одна колония окажется в корне.
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
2.1 Докажите, что касательные к окружностям в точке A перпендикулярны.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Заметим, что радиусы в точку A являются биссектрисами смежных углов DAB и CAB; следовательно, радиусы перпендикулярны. Но тогда перпендикулярны и касательные.
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
2.2 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Замечаем, 
и 
так как равны половине дуг AD и AC соответственно (вписанный угол и угол между касательной и хордой равны половине дуги, в них заключенной). Треугольник BCD прямоугольный (медиана — половина гипотенузы). Следовательно, 
поэтому
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
3.1 Найдите a(1, 5).
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Пусть 
—
(чтобы покрыть карточку 
(чтобы покрыть карточку 
аналогично 
Заметим, что карточка 
подходит, поскольку на любой карточке наибольшее число не превосходит 1, следующее не 
Ответ: 
1.1 Найдите a (2, 2).
Пример: наборы 
и 
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа 
Если это одна и та же пара, то сумма уже 
Если разные, то посмотрим на набор 
чтобы набор 
мажорировал его, должно быть 
а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ: 
3.2 Найдите a(n, 2).
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Пара чисел, в сумме дающая 1, однозначно кодируется большим из них, т. е., произвольным числом l из отрезка 
Из пары чисел вида 
где 
можно (вычтя из обоих чисел в паре что-то с суммой 
получить, в лучшем случае, пары в которых 
то есть интервал длины 
Такими интервалами мы должны закрыть весь отрезок длины откуда оценка 
то есть 
Отсюда ясно и как построить пример: подойдёт набор
Ответ: 
1.1 Найдите a (2, 2).
Пример: наборы и
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа Если это одна и та же пара, то сумма уже Если разные, то посмотрим на набор чтобы набор мажорировал его, должно быть а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ:
1.3 Докажите, что как бы колонии тупиков ни располагались изначально, миграциями можно расселить колонии по одной на остров.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Индукция по числу вершин.
База тривиальна.
Переход. Докажем, что в любой вершине можно получить не 0, обобщив рассуждение из пункта 2. Подвесим дерево за эту вершину. Рассмотрим такой полуинвариант: сумма по всем вершинам величин 
где xi — число в вершине, di — её глубина в подвешенном дереве. Легко видеть, что каждая миграция не из корня дерева отдаёт единичку наверх и менее n на уровень вниз, то есть сумма строго увеличивается. Но всех возможных сумм конечное число, так что рано или поздно будет возможна миграция только из корня, а это значит, что там не 0.
Теперь, собственно, переход. Рассмотрим лист v, при необходимости делаем там не 0 (мы только что доказали, что это возможно). Теперь отдаём из v всё, кроме 1, его соседу u. Рассмотрим последовательность миграций, делающую единички в дереве без v (она берётся из индукционного предположения). Применим её, только перед каждой миграцией из u будем отдавать туда 1 из v.
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
1.4 Пусть изначально на каждом острове обитает одна колония, и пусть один из островов имеет d соседних. Чему может равняться максимально возможное количество колоний, способных поселиться на этом острове?
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Пример. Докажем, что в вершине степени d может собраться 
колония. Подвесим дерево за эту вершину как за корень и будем доказывать, что в каждой вершине, из которой вниз идет e рёбер, можно собрать 
колонию, проводя только миграции в её поддереве. Докажем это «индукцией от нижних вершин к верхним». Для листьев утверждение очевидно (в них и так есть одна колония), а в для любой другой вершины достаточно собрать нужное количество колоний в её непосредственных потомках, после чего проделать по одной миграции для каждого из них.
Оценка. Покажем, что любое доступное распределение чисел на дереве можно получить, организуя миграции так, чтобы каждая колония уходила не дальше, чем на соседний остров. Из этого будет следовать, что ответ не больше 
Доказываем индукцией по числу миграций. База — ноль миграций, очевидна.
Переход. Пусть вот-вот произойдёт миграция с острова v. По ИП все находящиеся на нем колонии — с него и соседних островов. Раз можно мигрировать, по ИП на острове есть колонии хотя бы с 
соседних островов; отправим их обратно на свои острова. Если есть колония с оставшегося соседнего острова, тоже отправим её обратно, если есть своя колония, отправим её на любой из соседних островов
Ответ:
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
2.3 Пусть C и D совпали с точками касания окружностей и угла. Чему может быть равен угол ADR?
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Треугольник RAB равносторонний: 
и 
по симметрии относительно биссектрисы угла R. Отсюда симметричные отрезки RA, RB образуют со сторонами углы, равные
и этому же равен 
Ответ: 15°.
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
2.4 Докажите, что если прямой, то C и D совпадают с точками касания окружностей и угла.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Так как 
то AC и AD должны быть симметричны AB относительно радиусов соответствующих окружностей. Из этой симметричности ясно, что такие точки C и D единственны. Значит, если мы покажем, что точки касания подходят на их роль, мы победим. Пусть радиус маленькой окружности равен 1, большой — R. Тогда из теоремы Пифагора для 
получим:
У этого уравнения ровно одно решение, где 
а именно 
Пусть C′, D′ — точки касания первой и второй окружностей разных сторон угла. Введём систему координат параллельно сторонам угла, тогда Пусть A′ — середина этого отрезка, тогда не очень трудно проверить, что она лежит на обеих
То есть можно считать Осталось убедиться, что
Тогда
(последнее равенство можно проверить, возведя в квадрат). По симметрии точка B имеет координаты значит,
Ура!
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
3.3 Докажите, что найдётся n такое, что 
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Рассмотрим все возможные способы записать число 
в виде суммы положительных рациональных дробей со знаменателем 
(не обязательно несократимых). Очевидно, что это количество конечно, его и обозначим за n — записав все соответствующие наборы на карточки, убедимся, что такой набор карточек подходит. Действительно, рассмотрим любой набор с единичной суммой. Заменим в нём каждое число на ближайшую сверху дробь со знаменателем 
При таком округлении сумма увеличится не более, чем на
значит, получится один из наших наборов или аналогичный набор с меньшей суммой. Произвольно увеличив числители некоторых дробей так, чтобы сумма стала равной 
мы превратим набор в числа на одной из карточек, которая, таким образом, мажорирует исходный набор с единичной суммой.
1.1 Найдите a (2, 2).
Пример: наборы и
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа Если это одна и та же пара, то сумма уже Если разные, то посмотрим на набор чтобы набор мажорировал его, должно быть а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ:
3.4 Докажите, что найдётся k такое, что 
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Пусть имеется подходящий набор из 
карточек. Упорядочим на каждой карточке числа по убыванию. Для любого 
мы должны уметь мажорировать набор, состоящий из l чисел равных 
и 
нулей, поэтому для каждого такого l должна найтись карточка, в которой 
Подчеркнём соответствующие числа — тогда сумма всех чисел на карточках не меньше суммы подчеркнутых, т. е. суммы
Как известно, найдётся k для которого такая сумма больше 
значит, сумма чисел на отдельной карточке должна быть больше
1.1 Найдите a (2, 2).
Пример: наборы и
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа Если это одна и та же пара, то сумма уже Если разные, то посмотрим на набор чтобы набор мажорировал его, должно быть а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ:
1.1 Можно ли из тройки с числами 2, 4, 7 получить тройку чисел 2, 6, 9 в каком-нибудь порядке?
Сюжет 1
На доске написана тройка целых чисел. Разрешается менять написанную на доске тройку (a,b,c) на тройку (f(a),f(b),f(c)), где f — квадратный трехчлен с целыми коэффициентами, произвольное количество раз (при этом можно брать различные f на разных шагах).
Если f — многочлен с целыми коэффициентами, то 
делится на 
при любых целых x, y. Теперь заметим, 
где 
— применяемые трехчлены, каждый член делится на предыдущий, а значит и на самую первую разность).
Ответ: нет.
1.2 Можно ли из тройки (1, 4, 7) получить (1, 10, 7) (числа именно таком порядке)?
Пусть какая-то последовательность трехчленов переводит (1, 4, 7) в (1, 10, 7). Несложно видеть, что одного такого трехчлена не существует (если этот трехчлен — 
то, подставляя мы получаем, например, систему: 
откуда, например, 
Предположим (x, y, z) — промежуточная тройка. 
должно делиться на 6 (из (1,7) получается (x, z)) и быть делителем 6 
не умаляя общности, можно считать 
(поменять знаки у всей тройки можно всегда). Аналогично, 
поэтому наша тройка имеет вид 
или 
то есть, с точностью до прибавления константы, совпадает либо с начальной тройкой, либо с конечной. Противоречие (например, если мы предположим, что имеем дело с кратчайшей последовательностью операций, тогда например в переходе
первый переход можно включить в последующие — противоречие с минимальностью).
Ответ: нет.
1.2 Можно ли из тройки (1, 4, 7) получить (1, 10, 7) (числа именно таком порядке)?
Сюжет 1
На доске написана тройка целых чисел. Разрешается менять написанную на доске тройку (a,b,c) на тройку (f(a),f(b),f(c)), где f — квадратный трехчлен с целыми коэффициентами, произвольное количество раз (при этом можно брать различные f на разных шагах).
Пусть какая-то последовательность трехчленов переводит (1, 4, 7) в (1, 10, 7). Несложно видеть, что одного такого трехчлена не существует (если этот трехчлен — то, подставляя мы получаем, например, систему: откуда, например,
Предположим (x, y, z) — промежуточная тройка. должно делиться на 6 (из (1,7) получается (x, z)) и быть делителем 6 не умаляя общности, можно считать (поменять знаки у всей тройки можно всегда). Аналогично, поэтому наша тройка имеет вид или то есть, с точностью до прибавления константы, совпадает либо с начальной тройкой, либо с конечной. Противоречие (например, если мы предположим, что имеем дело с кратчайшей последовательностью операций, тогда например в переходе
первый переход можно включить в последующие — противоречие с минимальностью).
Ответ: нет.
1.1 Можно ли из тройки с числами 2, 4, 7 получить тройку чисел 2, 6, 9 в каком-нибудь порядке?
Если f — многочлен с целыми коэффициентами, то делится на при любых целых x, y. Теперь заметим, где — применяемые трехчлены, каждый член делится на предыдущий, а значит и на самую первую разность).
Ответ: нет.
1.3 Докажите, что если тройку (x,y,z) можно получить из тройки (a,b,c) многократным применением указанных операций, то то же можно сделать и за одну операцию.
Сюжет 1
На доске написана тройка целых чисел. Разрешается менять написанную на доске тройку (a,b,c) на тройку (f(a),f(b),f(c)), где f — квадратный трехчлен с целыми коэффициентами, произвольное количество раз (при этом можно брать различные f на разных шагах).
Попытаемся получить (x, y, z) за одну операцию. Нужный результат даст многочлен
(это интерполяция по Ньютону: первое слагаемое устанавливает значение x в точке a, второе, сохраняя его, устанавливает значение y в точке b, наконец третье устанавливает значение z в точке 
не меняя значений при 
и 
Если оба числа
являются целыми числами, то коэффициенты P целые, а значит (x, y, z) достижим из (a, b, c) за один ход.
Теперь покажем, что если (x, y, z) можно получить из тройки (a, b, c) за много операций, то эти числа и вправду целые-отсюда будет следовать нужное утверждение. Действительно, пусть мы получили (x, y, z) применяя
это тоже многочлен, причём 
Тогда число 
—
То, что это целое число, легко проверяется явным вычислением. Заметим, например (больше для краткости записи), что эту целость достаточно проверять для мономов, т. е для случая 
(при сложении одночленов интересующие нас дроби будут тоже складываться). Имеем
что является целым числом.
1.1 Можно ли из тройки с числами 2, 4, 7 получить тройку чисел 2, 6, 9 в каком-нибудь порядке?
Если f — многочлен с целыми коэффициентами, то делится на при любых целых x, y. Теперь заметим, где — применяемые трехчлены, каждый член делится на предыдущий, а значит и на самую первую разность).
Ответ: нет.
1.4 Верно ли, что четверку (1, 2, 3, 4) можно превратить в четвёрку (19999, 29999, 39999, 49999) применением аналогичных операций над четвёрками?
Сюжет 1
На доске написана тройка целых чисел. Разрешается менять написанную на доске тройку (a,b,c) на тройку (f(a),f(b),f(c)), где f — квадратный трехчлен с целыми коэффициентами, произвольное количество раз (при этом можно брать различные f на разных шагах).
Посмотрим по модулю 5 : (1, 2, 3, 4) должна перейти в (1, 3, 2, 4). Пусть хотя бы у одного из использованных квадратных трёхчленов (скажем, 
старший коэффициент не делится на 5. Перейдем в вычеты по модулю 5, и указанный трехчлен преобразуется к виду
поэтому его применение склеивает две различные пары остатков (с суммой 
(здесь всюду деление остатков по модулю 5), это значит, что он не может перевести четыре различных остатка в четыре различных, а значит и его композиция со всеми последующими трехчленами тоже не может.
Значит, единственная возможность — если у всех использованных трехчленов, старший коэффициент делится на 5, то есть по модулю 5 применяется просто линейная функция. Но тогда и их композиция — линейная по модулю 5. Однако 
очевидно, не линейная функция.
Замечание. Для четвёрок чисел аналог п. 3, как легко видеть, неверен.
Ответ: нет, нельзя.
1.1 Можно ли из тройки с числами 2, 4, 7 получить тройку чисел 2, 6, 9 в каком-нибудь порядке?
Если f — многочлен с целыми коэффициентами, то делится на при любых целых x, y. Теперь заметим, где — применяемые трехчлены, каждый член делится на предыдущий, а значит и на самую первую разность).
Ответ: нет.
Наверх