Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В

• Название: Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
• Дата: 16.10.2022
• Размер: 3.28 Mb.
• Имя файла: algebra.pdf
• Тип: Учебное пособие; #736986
• страница: 27 из 71

16.2. а) Положим k = l! − 1. Тогда k! l! = n!, где n = б) Положим a
1
= a
2
! . . . a
m
! − 1. Тогда a
1
! a
2
! . . . a
m
! = n!, где n =
= a
2
! . . . a
m
!.
16.3. Для n = 2 можно взять числа 1 и 2. Пусть числа a
1
, . . .
. . . , удовлетворяют требуемому условию. Покажем, что тогда числа A, A + a
1
, . . . , A + a
n
, где A = a
1
. . . a
n
, тоже удовлетворяют требуемому условию. Ясно, что A+a
k
+A делится на поскольку A делится на a
k
. Проверим, что A + a
i
+ A + делится на A + a
i
− (A + a
j
)
= a
i
− a
j
. По условию a
i
+ делится на a
i
− Кроме того, 2a
i
= (a
i
+ a
j
)
+ (a
i
− a
j
) делится на a
i
− a
j
, а значит, делится на a
i
− a
j
16.4. а) Ответ бесконечно. Пусть, например, a = 2
n
− и b = 2
n
(2
n
−2). Тогда a+1=2
n
−1 и b+1=2 2n
−2·2
n
+ 1 = б) Ответ бесконечно. Пусть, например, a=2
k
+ 1 и b= a
2
−1=
= 2
k
+1
(2
k
−1
+ 1). Тогда у чисел a и b + 1 = одинаковые простые делители. У чисел a + 1 = 2(2
k
−1
+ 1) и b = 2
k
+1
(2
k
−1
+ 1) тоже одинаковые простые делители. Воспользуемся тождеством Рамануджана f
2
= f
4
= 0 из задачи. Положив a = 1, b = 2, c = 3 и d = 6, получим требуемый набор чисел 11, 6, 5 и 10, 9, 1.
16.6. Ответ для любого. Числа 1/n!, 2/n!, . . . , n/n! образуют арифметическую прогрессию длины n с разностью 1/n!. Эти числа имеют вид, где числа n!/k целые. Ответ существует. Положим a
1
= 2, a
2
= 2 2
· 3, a
3
=
= 2 2
· 3 2
· 5, . . . , a
n
= 2 2
· 3 2
· . . . · p
2
n
−1
p
n
, где p
n
— е простое число

