Обсуждение задач | Заочные Математические Олимпиады
Целые числа и многочлены
Главная страница ЗАОЧНЫЕ МАТЕМАТИЧЕСКИЕ ОЛИМПИАДЫ
Основу книги составляют задачи, предлагавшиеся на Всесоюзных заочных
математических олимпиадах и конкурсах Всесоюзной
заочной математической школы для учащихся 7—10 классов.
Скачать или посмотреть эту книгу онлайн в формате PDF можете на странице
Учебники Скачать.
Ниже можете просто ознакомится с текстовым содержанием книги. Но здесь формулы отображаются не корректно. Если книга вам понравиться, можете скачать её бесплатно по ссылке выше.
З а д а ч а 2-1. Ответ: ученик решал 13 задач.
Пусть х — количество правильно решенных задач,
у — неправильно решенных. Тогда 8л: — 5у = 13. Переписав
это уравнение в виде
8 С* + у) = 13 (1 + у),
мы видим, что число х у делится на 13. С другой
стороны, по условию, х + у не больше 20. Поэтому
х -f- У = 13 (при этом х = 6 ,у — 7).
V Можно решать уравнение 8х — 5у = 13 так. Одно решение
сразу угадывается: хо = 1 , (/о *= — 1. При любом целом է
пара чисел х ■= 1 + նէ, у = — 1 + 8 1 тоже удовлетворяет этому
уравнению. Действительно,
8 (1 + 5 0 — 5 ( — 1 + 81) = . (8 + 5) + (40< — 40/) = 13.
При этом х + у = Ш , а так как х + у 20, то / «=■ 1, х + у =
= 13, х = 6, у = 7.
Для любого линейного уравнения вида ах — by = с (а и Ь —
взаимно простыв числа) общий вид решений 6 целых числах
можно записать по такой ж е схеме. Находим какое-нибудь одно
его целое решение (х 0: уо). Тогда х = Хо + Ы, у = г/о + at, где
t е Z , — все его решения.
16
З а д а ч а 2-2. Ответ: нельзя.
Допустим, что можно взять k рублевых, I трехрублевых
и т пятирублевых купюр так, чтобы выполнялись
условия задачи, т. е. k + 1-\- т — 10 и £ + 3/ +
+ 5 т = 25.
Вычитая из второго равенства первое, получим:
21 + 4т = 15. Но последнее равенство невозможно,
так как его левая часть четна, а правая — нет. Значит,
наше предположение неверно.
V Вообще уравнение вида ах — by = с имеет решение в целых
числах тогда и только тогда, когда с делится на наибольший
общий делитель и. о. д. (а, Ь) чисел а и Ь.
В задаче 2-2 с = 15 не делится на н. о. д. (а, Ь) =
= н. о. д. (2; 4) = 2.
З а д а ч а 2-3. Ответ: на 68 частей.
Разобьем каждую из двух смежных сторон прямоугольника
на 68 одинаковых частей и через точки
деления проведем прямые по линиям сетки. Тогда
диагональ прямоугольника разобьется узлами сетки
на 68 одинаковых частей, служащих диагоналями прямоугольников
размером 3 X 4 мм. На диагонали каждого
такого прямоугольника нет ни одного узла сетки.
V В общем случае диагональ прямоугольника т Х л разбивается
узлами сетки на н. о. д . ( т , п) одинаковых отрезков.
З а д а ч а 2-4. а ) Ответ: 3 мм.
Произведем деление с остатком:
324 = 141 -2 + 42 (2 квадрата со стороной 141 мм),
141 = 42-3 + 15 (3 квадрата со стороной 42 мм),
42 = 15-2+12 (2 квадрата со стороной 15 мм),
15 = 12-1+3 (1 квадрат со стороной 12 мм),
12 = 3-4 (4 квадрата со стороной 3 мм).
V Для произвольного прямоугольника а X ծ длина стороны
последнего к в ад ра та равна н. о. д. (о, Ь).
Действительно, процедура последовательного деления с остатком,
которую мы проделали в решении задачи, — это алгоритм
Евклида нахождения н. о. д. (а, Ь) (см. [34, 88, 9 8 ]).
А л г о р и т м Е в к л и д а основан на таком факте. Пусть
а = bq + г, тогда н. о. д .(а , 6) = н. о. д . (ծ, г). Сам алгоритм
можно описать так. Если имеются д ва числа а и Ь, причем
с > Ь > 0, то сначала делим а на 6 и получаем остаток г\
(0 ^ /ч < 6). Затем делим число Ь на Ti и находим остаток гг
(0 ^ r2 < гу). Далее делим число г, на число г2, при этом
17
получается остаток /з (0 Гз < քշ), и т. д., пока какой-нибудь
остаток гп֊ 1 не разделится на остаток гп нацело, т. е. лл+ 1 = 0.
Последний ненулевой остаток гп и есть и.о. д. (а, Ъ). В самом
деле,
Гп = Н. О. Д. (rn, rn-x ) = Н. О. д. (г/J—1, гп- 2) = . . .
. . . ■= н. о. д. (г2, п ) = н. о. д. (гь Ь) = н. О. д. (а, Ъ)
В задаче 2-4 а) мы встретились с геометрической иллюстрацией
этого алгоритма.
Отметим еще, что по последовательности частных գ\, հշ, . . .
, . . , զ„, получающихся в процессе применения алгоритма Евклида,
можно записать разложение дроби а /b в цепную дробь (см.
[66, 61, 119]):
а , 1 ֊ = 91 +
+
б) Ответ: например, а = 21, b = 13.
Действительно, произведем деление с остатком!
21 = Ы З + 8; 13 = 1-8 + 5; 8 = 1-5 + 3; 5 = 1-3 +
+ 2; 3 = 1 -2 + 1; 2 = 2-1. Таким образом, получаются
квадраты со сторонами соответственно 13, 8, 5, 3,
2, 1 — шести разных размеров.
V Для произвольного натурального числа п можно найти т а кие
числа а и Ь, чтобы при разрезании получилось ровно п р а з ных
размеров квадратов.
В качестве таких чисел можно взять числа Բո+շ и F n+i последовательности
Фибоначчи, которая задается следующим обра-
80м: Fi = 1, Բշ — 1, Fs = 2, F k — F + F k֊ 2 для k > 3.
Если положить a = F n+ շ и b =» F n+i, то каждый ра з от
прямоугольника F k X Fk- 1 будет отрезаться только один квадрат
со стороной длины Fa-^i и оставаться прямоугольник F k — iX .F * _ 2.
В решении задачи 2-4 б) мы взяли F-i == 13 и F s = 21; р а з меры
квадратов получились равными первым шести различным
числам Фибоначчи: 1, 2, 3, 5, 8, 13.
Построенный пример прямоугольника a X ծ имеет наименьшие
возможные (при данном п) размерьц другими словами, если
числа а и 6 не больше F n+շ, то алгоритм Евклида дает
н. о. д. (а, Ь) не больше чем з а п шагов (см. [6 3 ]).
• Заметим также, что для отношения F n+ ilF n двух соседних
чисел Фибоначчи разложение в цепную дробь имеет чрезвычайно.
18
простой вид: оно состоит из одних единиц. Например,
1—1 + 1
1 Ч —
1 + Т
З а д а ч а 2-5. а ) Ответ: можно.
Обозначим операции автоматов соответственно I,
II, III и условимся п сделанных подряд операций I
или II записывать соответственно как I՞ или II».
Тогда карточку (31; 13) можно получить из карточки
(19; 86) так:
(19; 86) -^>(86; 19) — ֊* ( 1 0 ; 19) —*(1 9 ; 10)
— ֊4 9 ; 10) (10; 9 ) ֊U( 1 ; 9) (9; 1) ֊^ >
֊ 4 2 ; 1 ) ^ ( 1 ; 2 )-^ > (3 ; 2 ) — ^ ( 2 ; 3 ) — ^
֊^ > ( 5 ; 3 ) ^ ( 3 ; 5) ֊^ > (1 3 ; 5) (5; 13)-1^ (31; 13).
б) Ответ: нельзя.
Поскольку операции 1,11,111 сохраняют н. о. д. (т , п),
а н. о. д. (19; 81) = 1 Ф и. о. д. (12; 21) = 3, из карточки
(19; 81) нельзя получить карточку (12; 21).
V Необходимое и достаточное условие того, чтобы из карточки
( т , п) можно было получить карточку (а, ծ), состоит в
том, что н. о. д Հա, гс) = н. о. д. (а. Ь).
Необходимость этого условия очевидна; все операции I, II,
III сохраняют н. о. д.
Если это условие выполнено, то обе карточки с помощью
операций I и III можно привести к карточке (d , d) по алгоритму
Евклида.
Действительно, каждый шаг алгоритма Евклида — это деление
с остатком числа а на число b: а = bq -f- г (0 ^ г < ծ).
Этот шаг можно провести так:
(а, Ь ) ֊* (г, Ь).
Затем, после операции (г, Ь) -—*-(6, г), можно аналогично сделать
следующий шаг алгоритма и т. д. до тех пор, пока не получится
карточка (d, d).
Идя по цепочке (а, Ь) — *■ .. .-*-(d , d) в обратном порядке
с заменой операции I на операцию II, мы из карточки {d, d)
получим карточку (at ծ),
19
Итак, проделав «спуск> от ( т , п) к (d, d ), а затем «подъем»
от (d, d) к (а, Ь) , мы придем в итоге от карточки ( т , п) к кар точке
(а, Ь), что и требовалось.
З а д а ч а 2-в. Ответ: может.
Например, 9-я синяя пометка и 13-я красная находятся
друг от друга на расстоянии 1 см, так как
13-25—9-36 = 1.
V В этой задаче нам фактически надо было найти какое-
нибудь решение в целых числах одного из уравнений
25л: — 36(/ = 1, 2 5 * — 36г/ = — 1
или доказать, что таких решений нет.
Существует стандартная процедура, с помощью которой все*
еда можно найти решение уравнения а х + by = 1, если
н. о. д. (а, ծ) = 1. Продемонстрируем ее на нашей задаче. Выпишем
все шаги алгоритма Евклида (см. обсуждение задачи 2-4 а ) )
для нахождения н. о. д. (36; 2 5 ):
36 = 25-1 + 11; 2 5 = 1 1 — 2 + 3; 1 1 = 3 — 3 + 2; 3 = 2 • 1 + 1.
Перепишем эту цепочку равенства так:
11 = 3 6 — 2 5 — 1 ; 3 = 2 5 — 1 1 — 2 ; 2 = 1 1 — 3 — 3 ; 1 = 3 — 2-1.
Тогда получим
1 = 3 — (11 — 3-3) = 3- 4 — 1 1 = (25 — 11-2)- 4 — 11 =
= 25 ■ 4 — 11 • 9 = 25 • 4 — (36 — 25) • 9 = 25 • 13 — 36 • 9.
В результате получается равенство 25-13 — 36-9 = 1, дающее
одно решение (13; 9) уравнения 25х — 36у = 1.
З а д а ч а 2-7. Ответ: можно.
Проведем какую-нибудь окружность с центром в
вершине данного угла. Стороны этого угла высекают
на окружности дугу в 19°.
Если последовательно отложить циркулем эту дугу
на окружности еще 18 раз, то, поскольку 19X19 =
= 361, последняя засечка отсечет от первой дуги дугу
в Г. Отложив циркулем эту дугу еще 17 раз, мы разделим
дугу в 19° на 19 равных частей. Соединив полученные
засечки с вершиной угла, мы разделим данный
угол в 19° на 19 равных частей.
V Пусть m и п — взаимно простые натуральные числа
(н. о. д Հա, п) = 1) и m < п. Откладывая на окружности после-
m
довательно друг за другом равные дуги, с о с т а в л яю щ и е ю
20
часть полной окружности, можно получить з а п шагоз все вершины
правильного вписанного в окружность «-угольника (сделав
при этом т полных оборотов). На некотором х-м шаге мы получим
вершину, соседнюю с начальной, — при этом мы сделаем некоторое
число у полных оборотов и еще пройдем — ~ » ю часть
т 1 _ окружности, так что х у И . Отсюда п п получается гео-
метрический способ решения уравнения
xm — уп—-1
в целых числах. В нашей задаче m = 19, п -= 360, х = 19, у — 1.
З а д а ч а 2-8. Ответ: 4 ломаные.
Будем считать какую-нибудь точку деления начальной
и занумеруем, начиная с нее, все точки деления
по часовой стрелке числами 1, 2, 3, . . . , 20.
Ломаные с одинаковыми звеньями будут получаться,
если мы будем соединять последовательно каждую
точку с k-и по счету после нее до тех пор, пока не вернемся
в исходную точку 1.
При k = 1 получится правильный двадцатиуголь-
ник с вершинами в точках 1, 2, 3………20.
При k = 2 — правильный десятиугольник с вершинами
в точках 1, 3, 5………19.
При & = 3 — самопересекающаяся замкнутая ломаная
с 20 вершинами в точках 1, 4, 7, 10, 13, 16, 19,
2, 5, 8, 11, 14, 17, 20, 3, 6, 9, 12, 15, 18.
При k = 4 — правильный пятиугольник.
При k = 5 — квадрат.
При 6 = 6 — самопересекающаяся замкнутая ломаная
с 10 вершинами в точках 1, 7, 13, 19, 5, 11, 17,
3, 9, 15.
При k = 7 — снова 20-звенная ломаная.
При k = 8 — 5-звенная ломаная (пятиконечная
звезда). #
При k = 9 — снова 20-звенная ломаная.
При k = 10 получается вырожденная 2-звенная ломаная—
дважды пройденный отрезок.
При £ = 11 получается та же ломаная, что и при
k —9, так как соединять точки через 10 по часовой
стрелке — то же самое, что соединять их через 8 против
часовой стрелки.
Точно так же при ft = 1 2 , 13………19 получаются
соответственно такие же ломаные, что и при k = 8,
.7, 1,
21
Таким образом, всего различных 20-звенных ломаных—
четыре, они получаются при k = 1, 3, 7, 9.
V При любом п различных по форме правильных п-звенных
замкнутых ломаных будет столько, сколько существует натураль-
п
ных чисел, меньших ֊ и взаимно простых с п.
Количество натуральных чисел, меньших данного числа п и
взаимно простых е ним, обозначается обычно через <р (п). Функция
ф (п) называется функцией Эйлера-, если р 1} р -չ pi — все
различные простые числа, входящие в разложение часла п на
простые множители, то
9 < « > — * ( i i — ) ( i £ — ) • • • ( ՛ — )•
Ответ к обобщению задачи 2-8 можно записать так: число
различных правильных rt-звенных ломаных равно ф(л)/2. В частности,
если п = 20, то փ (20) = 2 0 (1 — = 8, а чио
ло ломаных равно ф(2 0 )/2 = 4 (см. [88]).
З а д а ч а 2-9. а ) Ответ: верно.
Разность двух чисел делится на 7 в том и только
в том случае, когда равны остатки от деления этих
чисел на 7. При делении на 7 существует семь возможных
остатков: 0, 1,2, 3, 4, 5, 6.
Допустим, что нельзя выбрать 15 нужных чисел из
100. Это значит, что не более 14 чисел дают при делении
на 7 остаток 0, не более 14 чисел — остаток 1,
аналогично — остатки 2, 3, 4, 5, 6. Но тогда всего чисел
получается не более чем 14-7 = 98 < 100, и наше
допущение неверно.
V Решение задачи 2-9 е ) — типичный пример применения
п р и н ц и п а Д и р и х л е : если в п клетках сидит nk + 1 зайцев,
то хотя бы в одной клетке не меньше k -f- 1 зайцев (см. [43]).
В самом деле, если бы в каждой клетке было не больше k
зайцев, то всего зайцев было бы не больше чем nk, что противоречит
условию.
б) Ответ: неверно.
Приведем контрпример: первые сто натуральных
чисел от 1 до 100. Среди них 14 чисел: 7, 14, . . . , 98,
дающих в остатке 0; по 15 чисел, дающих в остатке
1 и 2; по 14 чисел, дающих в остатке 3, 4, 5, 6. Значит,
среди них нет 16 чисел, для которых разность
любых двух делится на 7.
22
З а д а ч а 2-10. Всякое целое число либо делится
на 3, либо при делении на 3 дает в остатке 1 или 2.
Если число п делится на 3, то его можно записать
в виде п = 3k, поэтому его квадрат можно записать
в виде 9k2, откуда видно, что он делится на 3.
Если число п при делении на 3 дает в остатке 1,
то его можно записать в виде п = 3 k 1, тогда для
его квадрата получаем: п2 = 3 (3k2 + 2k) + 1, откуда
видно, что квадрат при делении на 3 также дает в
остатке 1.
Если число п при делении на 3 дает в остатке 2,
аналогично получаем: п2 = 3(3k2 + 4k + 1 ) + 1, т. е. и
в этом случае квадрат числа п дает при делении на
3 остаток 1.
Если ровно одно из двух чисел не делится на 3, то
его квадрат при делении на 3 дает, как мы видели,
остаток 1, поэтому сумма квадратов этих двух чисел
при делении на 3 дает остаток 1; а если ни одно из
двух чисел не делится на 3, то их квадраты оба дают
при делении на 3 остатки 1, поэтому сумма их квадратов
при делении на 3 даст остаток 2.
Таким образом, сумма квадратов двух целых чисел
делится на 3 лишь в случае делимости каждого
из них на 3.
V Переход от целых чисел к их остаткам от деления на
фиксированное число т —■ основной прием в зад ачах на делимость
де.’ых чисел. При этом постоянно используется следующее простое
правило: чтобы найти остаток от деления на m суммы или
произведения двух (или нескольких) целых чисел, достаточно проделать
те же операции с остатками и найти, какой остаток при
делении на m дает результат.
Покажем, например, что утверждение задачи 2-10 останется
верным, если заменить в ее условии число 3 на число 7. Возведя
в квадрат числа от 0 до б, можно убедиться, что остатки, которые
дают квадраты целых чисел при делении на 7, — это только
0, 1, 2 и 4. Поскольку никакие два из этих четырех чисел, крома
пары нулей, в сумме не дают числа, делящегося на 7, сумма
квадратов двух целых чисел делится на 7, только если каждое
число делится на 7.
Для знатоков. Вопрос о том, может ли для данного простого
числа р сумма квадратов двух целых чисел х 2 -)- у2 делиться на р,
если ни одно из них не делится на р, эквивалентен такому: я в ляется
ли (—1) квадратичным вычетом по модулю р, т. е. существует
ли такое г, что 1 + z z делится на р. Ответ (известный
23
еще Эйлеру): это возможно для чисел р вида Ak -f- 1 (р = 5, 13,
17, 29, . . . ) и невозможно для р — 46 + 3 (р ■= 3, 7, 11, 19,
23, . . . ) . Обобщение этого факта, позволяющее для каждых двух
чисел q и р быстро решить вопрос, является ли q квадратичным
вычетом по модулю р, — квадратичный закон взаимности Гаусса
(см. [31, 88]).
З а д а ч а 2-11. Покажем, что ни одно число вида
9п + 4, где п — натуральное число, не представляется
в виде суммы трех кубов; поскольку чисел такого
вида бесконечно много, отсюда будет следовать утверждение
задачи.
Любое целое число имеет либо вид 3/, либо 3 / + 1,
либо 3/ — 1, где I — целое число. Поэтому куб любого
целого числа имеет соответственно вид либо 27/3, либо
27Р ± 2712 + 9/ ± 1 = 9 (3/З± 3 /2 + /) ± 1,
т. е. имеет вид либо 9гп, либо 9m ± 1.
Комбинируя всеми способами эти возможности, мы
получим, что сумма кубов трех целых чисел представляется
одним из следующих вариантов: 9п\ 9/г±1;
9п ± 2; 9п ± 3 , но не может равняться числу вида
9п + 4 (и, кстати, 9п — 4).
V В 1909 г. были доказаны следующие г и п о т е з ы Э. В а ри
н г а (1770 г.): каждое натуральное число может быть представлено
в виде суммы не более 9 кубов натуральных чисел-, для
каждого натурального k любое натуральное число представляется
как сумма w или меньше k-x степеней натуральных чисел, где w
зависит только от k. Первая гипотела была доказана А. Вифери-
хом, вторая — Д. Гильбертом (элементарное ее доказательство
было получено советским математиком Ю. В. Линником). Наименьшее
значение w = w(k) неизвестно уже для k = 4 (см,
[5, 118]). ‘
Любопытно, что каждое натуральное число п легко представить
в виде суммы пяти кубов целых чисел.
В самом деле, п — п3 делится на 6 при всех п. Поэтому
п — п3 + 6/, где է целое. Отсюда
n = n3 + ( t + l ) 3 + ( t — 1)» + ( — /)» + ( — է )\
З а д а ч а 2-12. Поскольку каждый ученик мог сидеть
не больше чем с 27 учениками, это не могло
длиться более 27 месяцев.
Покажем, как учитель мог рассаживать учеников
в течение 27 месяцев.
24
Занумеруем учеников числами от 1 до 28. Поставим
числа от 1 до 27 на окружности в вершинах
правильного 27-угольника, а число 28 — в центре этой
окружности. Соединим отрезком точки 1 и 28. Остальные
точки соединим попарно отрезками, перпендикулярными
этому отрезку — см. рис. 8, а. Рассадим учеников
так: если два числа соединены отрезком, то
соответствующих им школьников сажаем за одну
парту.
В следующем месяце соединяем отрезком точки 2
и 28 и через остальные точки проводим перпендикулярные
ему отрезки; рассаживаем учеников по этой
схеме — рис. 8,6. Дальше берем поочередно отрезки
28-3, 28-4, . . . , 28-27 и проводим отрезки, перпендикулярные
каждому из них.
V Заметим, что на рис. 8, а сумма номеров каждой пары
точек круга, соединенных отрезком, равна числу 29, которое дает
остаток 2 при делении на 27, а точка 1 соединена с центром
точкой 28; эта последняя пара оказывается в особом положении:
среди чисел от 1 до 27 невозможно подобрать такую пару к числу
1, кроме него самого, чтобы сумма чисел этой пары давал а
остаток 2 при делении на 27.
На рис. 8, б ситуация аналогична: суммы пар номеров соединенных
точек дают при делении на 27 остаток 4, а для номера 2
среди чисел от 1 до 27 нет подходящей пары, кроме него самого;
*то т номер 2 соединен с центром 28.
Эти наблюдения приводят к следующей числовой интерпретации
приведенного в задаче 2-12 расписания.
25
Фиксируем какое-нибудь число г от 1 до 27. Объединяем
в пары те номера от 1 до 27, которые в сумме дают остаток г
при делении на 27. При этом без пары останется только тот номер
х, который в сумме с самим собой дает при делении на 27
остаток г. Если г четно, то х = г/2, а если нечетно, то х ==;
= (г + 27)/2. Этот номер х мы соединим с номером 28.
Для любого четного числа п учеников можно аналогичным
образом составить расписание на п — 1 месяц. Для этого надо
объединять в пары те номера из множества всех целых чисел
от 1 до п — 1, сумма которых дает остаток г при делении на
п — 1. Если г четно, то при этом без пары останется номер г/2,
а если нечетно, то номер (r + n — 1)/2; этот номер объединим
в пару с оставшимся номером п (см. [34]).
З а д а ч а 2-13. Ответ: например, 48, 49, 50 или
548, 549, 550.
V Можно показать, что вообще для любого k существует It
последовательных натуральных чисел, каждое из которых делится
на квадрат целого числа, большего единицы.
Тут уместно воспользоваться так называемой к и т а й с к о й
т е о р е м о й об о с т а т к а х (см. [88]): каковы бы ни были
натуральные попарно взаимно простые числа a i, а 2, . . . , а„ и целые
неотрицательные числа г1։ г2, . . . , гп (п < a ւ, гг < аг, . . .
. . . , тп < а „ ), существует такое натуральное число гп, которое
при делении на числа ai, Օշ. а„ соответственно дает остатки
Г1, Гг, . . ., гп.
Пусть բԼ p j р 2 — квадраты п различных простых чисел.
Тогда, по этой теореме, найдется такое целое число т , которое
дает при делении на числа р\, р% . . . . р \ соответственно
6 2 2 1-г остатки р * — 1, р — 2, . . рп — п . Поэтому п последовательных
чисел т + 1, т + 2, . . . , m + п будут делиться соответственно
2 9 2 на pf, Pi Рп.
Пример (548, 549, 550), указанный в ответе, подобран именно
таким путем: полагаем pi = 2, р2 = 3, рз = 5, находим число
ш, которое дает соответственно остатки 3, 7 и 22 при делении
на 4, 9 и 25; годится, например, число m *■« 547.
Это число m можно подобрать таким образом. Ищем его в
виде
т = а — 9-25 + 4- й-25 + 4- 9-с.
Нужно, чтобы число а — 9-25 давало остаток 3 при делении
на 4, число 4 ծ-25 — остаток 7 при делении на 9 и число 4-9-с —
остаток 22 при делении на 25. Полагая а = —1, 6 = 7, с = 2,
получаем m ֊ 547.
26
З а д а ч а 2-14. Ответ: можно.
На рис. 9 приведены два примера нужной расстановки.
Это можно проверить простым подсчетом.
1 г
«)
Рис. 9
V Числа, выписанные на первом круге на рис. 9, а по часовой
стрелке, — это остатки от деления последовательных степеней
I, 2, 22, 23, . . . , 2 11 на число 13, а против часовой стрелки —
остатки последовательных степеней 1, 7, 72, 73……….. 7й . Естественно,
что для каждых трех соседних чисел а, Ь, е (а значит,
и для их остатков при делении на 13) число b2— ас делится на
13; если три числа а, Ь, с образуют геометрическую прогрессию,
то Ьг — ас.
Точно так же на рис. 9 ,6 выписаны остатки от деления на 13
последовательных степеней 1, 6, 62, . . . , 6 11 (по часовой стрелке)
н 1, 11, I I 2, . . . . I I 11 (против часовой стрелки).
Числа 2, 6, 11, 7, стоящие на рис. 9 рядом с 1, — это остатки
при делении на 13 чисел 2, 25, 27, 2 11.
Вообще, для любого простого р существует первообразный
корень — такое число г, что его степени 1, г, г2, . . . , г”՜ 1 дают
все различные остатки 1, 2 р — 1 при делении на р; число
таких г равно ф( р— 1 )— числу взаимно простых е р — 1 чисел
от 1 до р — 2 (см. комментарий к задаче 2-8).
В задаче 2-14 р = 13, ф( р— 1) = ф(12) = 4, так как имеется
4 числа, 1, 5, 7, 11, взаимно простых с числом 12 и меньших
его: все первообразные корни — остатки от деления на 13 чисел
£, 2 5, 27, 2 11 (см. [88]).
З а д а ч а 2-15. Ответ: неверно.
Например, при п = 6 число 63 + 5-6— 1 равно
V Знаток сразу ответил бы на вопрос задачи отрицательно,
так как, кроме констант, вообще не существует многочленов F {n )
б-72.
27
с целыми коэффициентами, значения которых при всех натуральных
п — простые числа.
В самом деле, если свободный член а многочлена не равен О
и ± 1 , то значения F (k a ) при целых ft-делятся на а и среди них
есть составные. Если а — ± 1 , то можно сначала «сдвинуть» многочлен—
заменить F (n ) на F (n — \ -h ) = G(n) так, чтобы свободный
член стал неравным ± 1 .
В задаче 2-15 найти а, при котором F (n ) — п3 + Ъп— 1 —
составное число, можно так. Положим п = т + 1; у многочлена
F ( т + 1) = ( т + I ) 3 — f 5 ( т + 1) — 1 свободный член равен 5, и
поэтому F (6) делится на 5.
Отметим, что недавно (в 1970 г.) советский математик
Ю. В. Матиясевич доказал существование многочлена от 21 переменного
с целыми коэффициентами, обладающего таким свойством:
множество его положительных значений при целых значениях
переменных совпадает с множеством простых чисел (см.
[47, 54, 100]).
З а д а ч а 2-16. Разложим данное число на множители:
п5 — 5 п3 + 4 п = п{п* — 5 п2 + 4) = п (п2 — 1) (п2 — 4) =
= (п — 2) (я — 1 ) ո ( ռ + 1 )(п — f 2).
В результате получилось произведение пяти последовательных
целых чисел.
Одно из таких чисел обязательно делится на 5,
одно из трех последовательных чисел делится на 3, а
из четырех последовательных чисел одно делится
на 4, а другое — на 2. Поэтому произведение делится
на 120.
V Другое, комбинаторное решение этой задачи можно получить,
если заметить, что при п ^ 3 число
(п + 2) (п + 1) п (п — 1) (п — 2)
1 ‘ 2 — 3 — 4 — 5
есть биномиальный коэффициент С®+2 (число 5-элементных подмножеств
из (п + 2) элементов), а это число, несомненно, целое.
Вообще, многочлен F (x ) принимает целые значения при всех
целых х тогда и только тогда, когда его можно представить в
виде суммы F ( x ) = ^ j a kC^c с целыми коэффициентами а к, где
Ժ Հ = (см. [104 ] ).
З а д а ч а 2-17. а ) Ответ: да.
Удобно искать такой многочлен в виде
р (х) — а х { х— 1) + Ьх + с.
28
Подставляя в это тождество л: = О, л: = 1 и л: = 2, получаем
для определения коэффициентов а, Ь, с удобную
«треугольную» систему линейных уравнений
Г с = 19,
Հ Ь + с = 85,
Լ 2а + 2Ь + с = 1985,
из которой находим: с = 19, Ь — 66, а = 9 1 7 и получаем
ответ:
р (х) = 917л:2 — 851л: + 19.
V Точно так же удобно искать многочлен степени не выше п,
принимающий в данных п + 1 точках ci, сг с „+ 4 данные
значения. Записав р (х ) в виде
Р (х) = b0 + b i ( x — d ) + Ь2 (х — ci) (х — с2) + . . .
. . . + Ьп (х — C l ) (х — с2) . . . (х — с „)
и подставляя в это тождество х — С\, с2 сп+ ь мы получаем
треугольную линейную систему для определения п + 1 неизвестных
коэффициентов Ь0, ծւ Ьп.
Указанный метод нахождения многочлена с данными значениями
называется способом интерполяции Ньютона.
б) Ответ: нет, не существует.
Для доказательства воспользуемся следующим
утверждением: если дан многочлен
р (х) = а^хп + а^хп՜ 1 + а2хп՜ 2 + . . . -\-ап_\Х + ап
с целыми коэффициентами, то для любых целых чисел
с и d целое число р(с )— p(d) делится на число
с —d.
Согласно этому утверждению число р( 19) — р( \) =
= 66 должно делиться на число 19— 1 = 18, что неверно,
откуда и следует ответ.
Докажем справедливость высказанного утвержлс՝-
ния:
Р(с) — p(d) = (a0cri + a lcn- 1 + . . . + ап_ хс + ап) —
— (oofi?՞ + aidn 1 + . . . ֊( — an-\d + an) =
= ao(cn— dn) — \ — a l {cn 1 — dn ՛) + . . . + a „ _ i ( c — d).
Для любого натурального k справедлива формула
ck — dk = (с — d) (cft-1 + ck~2d + . . . ֊) ֊ cdk՜ 2 + dk~l)
29
(она получается из формулы суммы k членов геометрической
прогрессии с первым членом Ժ—Հ и знаменателем
d/c). Поэтому каждое слагаемое в полученном
равенстве для р(с) — р ( а ) делится на с — d, значит,
и вся сумма делится на с — d.
V Аналогично можно показать, что для любого многочлена
р (х ) и любого числа d многочлен р ( х )— p (d ) делится на многочлен
х — d, т. е. р ( х )— p(d ) = (х — d )q (x ) , где q ( x )— неко*
торый многочлен. Переписав это тождество в виде р (х ) =>՝,
= ( х — d )q (x ) + p (d ), получаем следующую т е о р е м у Б е з у:
остаток от деления многочлена р (х ) на двучлен (х — d) равен
p (d ).
З а д а ч а 2-18. а ) Ответ: (х2 + х + 1 ) (х2— х +
+ 1) ( * 4 — х2 1).
Действительно:
х8 + л» + 1 = х8 + 2х4 + 1 — х4 = (х4 + I)2 — (х2)2 =
= (х4 ֊Ь х2 + 1) (х4 — х2 + 1) =
= ((х2 + I)2 ֊ х2) (х4 — л:2 + 1) =
= (х2 + х + 1)(х2 — х + 1)(х4 — х2 + 1).
б) Ответ: (х3— х2 + 1 )(х2 + х + 1).
Действительно:
х5 + х + 1 = (г5 + х4 + х3) — (х4 + х3 + х2) +
+ (х2 + х + 1) = (х3 — х2 + 1) (х2 + х -+ 1).
V Существуют многочлены любой степени с целыми коэффициентами,
которые не разлагаются в произведение многочленов
меньшей степени с целыми коэффициентами (например, х” — 2).
Они называются неприводимыми (над кольцом целых чисел).
Имеются алгоритмы, позволяющие для любого многочлена
указа ть его разложение на неприводимые множители или показать,
что он сам неприводим (см. [85, 117]).
З а д а ч а 2-19. Ответ: при а = —2.
Пусть многочлены f(x) = х4 + ах2 + 1 и g ( x ) = ‘
= х3 + а х + 1 имеют общий корень хо. Тогда, умножив
второй многочлен на х и вычитая из первого, получим
многочлен, имеющий тот же корень, а этот многочлен
— просто
f (х) — xg (х) = 1 — х.
Его единственный корень х о = 1 . Многочлены /(х) и
30
g(x) имеют этот корень при а = —2; чтобы убедиться
в этом, достаточно приравнять нулю /(1) и g ( l )—
оба эти числа равны а + 2.
V Для того чтобы многочлены f (x ) и g (x ) имели общий корень
Хо, нужно, чтобы оба они делились на многочлен х — Хо
(теорема Безу, см. задачу 2-17). Найти общий делитель наибольшей
степени двух многочленов можно с помощью алгоритма
Евклида — так же, как и наибольший общий делитель дэух чисел.
В решении задачи 2-19 мы проделали один шаг этого алгор
и тм а— разделили многочлен f (x ) на g (x ) с остатком, который
оказался равным 1 — х.
Если далее разделить g {x ) столбиком на ( х— 1), то получится
остаток а + 2:
g (х) = (х — 1) (х 2 + х + а + 1) + (а + 2).
Если а = —2, то остаток равен 0: если же а ф —2, то многочлены
не имеют общего делителя степени, большей 0.
З а д а ч а 2-20. а ) Пусть k = Ժ + 5b2 и / = с2 4 +
5d2 — два каких-нибудь числа из множества М.
Тогда
Ы = (а2 + 5Ь2) (с2 + Ы2) = {ас — 5bd)2 + 5 {ad + be)2. (*)
Таким образом, kl = x2 -\-btj2, где х = ас — 5bd,
у — ad + be, т. е. число kl принадлежит М.
б) Ответ: существуют. Например, 84 = 4-21 = 6-14.
Покажем, что все пять выписанных чисел принадлежат
множеству М:
4 = 22 + 5 • О2, 6 = I2 + 5 • I2, 14 = З2 + 5 • I2,
21 = 42 + 5 • I2, 84 = 22 + 5 — 4 2.
Для того чтобы показать, что числа 4, 6, 14, 21 —базисные,
выпишем все числа из М, большие 1 и не превышающие
21 :4, 5, 6, 9, 14, 16, 20, 21. Среди них все,
кроме 16, 20, — базисные, потому что каждое из них
не делится ни на одно из предыдущих.
в) Предположим, напротив, что базисных чисел
конечное число: Ь\, Ь2, . . . , Ьп. Тогда число 1 +
+ 5 (ծյծշ . . . bn)2, очевидно, принадлежащее М, не делится
ни на одно из чисел Ь\, Ь2, . . . , Ьп, поэтому оно
само базисное и не равно ни одному из Ьь Եշ, . . . , b„,
что противоречит предположению.
V Обратим внимание на аналогию между множеством М и
множеством всех натуральных чисел.
31
Так же как всякое натуральное число разлагается в произведение
простых чисел, любое число из М разлагается в произведение
базисных чисел. Однако если натуральное число единственным
образом ра злагается на простые множители (основная теорема
арифметики), то, согласно задаче 2-20 б), это неверно для
чисел из множества М.
Для знатоков. Тождество (») связано с правилом умножения
чисел вида х + у V — 5 (см. [4 8 ] ) :
(а + Ь V — 5) (с + d V—՜Յ) “ («с ~ 5а6) + (ad, + be) V — б.
Вопрос о разложении на множители чисел из М эквивалентен
вопросу о разложении на множители в кольце чисел вида
х + у V ~ 5 , где х и у — целые. Задачи о разложении на множители
в кольцах такого типа сыграли важную роль в истории математики.
Из этих задач возник новый раздел математики — ал гебраическая
теория чисел (см. [82]).
З а д а ч а 2-21. Ответ: например, (72, 132, 172),
(172, 252, 312), (312, 412, 492).
Тройка квадратов р2, q2, г։ образует арифметическую
прогрессию тогда и только тогда, когда р2 +
+- г2 = 2 q2 или
(г — q) {г + q) — (<7 — р) (q + р).
Например, для третьей из указанных троек (р =
= 31, <7 = 41, г = 49) получаем
(49 — 41) (49 + 41) = (41 — 31) (41 + 31)=“ 720.
V Вот общие формулы для таких троек (из взаимно простых
чисел):
р = п2 + 2mn — т ։ , q =» m* + п%, г = т 2 + 2т п — п®,
где т и п — произвольные взаимно простые числа. Если при каких-
нибудь т и п числа р, հ, г имеют общий делитель, то мы
можем их сократить на него. (Это бывает, когда числа т и п
оба нечетны; тогда соответствующие чцела р, q, г имеют общий
множитель 2. Других общих множителей, как нетрудно показать,
быть не может.)
То, что числа такого вида годятся, можно проверить, подставив
их в соотношение (р —■ q) {р + q) = (q — t) (q + г ) .
К этим формулам можно прийти разными путями; мы укажем
один из них (см. [1 2 2 ]).
Пусть р1 + г1 = 2<72. Разделив все члены этого уравнения на
q2, получаем (p /q )2 + (г/17) 2 = 2. Обозначив p/q через х, r\q —
через у, получаем уравнение х ։ + у2 = 2. Таким образом, задача
32
нахождения чисел р, q, т сводится к решению уравнения
* 2 + </2 2 в рациональных числах х, у.
Идею решения объясним на геометрическом языка. Решить
полученное уравнение — это значит на окружности х 2 + у2 • ֊- 2
найти все точки с рациональными координатами. Возьмем одну
такую точку — скажем, (— 1; — 1). Если провести через эту точку
и другую рациональную точку (х ; у) прямую, то ее угловой
коэффициент է == (у + 1) / (jc + 1) рационален.
Верно и обратное: любая прямая с рациональным угловым
коэффициентом է ф —1, проходящая через точку (—1; —1), пересекает
еще раз окружность х2 + у2 = 2 в рациональной точке
(х ; у ). Чтобы убедиться в этом, выразим у из уравнения прямой
у ■— /(1 + * ) — 1 и подставим в уравнение окружности:
•*2 + (f(i + *) — О2 = 2,
откуда
(1 + է2) х 2 — 2/ (1 — /) л: + (է2 — 2է — 1) = 0.
Это — квадратное уравнение относительно х, один корень которого,
х = —1, мы знаем.
С помощью теоремы Виета находим второй корень: х =
֊ Р + 2/ + 1
է2 + 1 ՜
Мы нашли одну координату точки (х; у ). Теперь можно най-
Ր + 2է — 1
ти и вторую: у = — —— .
Положим затем է — гп/п; тогда из формул для х — ~ и
у = — получаем тройку р, q, г в таком виде: р = —т 2 + 2пш +
— f п2, q — m2 п2, г = ш2 + Գոտ — п2.
Описанный способ рассуждений годится для отыскания всех
рациональных точек на кривой второго порядка (или — что то же
самое — всех целых решений уравнений типа а х 2 + Ьху + су2 =
*= dz2), задаваемой уравнением с целыми коэффициентами,
если известна хоть одна такая точка. Для выяснения вопроса
о том, существует ли такая точка, также существует эффективный
алгоритм.
З а д а ч а 2-22. Ответы: а ) семь решений в целых
числах: (0 ;0 ), (1; 0), ( — 1 ; 0 ) , (2; 6), (2; ֊6 ) , (3; 12),
(3; —12);
б) еще четыре решения в рациональных числах:
( ~ ¥ : ± ¥ ) ‘ ( ~ Т : т ) ‘
V Как находить новые решения в рациональных числах по
уже имеющимся, можно объяснить на геометрическом языке.
2 Н. Б. Васильев
33
Наше уравнение зад ае т некоторую кривую на координатной плоскости
Оху.
Пусть мы знаем какие-нибудь две точки этой кривой, коор«
динаты которых ( * i ; y i) и (Хг\ ւ/շ) — рациональные числа. Прямая,
проходящая через эти точки, пересекает кривую в третьей
точке, поскольку уравнение кривой имеет третью степень.
Координаты * յ , уз этой третьей точки будут рациональными
функциями от хи уи *շ, уз с целыми коэффициентами, т. е. тоже
рациональными числами.
Таким образом, отправляясь от двух каких-нибудь решений
(*ւ ; г/|), (*շ; Уг) уравнения в рациональных числах, мы получаем
новое решение (*տ; уз) в рациональных числах.
Представим теперь результаты соответствующих вычислений,
Прямая, проходящая через данные точки ( * i i y i) и (х2\ уг),
задается уравнением y = t ( x — *ւ ) + ^ւ где ^ —= (</2 — y i ) l ( * i— ■*<)»
Подставляя у в уравнение ք/յ — 6 ( * 3 — х ), получаем уравнение
третьей степени относительно х, дв а корня ЛГ], Хг которого нам
известны (ведь точки лежат на кривой), а третий можно найти
по теореме Виета:
*8 = է2/6 — * ւ — х 2. (1)
Аналогично можно найти уз:
Уз = f 3/6 + 2</i — У з ֊ 3 / * i . (1 ‘)
Можно взять точку (Хг\ уг), «совпадающую» с (*ւ ; иi ) ,—
провести в ней касательную к кривой; она будет пересекать кривую
еще в одной точке:
А’* *= / 2/6 — 2лгI, #4 = P/Q. (2)
Итак, мы получили формулы, позволяющие находить по известным
рациональным решениям уравнения у2 = &(х3— х) но»
вые решения.
Для знатоков. Естественно зад а ть следующие вопросы. Будем
ли мы указанным способом (проводя через известные рациональные
точки прямые) получать каждый ра з новые рациональные
точки? Конечно или бесконечно множество рациональных
точек? Каким образом их все можно описать? Сколько среди
них целых точек?
Для того чтобы ответить на эти вопросы, целесообразно на
кривой третьей степени ввести операцию сложения точек, обладающую
свойством ассоциативности. Описать ее удобнее для
кривой, заданной уравнением
у 2 = я 3 + а х + Ь. (3)
(Любую неособую кривую Р (х , у) « 0 третьей степени можно
некоторым преобразован кем переменных привести к такому виду;
34
при этом если коэффициенты Р (х , у) были целыми, задачу отыскания
рациональных точек на кривой Р (х , у) = 0 можно свести
к аналогичной задаче для кривой (3) с целыми а и 6; для нашей
кривой у2 — 6 (х 3— х) достаточно заменить переменные
v — 6х, и — 6у — она примет вид и2 — v3 — 36у.)
Рассмотрим две точки А, В кривой (3 ), найдем третью точку
пересечения прямой АВ с этой кривой. Обозначим через А © В
точку, симметричную ей относительно оси Ох (рис. 10). Тогда
для любых трех точек А, В и С кривой имеет место соотношение
( А ® В ) © С = Л ® ( В ® С ) .
Это свойство ассоциативности имеет интересную геометрическую
интерпретацию. Если на плоскости проведены две тройки
Рис. 10
прямых так, что прямые из разных троек пересекаются в 9 точках^
то кривая третьей степени, содержащая 8 из этих точек, должна
содержать и девятую. Если добавить к кривой бесконечно у д аленную
точку Z, то множество всех ее точек с операцией © образует
коммутативную группу (свойство А®В « 6Ф .1 очевидно).
Точка Z играет в этой группе роль нуля; точкой 0 Л, противоположной
точке А, считается точка, симметричная точке А от-
2* 35
носителыю оси Ох. Условие принадлежности трех точек А, В , С
одной прямой имеет вид А®В = Q C или А ® ВФ С = Z.
Рациональные точки на кривой (3) с целыми а, Ь также образуют
группу относительно операции 0 . Для нашей кривой
у2 = 6 (х 3 — х) сложение точек задается формутами (1 ), ( Г ) ,
(2), а именно
(х\, г/ i ) © (Х2, у 2) -= (х г\ — у 3)\
(Х й У \ ) ® { х и г/1) = 2 (хй У\) = (Х£ t/t).
Все указанные в ответе точки легко получить из трех точек*
Е ( I ; 0 ), F (—1; 0 ), G (2; 6 ). При этом E@ F имеет координаты
(0; 0 ), £© G ■= (3; 12), F 0 G = (— 1/3; 4/3), £ © F 0 G =
« = (— 1/2; —2/3), G 0 G = 2G = (25/24; —35/48), 2 G®F =
= (— 1/49; 120/49), 2G®E — (49; 840) и т. д. (Заметим, что
2Е = 2F ■= 2 (Е Ф F ) = Z.)
Найти полностью группу рациональных точек для конкретной
кривой (3) — очень трудная задача. Известно, что это — группа
с конечным числом образующих (теорема Морделла), но непросто
найти в конкретном случае даже количество ее образующих
бесконечного порядка (т. е. количество независимых точек А кривой,
для которых пА Z ни при каком п). См. [122].
Целые точки, как видно из нашего примера, могут появляться
среди рациональных достаточно неожиданно. Однако, согласно
теореме Туэ, на неособой кривой степени 3 (или больше) их
всегда лишь конечное число.
Еще одна «теорема конечности» явилась недавней математической
сенсацией: в 1983 г. появилось доказательство (молодого
математика Фалтингса) г и п о т е з ы М о р д е л л а : на неособой
кривой Р (х , у) = 0 рода больше 1 (кривая предполагается неособой
и на бесконечности) может быть лишь конечное число р а циональных
точек (здесь Р (х , у)— неприводимый многочлен с
целыми коэффициентами).
Род кривой Р (х , у)— сравнительно легко вычисляемая целочисленная
характеристика, связанная со степенью п многочлена
Р (х , у ). К кривым рода 0 относятся окружности и другие кривые
второго порядка, рода 1 — неособые кривые третьей степени. Что
же касается неособых кривых Р ( х , у) = 0 степени п ^ 4, то их
род, как правило, не меньше двух, и поэтому они могут содерж
ать лишь конечное число рациональных точек. В частности, это
относится к кривой Ферма хЛ + уп — 1 при п ^ 4.
36
#Математика #математические_олимпиады