WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 27 |
Алгебра и теория чисел для математических школ Н. Б. Алфутова, А. В. Устинов September 3, 2003 УДК 51 ББК 21.1 А45 Алфутова Н. Б. Устинов А. В.

А45 Алгебра и теория чисел. Сборник задач для математических школ.— М.: МЦНМО, 2002.— 264 с.

ISBN 5-94057-038-0 Настоящее пособие представляет собой сборник задач по математике, предназначенный прежде всего для учеников старших классов с углубленным изучением математики, интересующихся точными науками. Он также будет полезен преподавателям математики и студентам, изучающим математику в высших учебных заведениях. Значительная часть материала может быть использована для подготовки к письменным и устным вступительным экзаменам в ВУЗы.

Основу сборника составляют задачи, к курсу алгебры, который в 1995— 2000 годах читался в школе-интернате им. А. Н. Колмогорова.

ББК 21.1 © Алфутова Н. Б., Устинов А. В., 2002.

ISBN 5-94057-038-0 © МЦНМО, 2002.

Предисловие Настоящее пособие представляет собой сборник задач по математике, предназначенный прежде всего для учеников старших классов, интересующихся точными науками. Он также будет полезен преподавателям математики и студентам, изучающим математику в высших учебных заведениях. Значительная часть материала может быть использована для подготовки к письменным и устным вступительным экзаменам в ВУЗы.

Основу сборника составляют задачи к курсу алгебры, который в 1995 – 2000 годах читался О. А. Чалых, Н. Б. Алфутовой и А. В. Устиновым. В приложении А приведена программа этого курса. Для того, чтобы сделать содержание книги более широким и целостным, авторы включили в нее дополнительный материал, собрав и упорядочив задачи из других источников.

Математические курсы, читаемые в школе-интернате им. А. Н. Колмогорова, традиционно содержат разделы, которые можно назвать смежными. Они находятся на стыке алгебры с комбинаторикой, геометрией, теорией чисел и математическим анализом. Поэтому некоторые задачи из книги имеют к алгебре лишь косвенное отношение. Эти задачи призваны подчеркнуть связь различных разделов математики и проиллюстрировать многообразие методов.

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

При подготовке пособия использовались различные учебники и монографии, сборники олимпиадных и конкурсных задач, большая часть упражнений была почерпнута из многочисленных публикаций журнала «Квант». В результате работы над книгой был создан своеобразный путеводитель, помещенный в приложение Б. В нем по каждой из тем задачника даны ссылки на соответствующие публикации. К сожалению, в настоящий момент не представляется возможным указать авторов всех задач, вошедших в книгу, и перечислить все оригинальные источники. Часть материала встречается сразу в нескольких сборниках. Со многими задачами авторы познакомились еще за время своего обучения в школе-интернате. Некоторые упражнения рождались в разговорах с коллегами по кафедре математики.

В настоящее время в центре дополнительного образования «Дистантное обучение» идет работа над созданием сетевого аналога курса алгебры с использованием материалов данной книги. Авторы надеятся, что в ближайшее время он также станет доступен читателям.

Авторы приносят глубокую благодарность педагогам и математикам, работавшим в разное время в ФМШ № 18 при МГУ (позднее в школе им. А. Н. Колмогорова), опыт которых отражен в этой книге.

Особенно авторы благодарят В. В. Вавилова, А. А. Егорова, И. Д. Кана, которые взяли на себя труд прочесть предварительные варианты книги, за их многочисленные добавления, исправления и полезные советы.

Отдельное спасибо О. А. Соловьеву за неизменную TEX-ническую поддержку.

Авторы будут благодарны читателям за отзывы, критические замечания, предложения и новые задачи. Их можно отправлять по электронной почте или по адресу: 117630, Москва, ул. акад. Челомея, д. 8 Б, ЦДО «Дистантное обучение».

Н. Б. Алфутова alpha@pisem.net А. В. Устинов ustinov@mech.math.msu.su Обозначения В списке указаны страницы, на которых введены эти обозначения.

Обозначение Смысл Стр.

