Гашков С.Б. Современная элементарная алгебра в задачах и решениях

Подождите немного. Документ загружается.

С. Б. ГАШКОВ

СОВРЕМЕННАЯ

ЭЛЕМЕНТАРНАЯ

АЛГЕБРА

В ЗАДАЧАХ И УПРАЖНЕНИЯХ

Москва

Издательство МЦНМО

2006

УДК 512

ББК 22.141я721.6

Г12

Гашков С. Б.

Г12 Современная элементарная алгебра в задачах и решениях.

—

М.: МЦНМО, 2006.

—

328 с.

ISBN 5

94057

211

Эта книга представляет собой учебное пособие по алгебре для учащихся 10

–

классов математических школ, содержащее многочисленные задачи и упражнения.

Её основу составили лекции, читавшиеся автором в ФМШ МГУ.

Книга может представлять интерес также для преподавателей математики, сту

дентов и для всех интересующихся математикой.

ББК 22.141я721.6

Редакторы: Устинов А.В., Коробкова Т.Л.

Сергей Борисович Гашков

Современная элементарная алгебра в задачах и упражнениях.

Подписано в печать 15.11.2005 г. Формат 60 × 90

. Бумага офсетная.

Печать офсетная. Печ. л. 20,5. Тираж 2000 экз. Заказ № .

Издательство Московского центра

непрерывного математического образования

119002, Москва, Большой Власьевский пер., 11. Тел. 241

83.

ООО

Пресс

. 610033, г. Киров, ул. Московская, 122.

Отпечатано в полном соответствии с качеством предоставленных диапозитивов

в ОАО

Дом Печати

—

ВЯТКА

. 610033, г. Киров, ул. Московская, 122.

Книги издательства МЦНМО можно приобрести в магазине

Математическая книга

Большой Власьевский пер., д. 11. Тел. 241

–

85. E

mail: biblio@mccme.ru

ISBN 5

94057

211

Предисловие

Предлагаемая вниманию читателя книга представляет собой учебное

пособие по алгебре для учащихся 10

х и 11

х классов физико

математи

ческих школ. Его основу составили записи лекций, читавшихся автором

в специализированном учебно

научном центре МГУ им. М. В. Ломоно

сова

––

школе имени академика А. Н. Колмогорова, более известной под

названиями ФМШ МГУ и интернат МГУ. Книга покрывает курс алгебры

для учащихся 10

х классов СУНЦ (и аналогичных ему учебных заведе

ний) и содержит основную часть обязательного курса алгебры для 11

классов.

По традиции, установленной А. Н. Колмогоровым, курс алгебры

для

ФМШат

, который читали в разное время сам А. Н. Колмо

горов, В. И. Арнольд, В. М. Алексеев, Н. Б. Алфутова, В. В. Вавилов,

О. Н. Василенко, И. Б. Гашков, С. Б. Гашков, А. А. Егоров, А. Н. Зем

ляков, В. А. Колосов, Ю. В. Нестеренко, В. Ф. Пахомов, А. А. Русаков,

Т. Н. Трушанина, А. В. Устинов, О. А. Чалых, В. Н. Чубариков (приношу

свои извинения тем, кого не вспомнил или о ком не знал), состоит

из двух частей: некоторого обязательного набора понятий, конструк

ций и теорем (эта часть является общей для всех лекционных курсов

алгебры, читавшихся в этой школе) и решения некоторой интересной

содержательной проблемы (например, построение циркулем и линейкой

правильных n

угольников, теорема Абеля

–

Руффини о неразрешимости

в радикалах общего уравнения пятой степени, квадратичный закон вза

имности и т. п.). Вторую часть курса лектор определяет в соответствии

со своими вкусами.

В этой книге излагается первая часть курса, а также некоторый ва

риант дополнительных глав. В ней много задач, в основном довольно

трудных.

Она может служить учебным пособием по алгебре и для студентов

вузов.

Автор выражает глубокую благодарность В. А. Колосову, материалы

которого существенно использовались при подготовке книги, а также

А. В. Устинову за тщательное редактирование.

Автор приносит извинения за оставшиеся в книге неточности и небреж

ности и за то, что не успел подготовить ее к 40

летию ФМШ МГУ

и 100

летию А. Н. Колмогорова.

Глава I. Числа и комбинаторика

§ 1.1. Позиционные системы счисления