Глава 16. Примеры и конструкции
Число a
k
+ a
k
+l
+ . . . + делится на и не делится на p
2
k
, поэтому оно не может быть степенью натурального числа. а) После перенумерации карточек можно считать, что карточки сложены в произвольном порядке, а сложить их нужно по порядку. Назовём
беспорядком пару соседних карточек с номерами и i + 1, на которых написаны числа a
i
>
a
i
+1
. Разобьём карточки на блоки, в которых нет беспорядков (блок может состоять из одной карточки. Любые два блока можно слить так, чтобы получился набор карточек без беспорядков и при этом в каждом блоке порядок карточек не изменился.
Первоначально количество блоков не превосходит 32. Снимем сверху первые 16 блоков и сольём блок с номером i с блоком с номером i + 16. После этого получится не более 16 упорядоченных блоков. Снимем теперь сверху первые 8 блоков и сольём блок с номером i с блоком с номером i + 8. После этой (второй)
операции останется не более 8 блоков, после третьей операции на более 4 блоков, после четвёртой не более 2 блоков, а после пятой операции карточки будут упорядочены.
б) Если карточки расположены в обратном порядке, то количество беспорядков равно 31. Когда мы снимаем сверху часть карточек, один беспорядок пропадает ив двух наборах карточек вместе будет 30 беспорядков, поэтому водной части будет не менее 15 беспорядков. Ясно также, что если между двумя карточками, образующими беспорядок, вставить любую карточку, то образуется по крайней мере один беспорядок. Значит, если между ними вставить несколько карточек, то всё равно образуется по крайней мере один беспорядок. Поэтому после первой операции останется не менее 15 беспорядков, после второй не менее 7, после третьей не менее 3, а после четвёртой операции останется не менее одного беспорядка. При заменах x на 1 − x и на 1/x из каждого числа можно получить всего шесть различных чисел x, 1/x, 1 − x,
1 1 − x
,
x
x
− 1
,
x
− 1
x
. Поэтому функция x
2
+
1
x
2
+ (1 − x)
2
+
1
(1
− x)
2
+
x
2
(1
− x)
2
+
(x
− обладает требуемыми свойствами. Да, существует. Пусть, например, f(x, y) = x
2
+ (xy − Если f(x, y) = 0, то x = 0 и xy − 1 = 0, чего не может быть. С другой стороны, для любого e
>
0 можно положить x =
√
e и xy − 1 те. Тогда f(x, y) = 2
e

Решения задач. Ответ существует. Пусть, например, f(x) = x
3
− Этот многочлен обращается в нуль при x = 0, ±
√
2. Предположим,
что x = m/n и y = p/q — несократимые дроби (n > 0 и q > 0), причём
f(x)
= f(y). Тогда 2n
2
)
= n
3
p(p
2
− Числа p и q взаимно простые, поэтому числа p
2
− и q тоже взаимно простые. Следовательно, делится на q
3
. Аналогично
q
3
делится на n
3
, поэтому n = q. В таком случае равенство (1) переписывается в виде m
3
− 2mq
2
= p
3
− 2pq
2
, те При m 6=p получаем m
2
+ pm + p
2
= 2q
2
. Нов таком случае оба числа и p чётные, а значит, число q тоже чётное. Это противоречит взаимной простоте чисел p и q.
16.12. Ответ да, можно. Поместим одного человека в центр окружности, а всех остальных расставим по окружности через равные промежутки. Разбиение на пары будем строить следующим образом. Выберем одного человека, стоящего на окружности,
и проведём через него диаметр. Одну пару составляет выбранный человек и человек, стоящий в центре. Остальные пары составляют люди, стоящие в концах хорд, перпендикулярных проведённому диаметру. а) Ответ звена. Выясним, при каком наибольшем достаточно расковать k звеньев n-звенной цепи, чтобы из образовавшихся частей можно было составить все целые веса от до n. Если расковано k звеньев, то любое число звеньев от 1 до можно набрать из них. Но k + 1 звеньев мы не сможем набрать,
если не будет части из k + 1 или менее звеньев (мы здесь не учитываем раскованные звенья. Наиболее выгодно иметь часть из ровно k + 1 звеньев. Тогда мы сможем получить любое число звеньев от 1 до 2k + 1. (Иначе мы сможем получить лишь число звеньев от 1 до l
1
+ k, где l
1 6
k.) Затем наиболее выгодно иметь часть из 2(k + 1) звеньев, затем из 4(k + 1) звеньев и т. д.
Итак, если мы расковали k звеньев, то наиболее выгодна ситуация, когда полученные при этом k + 1 частей состоят из k + 1,
2(k + 1), 4(k + 1), 8(k + 1), . . . , 2
k
(k
+ 1) звеньев (раскованные звенья мы здесь не учитываем. В таком случае можно составить любое число звеньев от 1 до n = 2
k
+1
(k
+ 1) − 1. Итак, если 6 n 6 2
k
+1
(k
+ 1) − 1, то можно обойтись k разрывами и нельзя обойтись k − 1 разрывами. В частности, если 24 6 n 6 63, то наименьшее число раскованных звеньев равно 3. Полученные при расковке четыре части цепи должны состоять при этом из 4, 8, 16,
29 звеньев

Глава 16. Примеры и конструкции б) Ответ звена. Согласно решению задачи а) для цепи,
состоящей из n звеньев, где 64 6 n 6 159, достаточно расковать звена. Ответ да, можно. Проведём 10 попарно пересекающихся прямых. Пусть маршруты проходят по этим прямым,
а остановками служат точки пересечения прямых. Любые 9 маршрутов проходят через все остановки, поскольку через каждую остановку, лежащую на оставшейся прямой, проходит одна из 9 прямых, соответствующих этим маршрутам. Любые 8 маршрутов не проходят через остановку, которая является точкой пересечения двух остальных маршрутов. Ответ да, можно. Отнесём к одной группе число а к другой — число a
n
−1
. Затем будем последовательно относить числа a
n
−2
, a
n
−3
, . . . , к той группе, в которой сумма чисел меньше (если суммы равные, то число можно относить к любой группе. Пусть ∆
k
>
0 — разность между суммами чисел в группах,
полученных после отнесения к ним a
k
. Покажем, что ∆
k
6
a
k
. Действительно. Ясно также, что если ∆
k
6
a
k
, то ∆
k
−1
= |∆
k
− a
k
−1
| и −a
k
−1 6
∆
k
− a
k
−1 6
a
k
− a
k
−1 6
6 2a
k
−1
− a
k
−1
= После того как мы распределим по двум группам все числа,
получим группы с суммами и S
2
, причём |S
1
− S
2
| 6 a
1
= 1. По условию число S
1
+ S
2
чётное, поэтому S
1
= S
2
16.16. Ответ да, можно. Занумеруем контакты лампы по порядку, а отверстия штепселя — в противоположном порядке.
Тогда контакт с номером k попадает в отверстие с номером a − где a — фиксированное число. (Точнее говоря, речь идёт не о самих номерах, а об их остатках отделения на 7, но номера совпадают тогда и только тогда, когда совпадают остатки) Нам нужно выбрать так, чтобы числа k и a − k давали одинаковые остатки при делении нате. число 2k давало такой же остаток, как и Легко убедиться, что когда k пробегает все остатки при делении на 7, то 2k тоже пробегает все остатки. а) Девять гирь весом n, n + 1, . . . , n + 8 можно разложить натри равные повесу кучи 1) n, n + 4, n + 8; 2) n + 1, n + 5, n + 6;
3) n + 2, n + 3, n + 7. Это позволяет разложить натри равные повесу кучи гири весом 1, 2, . . . , 549 = 61 · 9. Оставшиеся шесть гирь весом 550, 551, . . . , 555 можно разложить натри равные повесу кучи следующим образом 1) 550 и 555; 2) 551 и 554; 3) 552 и б) Разложим девять гирь весом n
2
, (n + 1)
2
, . . . , (n + натри кучи следующим образом 1) n
2
, (n + 5)
2
, (n + 7)
2
; 2) (n + 1)
2
,
(n
+ 3)
2
, (n + 8)
2
; 3) (n + 2)
2
, (n + 4)
2
, (n + 6)
2
. Первые две кучи

