Лекции по математике 269 Литература 274 Предисловие в этой книге собраны материалы по курсу математики в одном из классов московской Пятьдесят седьмой школы
 Скачать 1.26 Mb.
|
|
? сделать произвольную перестановку перемен- ных? 23. Доказать, что любая чётная перестановка представи- ма в виде произведения циклов длины 3. 24. ⋆ Доказать, что можно единственным способом разбить перестановки на чётные и нечётные так, чтобы произведение двух чётных или двух нечётных было чётно, а произведение чётной и нечётной (в любом порядке) было нечётно. 25. Доказать, что чётных перестановок столько же, сколь- ко нечётных. 26. ⋆ Как определить, будет ли заданная перестановка n элементов чётной или нечётной, сделав O(n) действий? (Под- счёт числа беспорядков требует порядка n 2 действий.) Задачи 1998 { 1999 года 185 27. ⋆ (а) Доказать, что в игре «15» нельзя вернуть на место переставленные 14 и 15 (не вынимая фишек из коробочки, а только двигая их). (б) Сколько классов неэквивалентных (не сводящихся друг к другу движением фишек) позиций есть в этой игре? 28. ⋆ На n катушках намотано n магнитных лент красным концом (ракордом) наружу, а белым | внутрь. Есть допол- нительная катушка и магнитофон, позволяющий перемотать ленту с одной катушки на другую (при этом внутри оказы- вается другой конец). Можно ли добиться, чтобы все ленты оказались белым концом наружу и пустой осталась та же дополнительная катушка? Можно ли добиться, чтобы при этом каждая лента осталась на своей катушке? 29. ⋆ Пусть σ 1 и σ 2 | две перестановки, фигурирующие в задаче 1 в качестве сомножителей. Найдётся ли такая пе- рестановка τ, что τσ 1 τ −1 = σ 2 ? 30. Пусть σ | произвольная перестановка. Доказать, что перестановки σ и τστ −1 раскладываются в произведение ци- клов одних и тех же длин. 31. ⋆ Дана перестановка σ=(123)(67)(89) множества {1, 2, 3, . . . , 8, 9 }. Сколько перестановок τ с ней коммутируют? 32. ⋆ Пусть σ и τ | перестановки из задачи 1. Найдётся ли такая перестановка ρ, что σρ = ρτ? 33. ⋆ Дана произвольная перестановка mn элементов, за- писанных в таблицу m×n. Доказать, что её можно предста- вить в виде композиции трёх перестановок, в которой первая и третья происходят по столбцам (новое положение любо- го элемента находится в том же столбце, что и старое), а вторая | по строкам. 34. ⋆ В словах, составленных из букв R и S, разрешается вычёркивать и дописывать (в любом месте) группы RRR и SS, а также заменять RRS на SR и наоборот. Сколько неэквива- лентных (не переводимых друг в друга такими заменами) слов существует? 35. ⋆ (Продолжение) Тот же вопрос, если слова составле- ны из букв a и b, разрешается вычёркивать и добавлять aa и bb, а также заменять aba на bab. 186 Задачи 1998 { 1999 года Группы Пусть G | множество с операцией * (каждой паре f, g элементов G поставлен в соответствие элемент f*g; порядок важен!). Множество G называется группой, если 1) (f * g) * h = f * (g * h) для любых f, g, h ∈ G; 2) существует единичный элемент e ∈ G, для которого e * g = g * e = g при любом g ∈ G; 3) для любого элемента g ∈ G существует обратный эле- мент g −1 ∈ G , для которого g −1 * g = g * g −1 = e Операцию * иногда называют «умножением», и вместо g * h пишут просто gh. Группы, в которых g * h = h * g для любых g, h ∈ G, называются коммутативными или абелевыми. (Иногда при этом групповую операцию называют «сложением».) 1. Выяснить, являются ли группами следующие множе- ства (с указанными операциями) и какие из этих групп ком- мутативны: (а) натуральные числа с операцией сложения; (б) целые числа с операцией сложения; (в) . . . с операцией умножения; (г) рациональные числа с операцией умножения; (д) остатки по модулю 5 с операцией сложения; (е) . . . с операцией умножения; (ж) ненулевые остатки по модулю 5 с операцией умножения; (з) то же для модуля 10; (и) векторы на плоскости с операцией сложения; (к) . . . только векторы с положительными координатами; (л) . . . с целыми коор- динатами; (м) комплексные числа с операцией умножения; (н) . . . только ненулевые комплексные числа; (о) по модулю равные 1; (п) по модулю равные 2; (р) движения плоскости (с операцией композиции); (с) . . . сохраняющие ориентацию; (т) . . . не сохраняющие ориентации; (у) повороты; (ф) пере- носы; (х) перестановки чисел 1, . . . , n с операцией умноже- ния; (ц) . . . только чётные перестановки; (ч) циклы длины 3; (ш) скорости в теории относительности (числа в интервале от −1 до 1, складываемые по формуле u*v = (u+v)/(1+uv); за единицу скорости выбрана скорость света); (щ) фигуры Задачи 1998 { 1999 года 187 (множества точек) на плоскости с операцией симметрической разности (A * B = A △ B состоит из точек, принадлежащих ровно одной из фигур A и B). 2. Доказать, что произведение n сомножителей не зави- сит от расстановки скобок. (Аккуратное рассуждение требу- ет индукции по n.) 3. Доказать (а) правило сокращения: если x * y = x * z, то y = z; (б) что в группе не может быть двух единичных элементов; (в) что у каждого элемента есть единственный обратный. Если групповая операция записывается как умножение, то обратный элемент обозначается a −1 4. Как найти (ab) −1 , зная a −1 и b −1 ? 5. Определить a n (где a | элемент группы, n | целое число) и проверить равенство a m+n = a m a n 6. Доказать, что для любого элемента a конечной группы найдётся целое положительное n, для которого a n равно e (единичному элементу). Наименьшее число n с таким свойством называется по- рядком элемента a; оно является периодом последователь- ности . . . , a −2 , a −1 , a 0 = e, a 1 = a, a 2 , a 3 , . . . и обозначает- ся пор(a). 7. ⋆ Доказать, что пор(fg) = пор(gf). 8. ⋆ В группе выбраны три элемента a, b, c. Сколько различных может быть среди чисел пор(abc), пор(acb), пор(bac), пор(bca), пор(cab), пор(cba)? 9. Пусть пор(g) = 57. Чему равно пор(g 6 ) ? Сформули- ровать и доказать общее утверждение. 10. ⋆ Доказать, что если порядок любого элемента группы (кроме единицы) равен 2, то группа коммутативна. 11. Найти все элементы конечного порядка (а) в группе ненулевых комплексных чисел (по умножению); (б) в группе движений плоскости. 12. Пусть a | фиксированный элемент конечной груп- пы G. Доказать, что операция «левого умножения» на a (пе- реводящая x в ax) является перестановкой элементов группы 188 Задачи 1998 { 1999 года и состоит из циклов одинаковой длины. Будет ли операция «правого умножения» на a состоять из циклов той же длины? 13. (Продолжение) Доказать, что порядок любого эле- мента конечной группы делит порядок (число элементов) группы. 14. Доказать малую теорему Ферма: если целое чи- сло a взаимно просто с целым положительным числом n, то a ϕ(n) ≡ 1( mod n). (Здесь φ(n) | количество чисел от 1 до n, взаимно простых с n.) 15. ⋆ Существует ли бесконечная группа, любой элемент которой имеет конечный порядок? Если любой элемент группы является (положительной или отрицательной) степенью элемента a, элемент a называ- ется образующей группы, а группа называется циклической. 16. Бывают ли нециклические группы из 1, 2, 3, 4, 5 и 6 элементов? 17. Будет ли группа ненулевых остатков от деления на 11 (с операцией умножения) циклической? Подмножество H группы G называют подгруппой, если оно само является группой относительно той же операции, то есть содержит единицу, произведение любых двух своих элементов и обратный к любому своему элементу. 18. Какие имеются подгруппы в группе остатков по мо- дулю 10 (с операцией сложения)? 19. . . . в группе перестановок трёх элементов? 20. Верно ли, что пересечение подгрупп | подгруппа? А объединение? 21. Доказать, что любая подгруппа группы Z целых чи- сел (по сложению) имеет вид nZ, то есть состоит из всех кратных некоторого числа n. 22. ⋆ Пусть X ⊂ R | подгруппа аддитивной группы веще- ственных чисел. Доказать, что либо X состоит из всех крат- ных некоторого числа x, либо X всюду плотна в R (пересе- кается с любым интервалом). Какой из двух случаев имеет место для множества чисел вида m + n √ 2 (где m, n ∈ Z)? 23. Множество элементов gh, где g | фиксированный элемент G, а h пробегает все элементы H, называется левым Задачи 1998 { 1999 года 189 смежным классом G по H и обозначается gH. Доказать, что (а) все смежные классы содержат одно и то же количество элементов; (б) любые два смежных класса либо не пересе- каются, либо совпадают. 24. (Теорема Лагранжа) Пусть G | конечная группа, H | ее подгруппа. Доказать, что порядок H делит порядок G . (Указание: G разбивается на смежные классы.) Как выве- сти отсюда, что порядок группы делится на порядок любого её элемента? 25. ⋆ Описать все конечные подгруппы группы движений плоскости. 26. ⋆ Сколько элементов циклической группы порядка n имеют порядок k? 27. ⋆ Пусть n | целое положительное число. Доказать, что сумма чисел ϕ(d) для всех делителей d числа n равна n . (Например, при n = 6 имеем ϕ(1)+ϕ(2)+ϕ(3) +ϕ(6) = = 1 + 1 + 2 + 2 = 6 .) 28. ⋆ Доказать, что любая группа простого порядка явля- ется циклической. 29. ⋆ Подмножество H конечной группы G замкнуто от- носительно умножения (произведение любых двух элементов из H лежит в H). Доказать, что H | подгруппа. 30. ⋆ В конечной группе квадрат любого элемента равен единице. Каков может быть порядок этой группы? Векторы 1. Даны два вектора a = − → OA и b = − → OB . Выразить через них вектор − → OC , если точка C делит отрезок AB в отноше- нии 5 : 7. 2. На плоскости фиксированы три точки O, A, B. Где на- ходятся концы векторов − → OX = λ − → OA + µ − → OB , (а) если λ+µ = = 1 ? (б) . . . и λ, µ > 0? 3. На плоскости заданы четыре точки O, A, B, C. Ба- рицентрическими координатами точки X относительно тре- угольника ABC называются числа (λ, µ, ν), для которых − → OX = λ − → OA + µ − → OB + ν − → OC и λ + µ + ν = 1. (а) Пока- зать, что если точки A, B и C не лежат на одной прямой, 190 Задачи 1998 { 1999 года то барицентрические координаты любой точки X определены однозначно и не зависят от выбора точки O. (б) Указать гео- метрическую интерпретацию барицентрических координат в терминах площадей. (в) Точка D имеет барицентрические координаты (1, 2, −2) относительно треугольника ABC. Ка- ковы барицентрические координаты точки C относительно треугольника ABD? 4. ⋆ Указать физическую интерпретацию барицентричес- ких координат (барицентр | центр тяжести). 5. В пространстве фиксированы четыре точки O, A, B, C. Где находятся концы векторов − → OX = λ − → OA + µ − → OB + ν − → OC , если λ + µ + ν = 1? 6. Где может находиться точка X, если − → OX = − → OA + − → OB , точка A находится внутри квадрата, а точка B | внутри треугольника (см. рис. 25)? r @ @ O Рис. 25 7. ⋆ Даны три вектора a, b, c на плоскости. Доказать, что найдутся такие целые числа k, l, m, не равные одновремен- но 0, что вектор ka + lb + mc имеет длину меньше 0,001. 8. ⋆ На плоскости даны 100 векторов, по длине не превос- ходящие 1. Доказать, что сложить некоторые из векторов со знаком «+», а другие со знаком «−», чтобы сумма по длине не превосходила 1/1000. (Сумма должна содержать хотя бы один вектор; вектор не может входить и со знаком «+», и со знаком «−», но может вовсе не входить в сумму.) 9. ⋆ На плоскости даны четыре точки A, B, C, D. Для ка- ких точек O найдутся такие неотрицательные числа λ, µ, ν, κ, что λ − → OA + µ − → OB + ν − → OC + κ − → OD = 0 ? 10. Для каждой из сторон многоугольника построили перпендикулярный ей вектор, направленный вовне много- угольника и по длине равный этой стороне. Доказать, что сумма этих векторов равна 0. Задачи 1998 { 1999 года 191 11. ⋆ Для каждой из граней многогранника построили пер- пендикулярный ей вектор, направленный вовне многогран- ника и по длине равный площади этой грани. Доказать, что сумма этих векторов равна 0. (Указание: задача имеет физи- ческий смысл.) До сих пор мы говорили о векторах на плоскости и в пространстве. Дадим теперь общее определение. Векторное пространство | это множество V, элементы которого назы- вают векторами. В нём выделен нулевой вектор 0 и определе- ны операции сложения (+) и умножения на действительное число. Эти операции должны обладать такими свойствами (x, y, z ∈ V, λ, µ | числа): (i) (x + y) + z = x + (y + z); (ii) x + y = y + x; (iii) x + 0 = x; (iv) для любого вектора x существует такой вектор y, что x + y = 0 (противоположный вектор); (v) 1 · x = 1; (vi) (λ + µ)x = λx + µx; (vii) λ(x + y) = λx + λy; (viii) λ(µx) = (λµ)x. 12. (Следствия из аксиом) Доказать, что (а) λ · 0 = 0 (здесь 0 обозначает нулевой вектор); (б) если λ ̸= 0 и x ̸= 0, то λx ̸= 0; (в) если сумма любых 5 из данных 7 векторов равна 0, то все векторы равны 0. 13. Многочлены образуют векторное пространство (с есте- ственными операциями сложения и умножения на число). Что будет, если ограничить рассмотрение (а) многочленами степени не более 10? (б) многочленами степени ровно 10? (в) многочленами, имеющими корень 1? (г) многочленами, имеющими действительный корень? 14. Последовательности образуют векторное пространст- во. Что будет, если ограничить рассмотрение (а) сходящи- мися последовательностями? (б) сходящимися к 1 последо- вательностями? (в) сходящимися к 0 последовательностями? (г) ограниченными последовательностями? (д) возрастающи- 192 Задачи 1998 { 1999 года ми последовательностями? (е) последовательностями, у ко- торых ряд из квадратов сходится? Линейной комбинацией векторов v 1 , . . . , v n с коэффици- ентами λ 1 , . . . , λ n ∈ R называется вектор v = λ 1 v 1 + . . . + + λ n v n . Говорят, что вектор v линейно выражается через v 1 , . . . , v n , если он представим в виде их линейной комби- нации. Множество всех таких векторов называется линейной оболочкой векторов v 1 , . . . , v n 15. Закончить фразу: система линейных уравнений (от- носительно x, y, z) a 1 x + b 1 y + c 1 z = d 1 , a 2 x + b 2 y + c 2 z = d 2 , a 3 x + b 3 y + c 3 z = d 3 имеет решение тогда и только тогда, когда вектор . . . ли- нейно выражается через векторы . . . 16. Как выглядит линейная оболочка двух векторов в трёхмерном пространстве? 17. Доказать, что линейная оболочка векторов v, w со- впадает с линейной оболочкой векторов v − w, v + w. 18. Проверить следующие полезные (хотя и простые) свой- ства линейной оболочки: (а) если в системе x 1 , . . . , x n за- менить какой-либо вектор x i на вектор x i + λx j (для ка- ких-то j и λ), то линейная оболочка системы не изменится; (б) если линейная оболочка векторов x 1 , . . . , x n содержит вектор y, то она совпадает с линейной оболочкой векто- ров x 1 , . . . , x n , y 19. Найти линейную оболочку векторов 1, (x−1), (x−1) 2 , (x − 1) 3 в пространстве многочленов. 20. (Продолжение) Тот же вопрос для 1, (x−1), (x−1)(x− − 2) , (x − 1)(x − 2)(x − 3). 21. Функции на прямой образуют векторное простран- ство. (а) Лежит ли функция sin x в линейной оболочке функ- ций 1, cos x, cos 2x, cos 3x, . . . ? (б) Тот же вопрос про функ- цию sin 2 x Задачи 1998 { 1999 года 193 22. ⋆ (Продолжение) Тот же вопрос про функцию sin k x при произвольном k. Набор векторов называется линейно зависимым, если ес- ли некоторая нетривиальная их линейная комбинация (не все коэффициенты нулевые) равна 0. В противном случае набор называется линейно независимым. 23. (а) В каком случае три вектора на плоскости линейно зависимы? (б) В каком случае три вектора в пространстве линейно зависимы? 24. (а) Доказать, что набор векторов линейно зависим в том и только том случае, когда один из векторов линейно выражается через остальные. (б) Можно ли в предыдущем утверждении заменить слова «один из векторов» на «первый вектор»? 25. Доказать, что векторы x, y линейно зависимы тогда и только тогда, когда векторы x + 2y и 2x + y линейно за- висимы. 26. Закончить фразу: система линейных уравнений (от- носительно x, y, z) a 1 x + b 1 y + c 1 z = 0 a 2 x + b 2 y + c 2 z = 0 a 3 x + b 3 y + c 3 z = 0 имеет ненулевое решение тогда и только тогда, когда векто- ры . . . 27. (а) Доказать, что векторы задачи 19 линейно незави- симы. (б) Доказать, что векторы задачи 20 линейно незави- симы. Координатное векторное пространство R n состоит из n-ок чисел с покоординатным сложением и умножением на число. 28. При каких a строки матрицы ⎛ ⎝ 1 2 3 4 5 6 7 2 a ⎞ ⎠ линейно зависимы? 194 Задачи 1998 { 1999 года 29. (Продолжение) При каких a столбцы этой матрицы линейно зависимы? 30. ⋆ Имеется три литровых банки, заполненных на три четверти тремя разными красками (каждая | своей). Разре- шается переливать краску из одной банки в другую, не пере- ливая через край и тщательно перемешивая смесь. Так мож- но повторять многократно. Наша цель | получить смесь, в которую все три краски входят поровну. (а) Можно ли по- лучить такую смесь во всех банках после конечного числа операций? (б) Можно ли получить такую смесь в одной из банок после конечного числа операций? 31. ⋆ Дано n различных чисел c 1 , . . . , c n . Доказать, что функции exp(c 1 x), . . . , exp(c n x) линейно независимы. 32. ⋆ Доказать, что функции cos x, cos 2x, . . . , cos nx ли- нейно независимы. 33. Доказать, что строки матрицы ⎛ ⎝ 1 1 1 a b c a 2 b 2 c 2 ⎞ ⎠ линейно независимы, если все три числа a, b, c разные. 34. ⋆ (Продолжение) Тот же вопрос для столбцов этой матрицы. 35. ⋆ |