Еще средневековые математики Ближнего Востока нашли простой

подход к вычислениям с дробными числами

––

использование десятич

ных позиционных дробей. Позиционная десятичная система попала туда,

видимо, из Индии, хотя позиционные дроби, правда не десятичные, а ше

стидесятеричные, были известны еще в Древнем Шумере, а десятичные

дроби по существу были известны в Древнем Китае. Отметим еще, что

двадцатеричную систему знали индейцы майя. Здесь уместно напомнить

читателю, что запись

...a

−1

...a

−k

)

в позиционной b

ичной системе означает число, равное

+ ... + a

b + a

+ a

−1

+ ... + a

−k

где

+ ... + a

b + a

––

его целая, а

−1

+ ... + a

−k

––

дробная часть. В западных странах вместо запятой, отделяющей целую

часть от дробной, используется точка.

Почему обычно используется десятичная система? Главным образом,

в силу традиции (которая, вероятно, основывается на том, что число паль

цев на обеих руках равно обычно 10; индейцы майя, возможно, не забыли

и про ноги). Как писал Паскаль *, десятичная система ничем не луч

ше систем с другими основаниями. Более того, с некоторых точек зре

ния удобнее другие системы. Так, много поклонников имеет двенадца

теричная система (идущая от счета дюжинами и гроссами

––

дюжинами

дюжин). Возможно, к их числу относился и Г. Дж. Уэллс (см. его ро

ман

Когда спящий проснется

). Преимущество этой системы в том,

что 12 имеет больше делителей, чем 10, что несколько упрощает деление.

* Б. Паскаль (Blaise Pascal, 1623

–

1662)

––

знаменитый французский математик, физик,

религиозный философ и писатель.

§ 1.1. Позиционные системы счисления 5

С этой точки зрения еще лучше шестидесятеричная система (но таб

лица умножения в этой системе вгоняет в дрожь). Остатки от было

го распространения этой системы видны в картографии и астрономии,

а алгоритм перевода из этой системы в десятичную запаян в любом

калькуляторе для научных расчетов (речь идет о переводе из градусной

меры в десятичную и обратно). Кстати, первая запись дробного чис

ла в позиционной системе в Европе была сделана в XIII в. знамени

тым Фибоначчи: корень уравнения x

+ 2x

+ 10x = 20 он нашел в виде

◦

′

′′

′′′

Есть поклонники и у восьмеричной и шестнадцатеричной систем. Пер

вую из них хотел вести в Швеции Карл XII (который, возможно, пришел

к этой идее самостоятельно), но ряд обстоятельств помешали этому про

грессивному начинанию (среди них, вероятно, и занятость короля в во

енных компаниях, в частности, под Полтавой в России). Преимущество

этих систем в том, что легко осуществляется перевод в двоичную систему

и обратно.

Двоичная система в каком

то смысле была известна в Древнем Китае.

В классической книге

И цзин

(

Книга перемен

) приведены диаграм

мы, так называемые Фу

си, первая из которых имеет вид

, а послед

няя (шестьдесят четвертая)

––

вид

(нулям и единицам соответствуют

сплошные и прерывистые линии). Китайцы не поленились придумать для

этих диаграмм специальные иероглифы и названия.

Возможно, что идея двоичной системы была известна и древним ин

дийцам. Об этом, например, говорит известная легенда об изобретателе

шахмат, который скромно попросил (после настояний магараджи, кото

рому очень понравилась игра) себе в награду положить одно зерно на уг

ловую клетку шахматной доски и удваивать количество зерен на каждой

следующей клетке.

В Европе двоичная система, видимо, появилась уже в новое вре

мя. Об этом свидетельствует система объемных мер, применяемая

английскими виноторговцами: два джилла = полуштоф, два полуштофа =

= пинта, две пинты = кварта, два кварты = потл, два потла = галлон, два

галлона = пек, два пека = полубушель, два полубушеля = бушель, два

бушеля = килдеркин, два килдеркина = баррель, два барреля = хогзхед,

два хогзхеда = пайп, два пайпа = тан.

Читатели исторических романов знакомы с пинтами и квартами. Ча

стично эта система дожила и до нашего времени (нефть и бензин до сих

пор меряют галлонами и баррелями). Удобство двоичной системы при

взвешивании демонстрируют также помещенные в конце параграфа зада