N множество натуральных чисел Z множество целых чисел Q множество рациональных чисел [x] целая часть числа x (наибольшее целое, не превосходящее x) {x} дробная часть числа x: {x} = x - [x] n! факториал: n! = 1 · 2 ·... · n {xn} последовательность x1, x2,..., xn,...

b | a b делит a.

.

a. b a кратно b a b mod m a сравнимо с b по модулю m класс вычетов по модулю m (ak... a0)q запись числа в q-ичной системе счисления (a1,..., an) наибольший общий делитель чисел a1,..., an [a1,..., an] наименьшее общее кратное чисел a1,..., an [a0; a1,..., an] цепная дробь (n) функция Эйлера (n) количество положительных делителей числа n (n) сумма положительных делителей числа n Fn числа Фибоначчи i мнимая единица i = -1 C множество комплексных чисел z комплексно сопряженное число к числу z arg z аргумент комплексного числа z |z| модуль комплексного числа z отношение длины окружности к диаметру e основание натуральных логарифмов = ( 5 + 1)/2 — число Фидия оператор конечной разности k число k-размещений с повторениями из n элементов n Ak число k-размещений без повторений из n элементов n Pn число перестановок из n элементов Ck число k-сочетаний с повторениями из n элементов n Ck число k-сочетаний без повторений из n элементов n Cn числа Каталана En репьюнит порядка n: En = 11... 1 n Глава Метод математической индукции 1. Аксиома индукции Аксиома индукции. Если известно, что некоторое утверждение верно для 1, и из предположения, что утверждение верно для некоторого n, вытекает его справедливость для n+1, то это утверждение верно для всех натуральных чисел.



1.1. Деление с остатком. Докажите, что если a и b — целые числа и b = 0, то существует единственная пара чисел q и r таких, что a = bq + r, 0 r < |b|.

1.2. Позиционная система счисления. Докажите, что при целом q 2 каждое натуральное число n может быть единственным образом представлено в виде n = akqk + ak-1qk-1 +... + a1q + a0, где 0 a0,..., ak < q. (См. также 3.125, 11.68.) Определение. Если ak, ak-1,..., a1, a0 — цифры числа n в q-ичной системе счисления, то используется запись n = (akak-1... a1a0)q.

Для записи числа в десятичной системе счисления используется также запись (akak-1... a1a0)10 = akak-1... a1a0.

1.3. Пусть {an} = a0, a1,..., an,... — периодическая последовательность, то есть для некоторого натурального T an+T = an (n 0).

Докажите, что среди всех периодов этой последовательности существует период наименьшей длины t, причем T делится на t без остатка.

1.4. Аксиомы индукции. Докажите, что аксиома индукции равносильна любому из следующих утверждений. (См. также 12.1.) 1) Всякое непустое подмножество натуральных чисел содержит наименьшее число.

2. Тождества, неравенства и делимость 2) Всякое конечное непустое подмножество натуральных чисел содержит наибольшее число.

3) Если некоторое множество натуральных чисел содержит 1 и вместе с каждым натуральным числом содержит следующее за ним, то оно содержит все натуральные числа.

4) Если известно, что некоторое утверждение верно для некоторого a, и из предположения, что утверждение верно для всех натуральных чисел k, таких, что a k < n вытекает его справедливость для n, то это утверждение верно для всех натуральных чисел k a.

5) (Обратная индукция.) Если известно, что некоторое утверждение верно для 1 и 2, и из предположения, что утверждение верно для некоторого n > 1, вытекает его справедливость для 2n и n - 1, то это утверждение верно для всех натуральных чисел.

1.5. Число x таково, что число x + — целое. Докажите, что при x любом натуральном n число xn + также является целым. (См. такxn же 7.46.) 1.6. Даны натуральные числа x1,..., xn. Докажите, что число (1 + x2) ·... · (1 + x2 ) 1 n можно представить в виде суммы квадратов двух натуральных чисел.

(См. также 7.14.) 1.7. Числовая последовательность A1, A2,..., An,... определена равенствами A1 = 1, A2 = -1, An = -An-1 - 2An-2 (n 3).

Докажите, что при n 2 число 2n+2-7A2 является полным квадратом.

n 2. Тождества, неравенства и делимость Определение. Через n! (читается «n факториал») обозначается произведение всех натуральных чисел от 1 до n:

