Лекции по математике 269 Литература 274 Предисловие в этой книге собраны материалы по курсу математики в одном из классов московской Пятьдесят седьмой школы
 Скачать 1.26 Mb.
|
|
(произошло хотя бы одно из событий A и B)? 10. ⋆ Имеются n событий, причём вероятность каждого из них равна p. Показать, что вероятность того, что произойдут не менее k из этих событий одновременно, не больше np/k. Условной вероятностью события A при условии собы- тия B называют отношение Pr[A|B] = Pr[A и B]/ Pr[B]. (Пред- полагается, что Pr[B] > 0.) 11. (а) Найти условную вероятность выпадения двух ор- лов в двух бросаниях, если известно, что хотя бы один орёл выпал; (б) . . . что на первом шаге выпал орёл; (в) . . . что на втором шаге выпал орёл. Событие A называют независимым от события B, если Pr[A|B] = Pr[A]. 12. Доказать, что отношение независимости симметрично: если A независимо от B, то B независимо от A. 13. Будут ли события «выпало чётное число» и «выпало число, делящееся на 3» независимы при бросании кости? 14. (а) Будут ли (для трёх бросаний монеты) события «при первом бросании монеты выпал орёл» и «выпало ров- но два орла» независимы? (б) Тот же вопрос для событий «при первом бросании выпал орёл» и «число орлов нечётно». (в) Тот же вопрос для событий «при первом бросании выпал орёл» и «при втором и третьем бросании был хотя бы один орёл». Задачи 1999 { 2000 года 261 15. Событие B и событие C независимы от события A. Можно ли утверждать, что событие «B и C» независимо от события A? 16. ⋆ Монету бросают n раз. Событие A определяется ре- зультатами первых k бросаний, событие B | результатами последних n − k бросаний. Показать, что события A и B независимы. 17. ⋆ Дать определение независимости трёх событий A, B и C (из которого следовала бы попарная независимость, а также, скажем, независимость события A и события «B и C »). 18. Найти условную вероятность Pr[A|B], если известна условная вероятность Pr[B|A], а также безусловные вероят- ности Pr[A] и Pr[B]. (Ответ к этой задаче называют формулой Байеса.) 19. Какое вероятностное пространство естественно рас- сматривать для бросаний несимметричной монеты с вероят- ностью выпадения орла p? (Указание: бросания независи- мы.) 20. ⋆ Имеется N мешков по N монет, в каждом мешке λ фальшивых. Мы проверяем наугад по одной монете из меш- ка. Каковы вероятности найти среди них 0, 1, 2, . . . фальши- вых (при N → ∞ и фиксированном λ)? 21. ⋆ В очередь за газетами ценой в полтинник становятся в случайном порядке n человек с полтинниками и n человек с рублями. Какова вероятность того, что всем хватит сдачи, если изначально ни у них, ни у продавца других денег нет? Блуждания На прямой дороге стоит пьяный, который делает случай- ным образом шаги вперёд и назад (с вероятностью 1/2). 1. Найти вероятность его попадания в данную точку до- роги (а) через один шаг; (б) через два шага; (в) через пять шагов. 2. Для какой точки вероятность оказаться там через n ша- гов будет наибольшей? Показать, что эта вероятность стре- мится к нулю при n → ∞. 262 Задачи 1999 { 2000 года 3. ⋆ Найти среднее значение квадрата смещения за n ша- гов (рассматриваются все 2 n вариантов его движения, для каждого варианта смещение возводится в квадрат и берётся среднее арифметическое). 4. ⋆ Показать, что вероятность отойти на расстояние бо- лее чем n/100, сделав n шагов в случайном направлении, стремится к нулю при n → ∞. Пусть теперь на дороге в k шагах впереди от пьяного имеется канава. Пусть p(n, k) | вероятность не упасть в канаву за n шагов. Например, p(0, 1) = 1 и p(1, 1) = 1/2 (шаг вперёд приводит к падению, шаг назад | нет). 5. (а) Найти p(n, k) при n = 1, 2, 3, 4 (и при всех k). (б) Как найти значения p(n, k) при данном n и при всех k, если известны значения p(n − 1, k) при всех k? 6. (а) Показать, что p(n, k) убывает с ростом n (для фиксированного k) и потому стремится к некоторому преде- лу p ∞ (k) . (б) Как связаны p ∞ (k − 1) , p ∞ (k) и p ∞ (k + 1) ? (в) Показать, что p ∞ (k) = 0 при всех k. Последнее утверждение часто выражают так: каково бы ни было начальное расстояние до канавы, почти наверняка пьяный рано или поздно свалится в неё. 7. Игрок приходит в игорный дом и играет в орлянку (ставит рубль, с вероятностью 1/2 проигрывает его, а с ве- роятностью 1/2 получает ещё рубль). Когда деньги конча- ются, он уходит, разорившись. Показать, что каков бы ни был начальный капитал игрока, вероятность не разориться после n партий стремится к нулю с ростом n. 8. ⋆ Пусть вероятность сделать шаг вперёд (к канаве) рав- на 1/3, а вероятность пойти назад равна 2/3. Какова веро- ятность избежать падения в канаву, находясь на расстоянии k шагов от неё? 9. ⋆ Показать, что с ростом n вероятность не вернуться ни разу в исходную точку, сделав n шагов (по дороге без канав), стремится к нулю. 10. ⋆ Пусть теперь на дороге есть две канавы: впереди в k шагах и позади в l шагах. Найти вероятность свалиться в ту и в другую канавы (пределы вероятности сделать это за Задачи 1999 { 2000 года 263 n шагов при n → ∞). 11. ⋆ Игрок приходит в игорный дом с капиталом в k ру- блей и играет, пока не проиграется или пока не выиграет l рублей. Какова вероятность того, что он уйдёт с выигры- шем? 12. ⋆ Пьяный блуждает по круговому шоссе длиной в n шагов. Отметим точку шоссе, в которую он придёт позже всего. (Это может быть любая точка шоссе, кроме исход- ной.) Какова вероятность того, что ей окажется точка шоссе, соседняя с исходной? 13. ⋆ (Продолжение) Показать, что все точки шоссе, кроме исходной, имеют равную вероятность оказаться последними. Рассмотрим теперь блуждание по двумерной сетке (точка находится в одном из узлов и с вероятностью 1/4 может сдвинуться влево, вправо, вверх и вниз. 14. ⋆ Предположим, что точка находится внутри области, ограниченной канавой (скажем, прямоугольной формы). По- казать, что вероятность не попасть в канаву после n шагов стремится к 0 при n → ∞. 15. ⋆ В кольце между двумя канавами находится точка. Рассмотрим вероятности свалиться в ту и другую канаву по- сле n шагов. (а) Показать, что эти вероятности имеют преде- лы при n → ∞ (обозначим их через p 1 (x) и p 2 (x) , где x | исходная точка) и что p 1 (x) + p 2 (x) = 1 при всех x внутри кольца. (б) Величины p 1 и p 2 можно найти эксперименталь- но: сделаем рёбрами сетки проводники единичного сопроти- вления, подадим во все точки внутренней канавы потенци- ал 1, а во все точки внешней | потенциал 0. Показать, что потенциал в точке x равен p 1 (x) . (в) Пусть A | точка вну- три канавы. Рассмотрим вероятность вернуться в точку A, не попав в канаву (начав блуждания из A). Показать, что эта вероятность равна 1 − 1 4R , где R | электрическое сопро- тивление между точкой A и точками канавы (мы считаем, что все точки канавы соединены проводником нулевого со- противления). 16. ⋆ (Продолжение) (а) Показать, что сопротивление меж- ду квадратной канавой размера 2N × 2N и её центром стре- 264 Задачи 1999 { 2000 года мится к бесконечности при N → ∞. (б) Показать, что это сопротивление заключено между c 1 log N и c 2 log N при не- которых c 1 и c 2 . (Указание: токи распределяются так, чтобы выделяемая энергия была минимальной.) 17. ⋆ Показать, что точка, блуждающая по плоскости, по- чти наверное вернётся в начальное положение. 18. ⋆ Показать, что для трёхмерного пространства анало- гичное утверждение неверно. Разное 1. Черепаха ползла N минут. При этом её наблюдали не- сколько человек, каждый по одной минуте | иногда не- сколько сразу, но так, что она ни в какой момент не оста- валась без наблюдения. За время наблюдения каждого че- ловека она проползла не более метра. Доказать, что общее расстояние, которая она проползла, не больше 2N метров. 2. Имеется последовательность из mn + 1 чисел. Дока- зать, что она имеет либо возрастающую подпоследователь- ность длины m + 1, либо убывающую длины n + 1. 3. Имеется несколько кружков с пересекающимися участ- никами. Мы хотим в каждом из них выбрать старосту так, чтобы ни один человек не был старостой сразу двух кружков. Доказать, что следующее условие необходимо и достаточно: объединение любых k кружков содержит не менее k человек. 4. Построить касательную, проходящую через заданную точку (а) к окружности (б) к параболе одной линейкой. 5. Доказать, что конечным числом внутренностей пара- бол нельзя покрыть плоскость. 6. Доказать, что если круг покрыт бумажными полоска- ми, то сумма ширин этих полосок не меньше диаметра круга. 7. Объединение N фигур имеет площадь N. Доказать, что для любого k < N можно выбрать из них k фигур, площадь объединения которых не меньше k. 8. Единичный квадрат разрезан на квадраты. Доказать, что стороны всех квадратов рациональны. 9. Прямоугольник можно разбить на квадраты. Доказать, что его стороны соизмеримы. Задачи 1999 { 2000 года 265 10. N школьников решали N задач. Каждый из них ре- шил k задач (k 6 N) и каждую задачу решило k школь- ников. Доказать, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были рассказаны. 11. Доказать, что любая перестановка элементов прямо- угольной матрицы есть композиция трёх перестановок: пер- вая и третья внутри строк, вторая внутри столбцов. 12. В бесконечной двумерной таблице все числа положи- тельны и каждое из них есть среднее арифметическое четы- рёх своих соседей. Доказать, что все числа равны. (Предо- стережение: числа не обязательно целые!) 13. Существует ли многочлен (а) от одной переменной (б) от двух переменных, который всюду положителен, но точная нижняя грань его значений равна нулю? 14. Доказать, что для комплексного многочлена степени меньше n значение в центре правильного n-угольника есть среднее арифметическое его значений в вершинах. 15. (Продолжение) Доказать, что для комплексного мно- гочлена значение в центре окружности равно его среднему по окружности. 16. Дан граф и две его вершины А и Б. Доказать, что следующие условия эквивалентны: (1) из А в Б ведут два пути, которые не имеют общего ребра; (2) нельзя удалить одно ребро так, чтобы А и Б лежали в разных компонентах связности. 17. (а) Доказать, что если многочлен от одной перемен- ной всюду положителен, то он представляется в виде суммы квадратов многочленов. (б) Верно ли это утверждение для многочленов от двух переменных? 18. Привести пример монотонно возрастающей функции на отрезке [0, 1], множеством точек разрыва которой являет- ся (а) множество всех рациональных точек отрезка; (б) про- извольное счетное множество {a 1 , a 2 , . . . } ⊂ [0, 1]. 19. Привести пример всюду дифференцируемой функции f(x) , имеющей при x = 0 локальный минимум, и такой, что 266 Задачи 1999 { 2000 года производная f ′ (x) не сохраняет знака ни в какой односто- ронней окрестности точки 0. 20. Функция F(x) имеет период 1 и равна |x| при −1/2 6 6 x 6 1/2. Определим функцию f n (x) равенством f n (x) = = F(x) + 1 4 F(4x) + 1 16 F(16x) + · · · + 1 4 n F(4 n x) . (а) Постро- ить графики функций f 0 , f 1 , f 2 , f 3 ; (б) Доказать, что предел f(x) = lim n →∞ f n (x) существует при всех x и является не- прерывной функцией; (в) Доказать, что f(x) не имеет произ- водной ни при каком x; (г) Доказать, что f(x) не монотонна ни на одном интервале действительной прямой. 21. Указать бесконечно дифференцируемую функцию f(x) , равную 0 при |x| > 2 и равную 1 при |x| 6 1. 22. На плоскости дано n прямых общего положения (ни- какие две прямых не параллельны и никакие три не пересека- ются в одной точке). Доказать, что среди частей, на которые эти прямые делят плоскость, не меньше n−2 треугольников. 23. После проведения шахматного турнира оказалось, что для каждого непустого множества его участников существу- ет участник, набравший нечетное число очков в играх с участ- никами, вошедшими в это множество. Доказать, что число участников турнира четно. 24. На листе клетчатой бумаги нарисован квадрат (сто- роны идут по линиям сетки). В крайних клетках квадра- та (на границе) расставлены числа. Доказать, что можно единственным образом заполнить числами оставшиеся клет- ки квадрата так, чтобы число в каждой клетке равнялось среднему арифметическому своих соседей. Контрольная работа 1. Даны три вектора a, b, c на плоскости. В каких случаях можно найти числа λ, µ, ν, не равные нулю одновременно, для которых λa + µb + νc = 0 и λ + µ + ν = 0? (Ответ сформулировать в геометрических терминах.) 2. Лежит ли функция sin x в линейной оболочке функ- ций cos 2x и sin 2x? 3. Рассмотрим пространство многочленов степени не боль- ше 7, делящихся на многочлен (x − 1)(x − 2). Какова его Задачи 1999 { 2000 года 267 размерность? Указать базис в этом пространстве. 4. Те же вопросы для многочленов степени не выше 7, делящихся на x 2 + x + 1 5. При каких λ векторы (λ, 1, 0), (0, λ, 1), (0, 0, λ − 1) линейно зависимы? 6. Доказать, что если любой вектор k-мерного простран- ства V линейно выражается через векторы x 1 , . . . , x n , то из этих векторов можно выбрать базис (отбросив часть). 7. Сколькими способами можно выбрать базис в преды- дущей задаче? (Указать максимальное и минимальное число вариантов, считая, что все векторы ненулевые.) 8. В магическом кубе 2 × 2 × 2 суммы по любых пря- мым, параллельным осям координат, а также по любой из главных диагоналей равны. Найти размерность пространства таких кубов. Контрольная работа 1. Оператор F: R 2 → R 2 имеет матрицу (︂0 1 1 1 )︂ . Указать все векторы, для которых Fx пропорционально x, и соответ- ствующие коэффициенты пропорциональности. 2. Система линейных уравнений с целыми коэффициен- тами и правыми частями имеет решение, в котором одна из координат иррациональна. Показать, что она имеет беско- нечно много решений. 3. Какую матрицу имеет оператор ϕ (действующий в дву- мерном пространстве) в базисе e 1 , e 1 + e 2 , если он имеет в базисе e 1 , e 2 матрицу (︂2 0 0 2 )︂ ? 4. Тот же вопрос для матрицы (︂1 0 0 2 )︂ 5. Тот же вопрос для матрицы (︂1 2 3 4 )︂ 6. Даны различные числа α 1 , . . . , α m ; в каждой из то- чек α i задано значение многочлена P и всех его производ- ных, меньших k i . Доказать, что по таким данным всегда можно восстановить многочлен степени меньше k 1 +. . .+k m , 268 Задачи 1999 { 2000 года причём единственным образом. 7. Найти числа p, q, для которых A 3 + pA 2 + qA + r = 0 , где A | матрица ⎛ ⎝ 1 1 0 0 1 0 0 0 2 ⎞ ⎠ 8. Доказать, что для всякого оператора ϕ найдётся мно- гочлен P, для которого P(ϕ)) = 0. (Подстановка оператора в многочлен имеет смысл, так как операторы можно возводить в степень и умножать на числа.) 9. Доказать, что если ϕ: U → U | линейный оператор, для которого ϕ n = 0 , то оператор E+ϕ (отображающий x в x + ϕ(x) ) обратим. (Указание: обратный оператор есть мно- гочлен от ϕ.) Популярные лекции по математике Большинство задач, решаемых школьниками, обсуждает- ся с ними на уроках, так что решения они не записывают. Чтобы научить школьников писать связные математические тексты, мы время от времени (не чаще раза в неделю) рас- сказывали им что-либо не очень сложное (рассказ длился не более одного урока) и достаточно замкнутое в себе, а за- тем просили принести письменное изложение рассказанного. В этом разделе мы приводим темы таких лекций (с коммен- тариями). 1997 { 1998 год 1. Бесконечность множества простых чисел. Основная те- орема арифметики для целых чисел. (Разные доказатель- ства). 2. Теорема Эйлера о соотношении В − Р + Г = 2 для вы- пуклого многогранника. (Доказательство с проектированием на плоскость и удалением рёбер). 3. Проективная геометрия и двойное отношение. (Парал- лельное и центральное проектирование. Двойное отношение, его сохранение при проективных преобразованиях. Примене- ние к «задаче о бабочке».) 4. Проективная геометрия, продолжение. (Проективные преобразования совпадают с дробно-линейными.) 5. Непланарные графы. (Полный пятивершинник и граф «три дома, три колодца» нельзя нарисовать на плоскости так, чтобы никакие два ребра не пересекались | доказательство с помощью формулы Эйлера.) 6. Теорема Дезарга. (Различные доказательства.) 7. Гармонический ряд, бесконечность множества простых. (Доказательство c помощью бесконечного произведения.) 8. Экстремальные задачи. ((а) Задача о минимальном пу- ти света у зеркала. Принцип Ферма. (б) Система стремится в положение с минимальной энергией: шар в ямке. (в) Груз на пружине (сумма энергии тяготения и энергии пружины, вы- вод формулы F = −kx из соображений энергии). (г) Физиче- 270 Популярные лекции по математике ское решение задачи о минимальном пути. (д) Преломление, закон Снеллиуса.) 9. Построение квадратных корней циркулем и линейкой. (Построение правильного пятиугольника. Теорема: коорди- наты всех построенных объектов выражаются через коорди- наты исходных с помощью операций сложения, умножения и взятия квадратного корня.) 10. Экстремальные задачи, продолжение. (Разные реше- ния задачи XA + XB + XC → min для треугольника ABC: (а) Три грузика | равновесие сил. (б) Задача при фикси- рованном AX: отражение света в окружности. Другое дока- зательство равенства всех углов. (в) Решение с поворотом на 120 ∘ . (г) Другое математическое решение. (д) Задача о мыльной плёнке.) 11. Дроби Фарея. (Возьмём дроби 0/1 и 1/1. Далее, меж- ду каждыми двумя дробями a/b и c/d будем записывать новую дробь a+c b+d . Тогда мы в конце концов получим все несократимые дроби отрезка [0, 1].) 12. Эллипс. (Определение эллипса как геометрического места точек, сумма расстояний от которых до двух данных постоянна. Три доказательства свойства касательной к эл- липсу (сравнение скоростей, принцип Ферма и отражение от прямой). Эллипс как сечение цилиндра (шары Данделена).) |