чи, вторая из которых заимствована из материалов жюри международных

олимпиад, а третья известна, вероятно, со средневековых времен.

6 Глава I. Числа и комбинаторика

Пропагандистом двоичной системы был знаменитый Г. В. Лейбниц *

(получивший от Петра I звание тайного советника). Он отмечал особую

простоту алгоритмов арифметических действий в двоичной арифметике

в сравнении с другими системами и придавал ей определенный фило

софский смысл. Говорят, что по его предложению была выбита медаль

с надписью

Для того, чтобы вывести из ничтожества все, достаточно

единицы

Известный современный математик Д. Данциг ** о нынешнем положе

нии дел сказал:

Увы! То, что некогда возвышалось как монумент моно

теизму, очутилось в чреве компьютера

. Причина такой метаморфозы

––

не только уникальная простота таблицы умножения в двоичной систе

ме, но и особенности физических принципов, на основе которых работает

элементная база современных ЭВМ (за последние 40 лет она неодно

кратно менялась, но двоичная система и булева алгебра по

прежнему

вне конкуренции).

Отметим еще, что двоичная система находит применения и в других

математических задачах, например при анализе известной игры

Ним

Игра состоит в следующем: на столе лежит несколько кучек спичек, и два

игрока по очереди выбирают одну из кучек и забирают из нее сколь

ко угодно спичек (хоть все); проигрывает тот, кто забирает последнюю.

Эпизод с этой игрой неоднократно повторяется в известном французском

фильме

Прошлым летом в Мариенбаде

Упомянутая стратегия поддается для реализации даже на специализи

рованных машинах. Одна из таких машин была выставлена после войны

в Берлине на английской выставке и с успехом конкурировала с нахо

дящимся рядом бесплатным пивным залом. Известный популяризатор

математики Мартин Гарднер в одной из своих книг пишет, что Алан Тью

ринг *** вспоминал о том, как популярность этой машины повысилась

еще больше после победы над тогдашним бундесминистром экономики

Л. Эрхардом.

Некоторую конкуренцию двоичной системе как по простоте арифме

тических алгоритмов, так и по количеству применений в математических

задачах может составить троичная система, в частности ее вариант, на

зываемый уравновешенной троичной системой, в которой вместо цифры 2

используется цифра −1.

* Г. В. Лейбниц (Gottfried Wilhelm Leibniz, 1646

–

1716)

––

великий немецкий математик

и философ, один из основоположников математического анализа.

** Д. ван Данциг (David van Danzig, 1900

–

1959)

––

голландский математик, изобретатель

симплекс

метода в линейном программировании.

*** А. Тьюринг (Alan Mathison Turing, 1912

–

1954)

––

английский математик, один из со

здателей теории алгоритмов. При его участии был построен первый английский компьютер.

§ 1.1. Позиционные системы счисления 7

Представление о ней дает следующая в конце параграфа задача 6,

опубликованная в книге Баше де Мезириака * в XVII в.

Троичная система применяется при объяснении следующего фокуса

Жергонна **. Зритель запоминает одну из 27 карт и выкладывает их в три

стопки по 9 карт картинками вверх (первая карта идет в первую стопку,

вторая

––

во вторую, третья

––

в третью, четвертая

––

в первую и т. д.). Фо

куснику сообщается, в какой из стопок задуманная карта, потом стопки

складываются в любом из шести возможных порядков (не перетасовы

вая карты внутри стопок) и раскладываются снова в три стопки, начиная

с верхней карты, потом складываются опять и процедура повторяется

в третий раз (каждый раз сообщается, в какую из стопок легла запо

мненная карта). Фокусник каждый раз замечает, куда легла стопка с за

помненной картой

––

сверху (это отмечается в уме символом 0), в середину

(символ 1), или в низ колоды (символ 2), и составляет из этих символов

трехзначное число в троичной системе счисления, ставя первый из за

меченных символов в младший разряд, следующий символ

––

во второй

и последний символ

––

в старший разряд. К полученному числу прибав

ляется единица и отсчитывается столько карт, начиная с верхней карты

колоды

––

последняя из отсчитанных карт и есть запомненная зрителем.

Имеется еще один вариант фокуса Жергонна, но с другим способом

раскладки карт. Колода из 27 карт раскладывается в три стопки в сле

дующем порядке: первая карта

––

в первую стопку, вторая

––

во вторую,