n! = 1 · 2 ·... · n.

Для удобства считается, что 0! = 1.

В задачах 1.8 – 1.14 докажите тождества.

1.8. 1 + 3 + 5 +... + (2n - 1) = n2.

n(n + 1)(2n + 1) 1.9. 12 + 22 +... + n2 =.

8 1. Метод математической индукции n(2n - 1)(2n + 1) 1.10. 12 + 32 +... + (2n - 1)2 =.

1.11. 13 + 23 +... + n3 = (1 + 2 +... + n)2.

n(n + 1)(n + 2)(n + 3) 1.12. 1 · 2 · 3 + 2 · 3 · 4 +... + n(n + 1)(n + 2) =.

12 22 n2 n(n + 1) 1.13. + +... + =.

1 · 3 3 · 5 (2n - 1)(2n + 1) 2(2n + 1) 1.14. 1 · 1! + 2 · 2! +... + n · n! = (n + 1)! - 1.

1.15. Факториальная система счисления. Докажите, что каждое натуральное число n может быть единственным образом представлено в виде n = a1 · 1! + a2 · 2! + a3 · 3! +..., где 0 a1 1, 0 a2 2, 0 a3 3,...

1.16. Числа a0, a1,..., an,... определены следующим образом:

a0 = 2, a1 = 3, an+1 = 3an - 2an-1 (n 2).

Найдите и докажите формулу для этих чисел.

Определение. Пусть a — целое и b — натуральное числа. b называется делителем a, если существует целое число q такое, что a = bq.

В этом случае a называется кратным b, а q — частным от деления a на b.

Соотношение «b делит a» записывается в виде b | a или в виде.

.

a. b («a кратно b»). Причем эти записи всегда включают в себя предположение, что b = 0.

Если b не является делителем a, то будем писать b a.

Докажите, что в задачах 1.17 – 1.24, указанные соотношения выполняются для любого натурального n.

.

.

1.17. 10n + 18n - 1. 27.

.

1.18. 11n+2 + 122n+1. 133.

.

.

1.19. 25n+3 + 5n · 3n+2. 17.

.

.

.

1.20. n3 + 5n. 6.

.

.

1.21. 62n+1 + 1. 7.

.

.

1.22. 32n+2 + 8n - 9. 16.

.

.

1.23. 4n + 15n - 1. 9.

n.

.

1.24. 23 + 1. 3n+1.

1.25. Докажите, что для всех натуральных n число, записываемое 3n единицами, делится на 3n.

2. Тождества, неравенства и делимость 1.26*. Из чисел от 1 до 2n выбрано n+1 число. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.

(См. также 2.34.) 1.27. Решите уравнение x(x x - 1) x(x - 1) ·... · (x - n + 1) 1 - + -... + (-1)n = 0.

1! 2! n! В задачах 1.28 – 1.36 докажите справедливость неравенств для натуральных n.

1 1 1 1.28. + + +... + < 2. (См. также 7.81.) 12 22 32 n 1 1 1.29. + +... + n.

n 1 (2n)! 4n 1.30. >.

(n!)2 n + 1 1 1 1.31. + +... + > (n > 1).

n + 1 n + 2 2n 1.32. Неравенство Бернулли. (1+x)n 1+nx при любом x > -1.





1.33. 2n > n.

1 · 3 · 5 ·... · (2n - 1) 1.34..

2 · 4 · 6 ·... · 2n 2n + 1.35. nn+1 > (n + 1)n (n > 2).

1.36. |x1 +... + xn| |x1| +... + |xn|, где x1,..., xn — произвольные числа.

1.37*. Неравенство между средним арифметическим и средним геометрическим. Докажите неравенство x1 +... + xn n x1 ·... · xn, n где x1,..., xn — положительные числа.

1.38. Докажите неравенство 2m+n-2 mn, где m и n — натуральные числа.

1.39. Для каких n выполняются неравенства:

а) n! > 2n; б) 2n > n2.

1.40. Вычислите произведение 23 - 1 33 - 1 n3 - · ·... · (n 2).

23 + 1 33 + 1 n3 + 10 1. Метод математической индукции 3. Индукция в геометрии и комбинаторике 1.41. Из квадрата клетчатой бумаги размером 16 16 вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на «уголки» из трех клеток.

