alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
 Скачать 2 Mb.
|
|
C k n ∆ k f(x)∆ n−k+1 g(x + k) + + n+1 X k=1 C k−1 n ∆ k f(x)∆ n−k+1 g(x + k) = = n+1 X k=0 (C k n + C k−1 n )∆ n f(x)∆ n−k+1 g(x + k) = = n+1 X k=0 C k n+1 ∆ k f(x)∆ n+1−k g(x + k) 11.19 . а) 1 − 1 n + б + 2)(n − 1) 4n(n + в 2 1 2 − 1 (n + 1)(n + где ж) (n + 1)! − 1. 11.21 . б) Для двух многочленов степени n f(x) и g(x) = d 0 C 0 x +d 1 C 1 x + + . . . + d n C n справедливы равенства ∆ k f(0) = ∆ k g(0) (0 6 k 6 Поэтому они совпадают в точках x = 0, 1, . . . , n, то есть равны. Поскольку многочлен f(x) принимает целые значения в точках x = 0 , 1, . . . , n, то коэффициенты d k , найденные по формулам d k = = ∆ k см. задачу, оказываются целыми. Если n = 4k + 1 или n = 4k + 2, то независимо от расстановки знаков будет получаться нечетное число. Поэтому задача решения иметь не будет. Исследуем прогрессии n = 4k+3 и n = 4k. Покажем, что для чисел из первой прогрессии задача имеет решение начиная с n = а из второй — начиная с n = 8. Очевидно, что для n = 3 и n = 4 решения не существует. Из равенства n 2 − (n + 1) 2 − (n + 2) 2 + (n + 3) 2 = 4 следует, что из восьми последовательных чисел, подобрав знаки + и −, всегда можно получить 0. Поэтому, если задача имеет решение для некоторого n , то она будет иметь решение и для всех чисел n + 8k (k > 0). Осталось показать существование решения для n = 7, 11 и 12. Поиск облегчается, если сначала выяснить, для каких комбинаций знаков можно получить 0 по модулю некоторого натурального m, например, для m = 8. Нужные представления устроены следующим образом + 4 − 9 + 16 − 25 − 36 + 49 = 0; 1 − 4 + 9 + 16 + 25 − 36 − 49 − 64 + 81 − 100 + 121 = 0; 1 − 4 + 9 + 16 + 25 − 36 + 49 − 64 + 81 − 100 − 121 + 144 = 0. Ответы, указания, решения 11.28 , 11.29 Гармоничность данных функций проверяется по определению. Рассмотрим функции f(x, y) = f(x + 1, y) − f(x, и f(x, y) = f(x, y + 1) − f(x, которые также будут ограниченными и гармоническими. Пусть функция, неравна нулю тождественно. Допустим, что M = = sup (x,y) ∈Z 2 f(x, y) . Тогда на плоскости можно найти квадрат сколь угодно большого размера (n × n), что ∆ x f(x, y) > для всех точек этой области V. Отсюда следует, что функция f(x, y) возрастет при движении внутри K параллельно оси Ox по крайней мерена Но это противоречит ограниченности f(x, y). 11.31 . Проведите доказательство по индукции. Согласно задаче, последовательности n }=c i x для любых c 1 , являются решениями уравнения ( 11.2 ), поэтому их сумма будет удовлетворять тому же уравнению. С другой стороны, числа c 1 , можно подобрать так, чтобы a 0 = c 1 + c 2 , a 1 = c 1 x 1 + После этого получается, что две последовательности n } и {c 1 x n 1 +c 2 x удовлетворяют одному и тому же уравнению и имеют одинаковые начальные условия. Согласно задаче, они совпадают. а) a n = 3 n − б) a n = в) a n = 1 2 1 + 1 √ 5 1 + √ 5 2 n + 1 2 1 − 1 √ 5 1 − √ 5 2 n = г) a n = n + да б) a 2 n − 2b 2 n = (a n − b n √ 2)(a n + b n √ 2) = (1 + √ 2) n (1 − √ 2) n = в) Из равенства (a n + b n √ 2)(1 + √ 2) = (a n+1 + b находим, что числа a и b удовлетворяют рекуррентным соотношениям a n+1 = a n + +2b n , b n+1 = a n +b n . Отсюда a n+2 −2a n+1 −a n = 0 , b n+2 −2b n+1 −b n = 0 (n > г) a n = 1 2 ((1 + √ 2) n + (1 − √ 2) n ) , b n = 1 2 √ 2 ((1 + √ 2) n − (1 − √ 2) n ) 11.38 . Перейдите к сопряженным числам. В явном виде многочлены Фибоначчи и Люка помещены в приложение В , V . Многочлены, стоящие в равенствах а, б) и д) удовлетворяют одному рекуррентному соотношению. Поэтому достаточно проверить лишь выполнение начальных условий. (См. задачу 11.31 .) Для доказательства равенств в) и г, найдите рекуррентные соотноше- Ответы, указания, решения 237 ния, которым удовлетворяют многочлены, стоящие в левых и правых частях и проверьте справедливость начальных условий. Например, многочлены Фибоначчи c четными номерами удовлетворяют равенству) = (x 2 + 2)F 2n+2 (x) − F 2n (x). 11.43 . F n (x) = 1 √ x 2 + 4 h x + √ x 2 + 4 2 n − x − √ x 2 + 4 2 n i ; L n (x) = x + √ x 2 + 4 2 n + x − √ x 2 + 4 2 n 11.45 . F n+1 (x) = P k>0 C k n−k x n−2k , L n (x) = P k>0 (C k n−k + C k−1 n−k−1 )x n−2k 11.46 . Пусть a n , b n , c n , d n , e n , f обозначают число способов добраться из вершины A за n прыжков до вершин A, B, C, D, E, соответственно. В силу симметрии задачи, b n = f n , c n = e n . Легко видеть, что выполняются равенства n+1 = a n + c n , d n+1 = 2c n , a n+1 = 2b n , c n+1 = b n + d Отсюда находим, что все перечисленные последовательности удовлетворяют рекуррентному уравнению x n+4 − 5x n+2 + 4x n = 0 (n > 0). Изначальных условий a 0 = 1 , a 2 = 2 , находим a 2n = (2 + 4 n )/3 11.47 . а) Из рекуррентного уравнения c n+4 − 5c n+2 + 4c n = 0 (n > см. решение задачи) и начальных условий c 0 = 0 , c 2 = 1 , находим c 2n = (4 n − б) При условии, что лягушке нельзя прыгать в D, рекуррентное уравнение запишется в виде c n+2 = 3c n (n > 1). Отсюда c 2n = 3 n−1 (n > 1). Аналогично a 2n = 2 · в) Вероятность того, что лягушка будет еще прыгать через n секунд равна отношению числа всех путей, не проходящих через D, к общему числу маршрутов. Для четных n имеем+ c 2k + e 2k 2 2k = 3 k−1 4 k−1 (k > Для нечетных n: P 2k+1 = b 2k+1 + f 2k+1 2 2k+1 = 2a 2k + c 2k + e 2k 2 2k+1 = 3 k 4 k (k > Лягушка может попасть в вершину D только на нечетном шаге. Вероятность такого события для шага с номером n = 2k + 1 равна c 2k + e 2k 2 2k+1 = 2 · 3 k−1 2 2k+1 Ответы, указания, решения Поэтому средняя продолжительность жизни задается рядом = ∞ X k=1 (2k + 1) 2 · 3 k−1 Указанная сумма может быть вычислена при помощи производящей функции f(t) = 1 3 ∞ X k=1 3 k 2 2k t 2k+1 = t 3 4 − Среднее число шагов совпадает со значением производной функции в точке t = 1: N = f 0 (t) | t=1 = Ответ 4 секунды. (3 n − (−2) n )/5. 11.50 . Сложите данные числа с сопряженными к ним. Все решения уравнения x 2 − 17n 2 = в натуральных числах могут быть получены по формуле (x 1 + n 1 √ 17) k = x k + n k √ 17 (k > 1). 11.53 . x n = 1/2 sin α[(1 + sin 2α) n − (1 − sin 2α) n ], y n = 1/2 cos α[(1 + sin 2α) n + (1 − sin 2α) n ] 11.54 . Пусть a 0 — начальное число орехов, a k — количество орехов, оставшихся в куче после того, как свою долю взял й моряк. Тогда a k+1 = 4/5(a k − 1) (k = 0, . . . , Отсюда следует, что последовательность k } удовлетворяет линейному рекуррентному соотношению второго порядка k+1 − 9a k + 4a k−1 = 0 (k = 1, . . . , Из результата задачи 11.33 следует, что a k = c 1 + c 2 (4/5) k (k = 0, . . . , Подставляя это представление в первое рекуррентное соотношение, находим. Чтобы a было целым числом для каждого k от 0 до, константа должна иметь вид c 2 = 5 5 n . Поскольку при n = оставшееся число орехов a 5 = 4 5 − кратно 5, то наименьшее возможно число орехов в куче равно 5 5 − 4 . Ответа б) a n = 1 − i 2 (1+i) n + 1 + в) a 3n = 1 , a 3n+1 = 2 , a 3n+2 = г) a n = i((3 − 4i) n − (3 + 4i) n ) 11.58 . Воспользуйтесь равенствами ∆ 3 n 2 = и ∆ 4 n 3 = 0 Ответы, указания, решения 11.59 . Воспользуемся методом задачи. Выбирая всевозможные комбинации знаков при числах √ 2 и √ 3 , получим равенства (1 + √ 2 + √ 3) n = p n + q n √ 2 + r n √ 3 + s n √ 6, λ n 2 = (1 − √ 2 + √ 3) n = p n − q n √ 2 + r n √ 3 − s n √ 6, λ n 3 = (1 + √ 2 − √ 3) n = p n + q n √ 2 − r n √ 3 − s n √ 6, λ n 4 = (1 − √ 2 − √ 3) n = p n − q n √ 2 − r n √ 3 + s Складывая эти равенства с коэффициентами (1, 1, 1, 1), (1, −1, 1, −1), (1, 1, −1, −1) , (1, −1, −1, 1), находим p n = 1 4 (λ n 1 + λ n 2 + λ n 3 + λ n 4 ), q n = 1 4 √ 2 (λ n 1 − λ n 2 + λ n 3 − λ n 4 ), r n = 1 4 √ 3 (λ n 1 + λ n 2 − λ n 3 − λ n 4 ), s n = 1 4 √ 6 (λ n 1 − λ n 2 − λ n 3 + Отсюда lim n →∞ p n q n = √ 2 , lim n →∞ p n r n = √ 3 , lim n →∞ p n s n = √ 6 11.65 . Пусть f(x) = (1 + x) n = n P k=0 C k n x k . Тогда f 0 (x) = n(1 + x) n−1 = = n P k=0 kC k n x k−1 . Подставляя в эту формулу x = 1, находим сумму из па Аналогично находится сумма из п. б n = (xf 0 (x)) 0 | x=1 = n(n + Ответа б) n(n + 1) · 2 n−2 11.67 . Из равенства C k n+k−1 1 (1 − x) n+k находим a n = C k n+k−1 11.68 . Данное равенство равносильно утверждению, что всякое положительное число может быть записано в десятичной системе счисления ипритом только одним способом Ответы, указания, решения. Как ив предыдущей задаче, примените формулу из задачи. Здесь первое соотношение — замаскированный случай биномиальной теоремы, а второе получается из первого умножением на x m : ∞ X n=0 C m m+n x n = 1 (1 − x) m+1 , ∞ X n=0 C m n x n = x m (1 − x) m+1 11.72 . Из задачи 11.71 следует, что число счастливых билетов равно коэффициенту при у функции − x 10 1 − x 6 . Для нахождения N разложим функции (1 − и (1 − по степеням x: (1 − x 10 ) 6 = 6 X k=0 (−x) 10k C k 6 ; (1 − x) −6 = ∞ X k=0 x Отсюда = C 0 6 · C 27 32 − C 1 6 · C 17 22 + C 2 6 · C 7 12 = 55252. 11.73 . Первое равенство непосредственно следует из определения производной формального степенного ряда. Для доказательства второго равенства сравним коэффициенты при z в рядах Exp((α + β)z) и) · Exp(βz). В первом случае, это + β) n n! , во втором — n X k=0 α k k! · β n−k (n − k)! = 1 n! n X k=0 C k Равенство этих коэффициентов следует из формулы бинома Ньютона (задача 2.53 ). 11.74 . Заметим, что a 3 + b 3 + c 3 − 3abc = (a + b + c)(a + ωb + ω 2 c)(a + ω 2 b + смотрите задачу. Отсюда + b + c = (1 + x) n , a + ωb + ω 2 c = (1 + ωx) n , a + ω 2 b + ωc = (1 + Поэтому a 3 + b 3 + c 3 − 3abc = [(1 + x)(1 + ωx)(1 + ω 2 x)] n = (1 + x 3 ) n Ответы, указания, решения 11.76 . Подставьте в производящую функцию последовательности чисел Фибоначчи z = 1/10. Данная сумма оказывается равна 10/89. 11.77 . L(z) = 2 − z 1 − z − z 2 11.78 . а) б) 6. 11.79 . F(x, z) = z 1 − xz − z 2 , L(x, z) = 2 − xz 1 − xz − z 2 11.80 . F T (x, z) = 1 − xt 1 − 2xt + t 2 , F U (x, z) = 1 1 − 2xt + t 2 11.81 . а) Обозначим искомую сумму через f(x). Применяя формулу для суммы геометрической прогрессии, находим, чтоб) Как ив задаче 11.65 вторая сумма равна f 0 (1) = 2 n (n − 2) + в) Снова, как ив задаче 11.65 б), сумма равна следующей величине f 0 (1) + f 00 (1) = 2 n (n 2 − 5n + 8) − г) По формулу из задачи 7.58 а), g(x) = n−1 X k=1 = sin((n − 1)/2)x · Искомая сумма равна −g 0 (1) : −g 0 (x) | x=1 = n sin(n − 1)x − (n − 1) sin nx 2(1 − cos x) 11.83 . Проследите за изменением диаграммы Юнга. Задачу можно решить используя комбинаторные соображения из задачи. Если же использовать метод производящих функций, то решение задачи сводится к проверке равенства 1 − x − x 2 − x 3 − . . . = 1 1 − x/(1 − x) = 1 + x + 2x 2 + . . . + 2 n−1 x n + . . . 11.87 . a n = q ν(n) , где ν(n) — число единиц в двоичном представлении числа n. 11.88 . Интересующий нас ряд может быть получен из произведения − ax)(1 − bx 2 )(1 − cx 4 )(1 − dx 8 ) . . . если положить x = 1. При определении знака можно положить a = b = = c = d = . . . = 1 . Тогда искомый знак будет согласно задаче 11.87 равен (−1) ν(n) Ответы, указания, решения. a n = C n 2n 11.90 . x = y/(1 − y), y = x/(1 + x). Таким образом = x − x 2 + x 3 − x 4 + . . . + (−1) n+1 x n + . . . 11.91 . y = x − x 2 /2 + x 3 /3 − x 4 /4 + . . . + (−1) n+1 x n /n + . . . 11.92 . Воспользуйтесь равенством из задачи 2.116 и тем, что коэффициент при z у функции совпадает с правой частью этого равенства. Решая квадратное уравнение C(z) = zC 2 (z) + 1 , находим) = 1 − √ 1 − знак минус выбирается из условия C(0) = 1). Отсюда) = − 1 2 ∞ X n=1 C n 1/2 (−4) n z n−1 , C n = 1 2 (−4) n+1 C n+1 1/2 = (2n)! n!(n + 1)! 11.94 . Многочлены Гаусса, как и биномиальные коэффициенты, удобно располагать в виде треугольника: g 0,0 (x) g 1,0 (x) g 1,1 (x) g 2,0 (x) g 2,1 (x) g 2,2 (x) g 3,0 (x) g 3,1 (x) g 3,2 (x) g 3,3 (x) В явном виде многочлены Гаусса помещены в приложение В , V 11.95 . Свойства б) ив) непосредственно вытекают из а). Свойство г) доказывается индукцией по k при помощи свойства в). Свойство д) доказывается индукцией по l при помощи свойства г. Поделите числитель и знаменатель функции из определения полиномов g на (1 − x) k . Свойства многочленов g при подстановке превращаются в равенства из задачи 11.97 . S l (x) = при нечетных l и) = (1 − x)(1 − x 3 ) . . . (1 − x l−1 ) = h l (x) h при четных l. Для доказательства применим индукцию. Очевидно, что) = и S 1 (x) = 0 . Задача будет решена, если доказать соотношение) = (1 − x Пользуясь свойством виз задачи, находим) = (1−x l−1 )g 0,l−1 (x)−(1−x l−2 )g 1,l−2 (x)+. . .+(−1) l−1 (1−x 0 )g l−1,0 (x). Ответы, указания, решения 243 Применяя равенство (1 − x l )g k,l (x) = (1 − x k+l )g к каждому слагаемому в полученной сумме, приходим к нужному равенству) = (1 − x l−1 )(g 0,l−2 (x) − g 1,l−3 (x) + . . . ) = (1 − x l−1 )S l−2 (x). 11.98 . в) Рассмотрите симметричную диаграмму Юнга. г) Разбиению n = a 1 + a 2 + . . . + a j , j 6 k, a i 6 l числа n сопоставьте разбиение kl−n = (l−a 1 )+(l−a 2 )+. . .+(l−a j )+l+. . .+l числа kl−n, где слагаемое l−a отбрасывается, если оно равно нулю, а число слагаемых, равных l, равно k − j. Как связаны диаграммы Юнга, соответствующие двум таким разбиениям. Воспользуйтесь конструкцией из задачи 2.59 Глава 12 12.3 . 16/64, 19/95, 26/65, 49/98. 12.5 . Приведите равенство к виду sin a 2 sin b 2 sin a + b 2 = Ответ либо a = 2kπ, либо b = 2lπ, либо a + b = 2mπ. 12.7 . Воспользуйтесь тем, что число дней в летнем цикле делится на 7. 12.9 . Название племени должно быть словом в их алфавите. Среди сомножителей присутствует скобка (x − x). Ответ 0. 12.12 . Результат возведения единицы в степень не определен однозначно. Это происходит из-за того, что ln z — многозначная функция 12.14 . Отношение длины мили к длине километра равно 1,609 . . . что мало отличается от числа ϕ = 1,618 . . . Литература Учебники и монографии Арсак Ж. Программирование игр и головоломок. — М Наука, 1990. [2] Беккенбах Э, Беллман Р. Неравенства. — М Мир, 1965. [3] Беккенбах Э, Беллман Р. Введение в неравенства. — М Мир, 1965. [4] Брадис В. М, Минковский В. Л, Харчева А. К. Ошибки в математических рассуждениях. — М Учпедгиз, 1959. [5] Бухштаб А. А. Теория чисел. — М Учпедгиз, 1960. [6] Виленкин Н. Я. Комбинаторика. — М Наука, 1969. [7] Виленкин Н. Я, Ивашев-Мусатов ОС, Шварцбурд СИ. Алгебра и математический анализ Учебник для уч-ся для 10 классов. — М Просвещение Виленкин Н. Я, Ивашев-Мусатов ОС, Шварцбурд СИ. Алгебра и математический анализ Учебник для уч-ся для 11 классов. — М Просвещение Гарднер М. Математические головоломки и развлечения. — М Мир Гарднер М. Математические досуги. — М Мир, 1972. [11] Гарднер М. Математические новеллы — М Мир, 1974. [12] Гельфонд АО. Исчисление конечных разностей. — М Наука, 1967. [13] Грэхем Р. Л, Кнут Д. Э, Паташник О. Конкретная математика. Основание информатики. — М Мир, 1998. [14] Ежов И. И, Скороход А. В, Ядренко МИ. Элементы комбинаторики. М Наука, 1977. [15] Ейтс С. Репьюниты и десятичные периоды. — М Мир, 1992. [16] Курант Р, Роббинс Г. Что такое математика. — М МЦНМО, 2001. [17] Моденов ПС. Задачи по геометрии. — М Наука, 1979. [18] Нивен Р. Числа рациональные и иррациональные. — М Мир, 1966. [19] Пойа Д. Математическое открытие. — М Наука, 1970. |