третья

––

в третью, четвертая

––

опять в третью, пятая

––

во вторую, ше

стая

––

в первую и т. д. Одна из карт запоминается зрителем и указывается

стопка, в которой она лежит, и все повторяется еще два раза. Способ уга

дывания тот же самый. Можно показывать тот же фокус и с 21 картой,

но тогда надо раскладывать карты самому и стопку с задуманной картой

всегда класть в середину колоды.

Уравновешенная система может быть рассмотрена и для любого нату

рального основания, правда, при четном основании запись в ней переста

ет быть однозначной. Преимуществом уравновешенных систем является

то, что в них записываются и отрицательные числа без знака минус перед

записью, а также то, что таблица умножения в этих системах в сравнении

с обычными примерно в четыре раза короче, как отметил О. Л. Коши ***.

* Баше де Мезириак (Gaspard Claude Bachet de Mésiriac, 1587

–

1638)

––

французский

математик и поэт, автор одной из первых книг по занимательной математике.

** Ж. Жергонн (Josef Diaz Gergonne, 1771

–

1859)

––

французский математик, член

корреспондент Парижской академии наук.

*** О. Л. Коши (Augustin Louis Cauchy, 1789

–

1857)

––

великий французский математик,

член Петербургской академии наук. По политическим взглядам ультрароялист, сторонник

Бурбонов, клерикал. Восемь лет провел в эмиграции.

8 Глава I. Числа и комбинаторика

Можно рассматривать системы счисления и с отрицательным осно

ванием b, но неотрицательными цифрами 0, 1, .. ., −b −1. Любое целое

число можно представить в этой системе без знака.

Основатель теории множеств Георг Кантор * предложил рассматри

вать системы счисления со смешанными основаниями. Запись в таких

системах выглядит так:

... a

, a

; a

−1

, a

−2

, a

−3

, ...,

... b

, b

; b

−1

, b

−2

, b

−3

, ...,

где b

––

основания, a

––

цифры, 0 6 a

< b

, и расшифровывается следу

ющим образом:

... a

+ a

−1

+ a

−2

·b

−1

) + . ..

Частным случаем таких систем является факториальная, которая по

лучается при b

= k + 2, b

−k

= k + 1. Используя ее, можно любое нату

ральное число представить в виде

n−1

n! + ... + a

2! + a

1!,

где 0 6 a

6 k + 1.

Системы со смешанными основаниями всем известны из повседнев

ной жизни. Например,

1 неделя, 2 дня, 3 часа, 4 минуты, 56 секунд,

789 миллисекунд

равно

1, 2, 3, 4, 56; 789;

7, 24, 60, 60; 1000

секунд.

И, наконец, вернемся к обычной позиционной системе и рассмотрим

вопрос о представлении отрицательных чисел в ЭВМ. Обычный способ

записи отрицательных чисел состоит в постановке знака минус перед за

писью модуля этого числа. Этот способ называется прямым кодом. Для

ЭВМ, как правило, удобнее дополнительный код, когда, например, число

−(123456789)

записывается как

− (123456789)

= (876543211)

При этом операции сложения

вычитания фактически проводятся по мо

дулю 10

и не возникает проблемы

минус нуля

. Дополнительный код

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

мощью обычного алгоритма вычитания как раз и получается разность,

записанная в дополнительном коде. Но есть у него и недостатки. Кро

ме дополнительного кода рассматривают также обратный код, в котором,

* Г. Кантор (Georg Cantor, 1845

–

1918)

––

знаменитый немецкий математик. Родился

в Санкт

Петербурге.

§ 1.1. Позиционные системы счисления 9

например, число −(123456789)

записывается как 876543210 (каждая

цифра дополняется до 9). В этом коде сложение и вычитание произво

дятся фактически по модулю 10

−1.

Задачи и упражнения к § 1.1

1. Оцените, сколько тонн зерна придется выплатить магарадже.

2*. За какое наименьшее количество взвешиваний на чашечных весах

можно отвесить один килограмм сахарного песка, если имеется лишь одна

однограммовая гирька?

3*. Чтобы взвесить любое число граммов песка от 1 до n граммов

за одно взвешивание, достаточно иметь гири весом 1, 2, 4, . .., 2

граммов,

где m = ⌊log

n⌋, и меньшего числа гирь недостаточно, если песок лежит