1.42. Ханойская башня I. Головоломка «Ханойская башня» представляет собой 8 дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск и не помещая больший диск на меньший.

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

также 5.71.) 1.43. Ханойская башня II. Занумеруем колышки в задаче о Ханойской башне числами 1, 2, 3. Предположим, что требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й запрещено (Каждое перекладывание должно производится через 2-й колышек. Как и раньше, больший диск нельзя класть на меньший.) 1.44. Ханойская башня III. Сколько понадобится перекладываний, если в условии задачи 1.42 добавить дополнительное требование:

первый диск нельзя класть на второй колышек 1.45. Докажите, что квадрат можно разрезать на n квадратов для любого n, начиная с шести.

1.46. Докажите, что правильный треугольник можно разрезать на n правильных треугольников для любого n, начиная с шести.

1.47. Золотая цепочка. а) На постоялом дворе остановился путешественник, и хозяин согласился в качестве уплаты за проживание брать кольца золотой цепочки, которую тот носил на руке. Но при этом он поставил условие, чтобы оплата была ежедневной: каждый день должно быть отдано ровно на одно кольцо больше, чем в предыдущий день. Замкнутая в кольцо цепочка содержала 11 колец, а путешественник собирался прожить ровно 11 дней, поэтому он согласился. Какое наименьшее число колец он должен распилить, чтобы иметь возможность платить хозяину б) Из скольких колец должна состоять цепочка, чтобы путешественник мог прожить на постоялом дворе наибольшее число дней при условии, что он может распилить только n колец 1.48. Банк имеет неограниченное количество трех- и пятирублевых купюр. Докажите, что он может выдать ими без сдачи любое число рублей, начиная с восьми. (См. также 3.72.) 3. Индукция в геометрии и комбинаторике 1.49*. Гениальные математики. а) Каждому из двух гениальных математиков сообщили по натуральному числу, причем им известно, что эти числа отличаются на единицу. Они поочередно спрашивают друг друга: «Известно ли тебе мое число» Докажите, что рано или поздно кто-то из них ответит «да». Сколько вопросов они зададут друг другу (Математики предполагаются правдивыми и бессмертными.) б) Как изменится число заданных вопросов, если с самого начала известно, что данные числа не превосходят 1000 1.50. На сколько частей делят плоскость n прямых «общего положения», то есть таких, что никакие две не параллельны и никакие три не проходят через одну точку 1.51. На плоскости проведены n окружностей так, что любые две из них пересекаются в паре точек, и никакие три не проходят через одну точку. На сколько частей делят плоскость эти окружности 1.52. На сколько частей делят пространство n плоскостей, проходящих через одну точку, если никакие три не имеют общей прямой 1.53*. На сколько частей делят пространство n плоскостей «общего положения» И что это за «общее положение» 1.54. Плоскость поделена на области несколькими прямыми. Докажите, что эти области можно раскрасить в два цвета так, чтобы любые две соседние области были окрашены в разные цвета. (Соседними называются области, имеющие общий участок границы.) 1.55. Сумма углов n-угольника. Докажите, что произвольный n-угольник (не обязательно выпуклый) можно разрезать на треугольники непересекающимися диагоналями. Выведите отсюда, что сумма углов в произвольном n-угольнике равна (n - 2).

1.56. Клетки шахматной доски 100 100 раскрашены в 4 цвета так, что в любом квадрате 2 2 все клетки разного цвета. Докажите, что угловые клетки раскрашены в разные цвета.

1.57. Имеется k ящиков. В некоторых из них лежат еще k ящиков.

В некоторых из последних лежат еще ящики (снова k штук) и т. д.

Сколько всего ящиков, если заполненных m 1.58. Теорема Эйлера. Докажите, что для любого выпуклого многогранника имеет место соотношение В - Р + Г = 2, где В — число его вершин, Р — число ребер, Г — число граней.

12 1. Метод математической индукции 1.59*. Задача Сильвестра. На плоскости взяты несколько точек так, что на каждой прямой, соединяющей любые две из них, лежит по крайней мере еще одна точка. Докажите, что все точки лежат на одной прямой.

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 27 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.