Решения задач
217
весят одинаково, а вес третьей кучи наг меньше. Поэтому гирь весом n
2
, (n + 1)
2
, . . . , (n + можно разложить на 9 куч так, что 6 куч будут одного веса, а ещё 3 кучи будут весить каждая наг меньше, чем первые 6. Из этих девяти куч можно сложить равные повесу кучи. Таким образом, 27k гирь весом 1 2
, 2 2
,
3 2
, . . . , можно разложить на 3 равные повесу кучи. При 3 получаем требуемое утверждение. Отнесём к первому классу все числа, в записи которых встречается чётное число двоек, а ко второму классу — все числа,
в записи которых встречается нечётное число двоек. Два числа одного класса либо содержат одинаковое число двоек, либо водном числе двоек по крайней мерена две больше, чем в другом. Если два числа различны, тона каком-то месте водном числе стоит а в другом числе стоит 2; если же двоек у этих чисел одинаковое количество, то таких мест по крайней мере два. Если водном числе двоек по крайней мерена две больше, чем в другом, то по крайней мере двум двойкам в записи первого числа соответствуют единицы в записи второго числа. Ответ да, можно. Пусть A — квадрат со стороной который разбит на квадраты со стороной 1, ив каждом из них написано натуральное число. Сопоставим ему квадрат+ 2
n
A
A
A
+ со стороной 2
n
+1
. Если мы начнём с квадрата со стороной 1, в котором написано число 1, то последовательно заполним весь прямой угол. Ясно, что при этом в каждом квадрате со стороной в каждом ряду квадратов со стороной 1, параллельном одной из сторон прямого угла, любое число от 1 до встречается ровно один раз

ГЛАВА ПРИНЦИП ДИРИХЛЕ. ПРАВИЛО
КРАЙНЕГО
Самая популярная формулировка принципа Дирихле такова:
«Если в n клетках сидит m зайцев, причём m > n, то хотя бы водной клетке сидят по крайней мере два зайца. На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач.
Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь зайцы и клетки и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден;
далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод даёт неконструктивное доказательство (мы, естественно, немо- жем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть, а попытка дать конструктивное доказательство, те. доказательство путём явного построения или указания требуемого объекта, может привести к гораздо большим трудностям. Остатки отделения. Докажите, что десятичная запись рационального числа является периодической дробью.
З а меча ни е. По поводу обратного утверждения см. задачу. Докажите, что если натуральные числа a и b взаимно простые, то a
n
− 1 делится на b для некоторого натурального. Пусть p < q — натуральные числа, причём q не делится на 2 и на 5. Согласно задаче 17.2 можно выбрать n

Условия задач
219
так, что 10
n
− 1 делится на q. Докажите, что p/q — чисто периодическая дробь, длина периода которой делится на n.
* * *
17.4. Докажите, что из любых ста целых чисел можно выбрать одно или несколько чисел так, чтобы их сумма оканчивалась двумя нулями. Из чисел 1, 2, . . ., n выбрано более+ 1 различных чисел. Докажите, что одно из выбранных чисел делится на другое. Простые числа a
1
, a
2
, . . . , образуют возрастающую арифметическую прогрессию и a
1
>
p. Докажите, что если p — простое число, то разность прогрессии делится на p.
17.7. Пусть n > 1 — натуральное число, e — наименьшее целое число, превосходящее. Докажите, что для любого натурального числа a, взаимно простого с n, можно выбрать натуральные числа x и y, не превосходящие e − 1, так, что ±x (mod См. также задачу 15.10.
17.2. Разные задачи. Докажите, что среди любых n > 2 человек найдутся два человека, имеющих одинаковое число знакомых среди этих n человек. Докажите, что любая последовательность из mn + попарно различных чисел содержит либо возрастающую последовательность из m + 1 чисел, либо убывающую последовательность из n + 1 чисел. Числа [a], [2a], . . ., [Na] различны между собой,
и числа [1/a], [2/a], . . . , [M/a] тоже различны между собой.
Найдите все такие a.

Глава 17. Принцип Дирихле. Правило крайнего. Приближения иррациональных чисел
рациональными
17.11. Пусть a
— иррациональное число. Докажите, что существует бесконечно много пар взаимно простых чисел, y, для которых −
a
| < 1/y
2
17.12. Пусть a
— положительное число. Докажите, что для любого числа C > 1 можно выбрать натуральное число и целое число y так, что x < C и |x
a
− y| 6 1/C.
17.13. а) Пусть a
— иррациональное число. Докажите,
что для любых чисел a < b можно выбрать целые числа и n, для которых a < m
a
− n < б) Докажите, что числа m и n можно выбрать натуральными. Правило крайнего
Правило крайнего заключается в том, чтобы рассмотреть тот элемент, для которого некая величина имеет наибольшее или
(наименьшее) значение. Правило крайнего помогает при решении многих задач. На полях бесконечной шахматной доски написаны натуральные числа так, что каждое число равно среднему арифметическому четырёх соседних чисел — верхнего,
нижнего, левого и правого. Докажите, что все числа на доске равны между собой. В каждой клетке бесконечного листа клетчатой бумаги написано какое-то действительное число. Докажите,
что найдётся клетка, в которой написано число, не превосходящее чисел, написанных по крайней мере в четырёх из восьми граничащих с ней клеток. В каждой клетке прямоугольного листа клетчатой бумаги написано число, причём в каждой клетке, нестоящей с края, написано среднее арифметическое чисел,
стоящих в соседних клетках. Все написанные числа различны. Докажите, что наибольшее число стоит с края (те. по крайней мере одна из соседних клеток отсутствует

Решения задач. Есть 13 гирь, каждая из которых весит целое число граммов. Известно, что любые 12 из них можно так разложить на 2 чашки весов, по 6 гирь на каждой, что наступит равновесие. Докажите, что все гири одного веса. а) Из чисел 1, 2, 3, 4, 5, 6, 7, . . ., 199, 200 произвольно выбрали 101 число. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.
б) Из двухсот чисел 1, 2, 3, . . ., 199, 200 выбрали одно число, меньшее 16, и ещё 99 чисел. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое. Из одной бактерии получилось n бактерий следующим образом. Сначала бактерия разделилась на две, затем одна из двух получившихся бактерий разделилась на две,
затем одна из трёх получившихся бактерий разделилась на две и т. д. Докажите, что для любого натурального числа 6 n/2 в некоторый момент существовала бактерия, число потомков которой среди получившихся в конце n бактерий не меньше a и не больше 2a − 1.