на одной чашке весов, а гири разрешается ставить на вторую чашку.

4**. Укажите выигрывающую стратегию в игре

Ним

5. Любое целое число от −(3

−1)

2 до (3

−1)

2 может быть одно

значно представлено в виде

n−1

+ ... + a

3 + a

где цифры a

= 0 или ±1.

6*. Допустим, что при взвешивании разрешается класть гири и на чаш

ку весов с грузом. Тогда для того, чтобы взвесить любой груз от 1

до (3

−1)

2 граммов за одно взвешивание, достаточно иметь гири весом

1, 3, 9, ..., 3

n−1

граммов, и меньшего количества гирь недостаточно.

7*. Объясните фокус Жергонна.

8*. Докажите, что во втором варианте фокуса Жергонна (с 21 картой)

после трех сдач задуманная карта окажется точно в середине колоды, т. е.

на одиннадцатом месте от любого края.

9. Запишите число (1234567890)

в уравновешенной десятичной си

стеме счисления.

10. Докажите, что любое ненулевое целое число имеет единственное

знакопеременное двоичное представление

−2

+ ... + (−1)

где α

< ... < α

11. Представьте в

негадесятичной

системе (т. е. в системе с отри

цательным основанием −10) числа

(1234567890)

, −(1234567890)

12*. Запишите в факториальной системе счисления число e

––

осно

вание натуральных логарифмов.

10 Глава I. Числа и комбинаторика

13. Докажите, что остаток от деления произвольного числа на 9 ра

вен остатку от деления на 9 суммы его цифр в записи по основанию 10.

Такой же признак делимости справедлив и для числа 3.

14. Обозначим сумму десятичных цифр числа a через ν

(a). Найдите

(ν

(4444

4444

))).

Целой частью числа x называется такое целое число n = ⌊x⌋, кото

рое удовлетворяет неравенствам n 6 x < n + 1. Дробной частью чис

ла x называется число {x} = x −⌊x⌋. Целое число m = ⌈x⌉ такое, что

m −1 < x 6 m, называется верхней целой частью. Число

kxk = min(x − ⌊x⌋ , ⌈x⌉−x)

называется расстоянием до ближайшего целого числа, а само это це

лое число обозначается ((x)) в случае, если x 6= n + 1

2, т. е. не является

полуцелым. В последнем случае функция ((x)) естественным образом

не определена, но ее можно доопределить, если угодно, например, ра

венством ((n + 1

2)) = n. Название для последней функции не является

общепринятым, впрочем, общепринятого названия и нет.

Для целой части в последнее время (благодаря книгам Д. Кнута и рас

пространению издательской системы T

X) входит в моду название

пол

и обозначение ⌊x⌋, а верхнюю целую часть все чаще называют

потол

ком

и обозначают ⌈x⌉. В старое время целую часть называли иногда

французским термином

антье

15. Докажите, что функции {x}, kxk периодичны с наименьшим пери

одом единица и постройте их графики. Проверьте, что

⌈x⌉ = −⌊−x⌋ , ((x)) = ⌊2x⌋−⌊x⌋ (при x не полуцелом),

kxk = |x − ((x))| (при x не полуцелом),

kxk = min ({x}, 1 − {x}) =

−



{x} −



16. Докажите, что ⌊x + 1

2⌋= ⌊2x⌋− ⌊x⌋, ⌊x⌋+ ⌊y⌋+ 1 > ⌊x + y⌋>

> ⌊x⌋ + ⌊y⌋, 0 6 ⌊2x⌋−2⌊x⌋ 6 1, ⌊2x⌋ + ⌊2y⌋> ⌊x⌋+ ⌊y⌋+ ⌊ x + y⌋,

⌊⌊x⌋

n⌋= ⌊x

n⌋.

17. Докажите, что ⌈x −1

2⌉= ⌈2x⌉− ⌈x⌉, ⌈x⌉+ ⌈y⌉−1 6 ⌈x + y⌉6

6 ⌈x⌉ + ⌈y⌉, 0 6 2⌈x⌉−⌈2x⌉ 6 1, ⌈2x⌉ + ⌈2y⌉6 ⌈x⌉+ ⌈y⌉+ ⌈ x + y⌉,

⌈⌈x⌉

n⌉= ⌈x

n⌉.

18. Докажите, что при x не полуцелом

((x)) =

x +

−

2x + 1