WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |   ...   | 65 |

б) О т в е т: 360. Ожерелье, в отличие от хоровода, можно не только вращать по кругу, но и перевернуть. В результате получаем 720/2 = 360 различных ожерелий.

168 Глава 14. Комбинаторика n 14.6. О т в е т:. Всего мы должны сделать m шагов вверх и n - m m шагов влево. Поэтому из n шагов нужно выбрать m шагов вверх.

n + m - 14.7. а) О т в е т: способами. Сопоставим разложению n = n = x1 +... + xm последовательность нулей и единиц, в которой сначала идёт x1 единиц, потом один нуль, потом x2 единиц, потом один нуль и т.д; в конце идёт xm единиц. Всего в этой последовательности n + m - 1 цифр, среди которых n единиц. Поэтому мы должны выбрать n предметов из n + m - занумерованных (т.е. различных) предметов.

n - б) О т в е т:. Каждому разложению n = x1 +... + xm, где n - m x1,..., xm натуральные числа, соответствует разложение n - m = y1 + +... + ym, где y1 = x1 - 1,..., ym = xm - 1.

14.8. Чтобы в произведении n множителей x1 +... + xk получить моном xl1 ·... · xlk, нужно сначала выделить l1 множителей из n и выбрать в них x1, 1 k затем нужно выделить l2 из оставшихся n - l1 множителей и выбрать в них x2, затем нужно выделить l3 из оставшихся n - l1 - l2 множителей и выбрать в них x3 и т.д. Поэтому коэффициент при мономе xl1 ·... · xlk равен 1 k n n - l1 n - l1 - l2 n - l1 -... - ln-·... · = l1 l2 l3 ln n! (n - l1)! (n - l1 -... - ln-1)! = · ·... ·.

l1!(n - l1)! l2!(n - l1 - l2)! ln!(n - l1 -... - ln)! Заметив, что n - l1 -... - ln = 0, получаем требуемое.

n n n 14.9. а) 2n = (1 + 1)n = + +... +.

0 1 n n n n n б) 0 = (1 - 1)n = - + - +....

0 1 2 14.10. Сравните коэффициенты при xk в обеих частях равенства (x + + 1)m+n = (x + 1)m(x + 1)n.

14.11. Примените тождество из задачи 14.10 при n = m = k и восполь n n зуйтесь тем, что =.

i n - i 2n 14.12. Коэффициент при xn-k в разложении (1 + x)2n равен = n - k n n 2n =. С другой стороны, (1 + x)2n = x2 + (1 + 2x) = x2i(1 + i n + k i - i n n +2x)n-i = x2i 2jxj. В последнем выражении коэффициент i j i j n - i n - i n n при xn-k равен 2n-k-2i = 2n-k-2i.

i i k n - k - 2i k i + k 14.13. Требуется доказать, что (n - 1)! n! (n + 1)! · · = (k - 1)!(n - k)! (k + 1)!(n - k - 1)! k!(n - k + 1)! (n - 1)! (n + 1)! n! = · ·.

k!(n - k - 1)! (k + 1)!(n - k)! (k - 1)!(n - k + 1)! Глава 14. Комбинаторика Это равенство очевидно.

n - r 14.14. Пусть Sn = (-1)r prqr. В действительности сум0 r n/r мирование можно вести по всем r, так как если > n/2, то n-r < r, а r потому n - r n + 1 - r n - r = 0. Поэтому Sn+1 - Sn = (-1)r - prqr = r r r n - r = (-1)r prqr = -pqSn-1. Ясно также, что S0 = S1 = 1. С другой r - p - q p2 - qстороны, = 1 и = p + q = 1. Поэтому при n = 0 и при n = p - q p - q pk+1 - qk+= 1 требуемое утверждение верно. Если равенство Sk = докаp - q pn+1 - qn+1 - pq(pn - qn) зано для всех k n, то Sn+1 = Sn - pqSn-1 = = p - q pn+1(1 - q) - qn+1(1 - p) pn+2 - qn+= =.

p - q p - q 14.15. О т в е т: P (n + 2) = 2n+2 - 2.

m (x - 1)(x - 2)... (x - m) Выражение = можно рассматривать как x - 1 m! x - 1 x - многочлен степени n от переменной x. Пусть f(x) = 2( + +...+ x - 1 x - 1 x - 1 x - + ). Ясно, что + +... + = (1 + 1)x-1 = 2x-n 0 1 n при x = 1, 2,..., n + 1. Поэтому P (x) = f(x), поскольку эти многочлены степени n совпадают при n + 1 различных значениях x. Следовательно, n + 1 n + 1 n + P (n + 2) = 2( + +... + ) = 0 1 n n + 1 n + 1 n + 1 n + 1 n + = 2( + +... + + - ) = 0 1 n n + 1 n + = 2(2n+1 - 1) = 2n+2 - 2.

n n 14.16. Продифференцируем тождество (1 + x)n = xm и доm=m множим полученное равенство на x. В результате получим nx(1 + x)n-1 = n n = mxm ; при x = 1 получаем первое из требуемых тождеств. Ещё m=m раз повторив дифференцирование по x и домножение на x, получим n n nx(nx + 1)(1 + x)n-2 = m2xm ;

m m=при x = 1 получаем второе из требуемых равенств.

n n 14.17. Запишем тождество (1+t)n = tm и проинтегрируем его:

m=m n x x n (1 + t)ndt = tm dt, m 0 m=170 Глава 14. Комбинаторика т.е.

n (1 + x)n+1 - 1 xm+1 n =.

n + 1 m + 1 m m=При x = 1 получаем первое требуемое тождество, а при x = -1 второе.

14.18. Применим индукцию по n. При n = 1 получаем обычную формулу для суммы бесконечной геометрической прогрессии. Чтобы перейти от n к n + 1, нужно доказать тождество n + k n + k - 1 + xk (1 - x) = 1 + xk.

n n - k=1 k= n + k n + k - Коэффициенты при xk в левой и правой частях равны n n n + k - и соответственно. Эти числа равны.

n - 14.19. Мы приведём доказательство лишь для первого числа (для второго числа рассуждения аналогичны). При n = 0 утверждение очевидно. При n = a a = 1 получаем (1 + a)a - 1 a · a + a2 (mod a3). Число a2 + a2 = 2 a2 + a + = a2 делится на a2 и не делится на a3.

n Предположим теперь, что (a + 1)a - 1 делится на an+1 и не делится на n n+1 n an+2 для некоторого n 1. Тогда (a + 1)a - 1 = (a + 1)a - 1 = (1 + a a + ban+1)a - 1 = a · ban+1 + b2a2n+2 + b3a3n+3 +... (здесь b целое 2 число, которое не делится на a). Если n 1, то 2n + 2 > n + 2, поэтому (a + n++ 1)a - 1 ban+2 (mod an+3); число ban+2 делится на an+2 и не делится на an+3.

14.20. Докажем индукцией по n, что если pk n, где n 2, то p1... pk 4n. При n = 2 требуемое утверждение очевидно. Предположим, что оно доказано для всех чисел, не превосходящих n - 1. Чтобы сделать шаг индукции, разберём отдельно два случая.

Пусть n = 2m. Согласно предположению индукции произведение всех простых чисел, не превосходящих m, не превосходит 4m. Кроме того, все 2m (2m)! простые числа pi, для которых m+1 pi 2m, делят число =, а m m!m! это число не превосходит 22m = 4m. В результате получаем, что произведение простых чисел, не превосходящих n = 2m, не превосходит 4m ·4m = 42m = 4n.

Пусть n = 2m + 1. Согласно предположению индукции произведение всех простых чисел, не превосходящих m + 1, не превосходит 4m+1. Кроме того, все простые числа pi, для которых m + 2 pi 2m + 1, делят число 2m + 1 (2m + 1)! 2m + 1 2m + 1 2m + =. Ясно также, что = и + m m!(m + 1)! m m + 1 m 2m + 1 2m + + 22m+1, поэтому 22m. В результате получаем, что m + 1 m Глава 14. Комбинаторика произведение простых чисел, не превосходящих n = 2m + 1, не превосходит 4m+1 · 22m = 42m+1 = 4n.

14.21. О т в е т: 669. Пусть сумма первых двух цифр равна n, и сумма двух последних цифр тоже равна n. Число n принимает значение от 1 до 18. Если количество двузначных номеров, у которых сумма цифр равна n, равно an, то искомое число равно a2 + a2 +... + a2. Двузначный номер, у которого сумма 1 2 цифр равна n, состоит из цифр a и n - a, где 0 a 9 и 0 n - a 9. Таким образом, 0 a 9 и n - 9 a n. Если n 9, то остаётся неравенство 0 a n, а если n 9, то остаётся неравенство n - 9 a 9. В итоге получаем a1 = 2, a2 = 3,..., a8 = 9, a9 = 10, a10 = 9,..., a17 = 2, a18 = 1.

14.22. О т в е т: 1422 = 20164. Число x2 + y2 делится на 7 тогда и только тогда, когда оба числа x и y делятся на 7. Действительно, квадрат целого числа при делении на 7 даёт остатки 0, 1, 2 и 4. Количество целых чисел, заключённых между 1 и 1000 и делящихся на 7, равно 142. Поэтому искомое число равно 1422 = 20164.

14.23. О т в е т: 686 чисел. Сначала вычеркнем из набора чисел 1, 2,..., 999 числа, кратные 5; их количество равно = 199. Затем из того же набора чисел 1, 2,..., 999 вычеркнем числа, кратные 7; их количество равно = 142. При этом числа, кратные 35, будут вычеркнуты дважды. Их количество равно = 28. Значит, всего мы вычеркнули 199 + 142 - 28 = = 313 чисел, а осталось 999 - 313 = 686 чисел.

14.24. О т в е т: 338 350. Уравнения |x| + |y| = 0, |x| + |y| = 1, |x| + |y| = 2,..., |x| + |y| = 99 имеют, соответственно, 1, 22, 32,..., 1002 целочисленных 100 · 101 · решений. Поэтому искомое число равно 12 +22 +32 +...+1002 = (см. задачу 9.12).

14.25. О т в е т: 2857. Остатки от деления на 7 чисел 2x и x2 повторяются с периодами 3 и 7, поэтому остатки от деления на 7 числа 2x - x2 повторяются с периодом 21. Среди чисел x от 1 до 21 равные остатки от деления на 7 чисел 2x и x2 дают ровно 6 чисел. Поэтому среди чисел от 1 до 9996 = 21 · 476 есть 476 · 6 = 2856 требуемых чисел. Непосредственная проверка с использованием полученной последовательности остатков показывает, что из оставшихся чисел 9997, 9998 и 9999 только число 9998 обладает требуемым свойством.

14.26. Эта задача обобщение задачи 4.19, при решении которой показано, что достаточно рассмотреть случай, когда a1 = p1,..., an = pn и 1 2 n....

Множитель p1 входит только в Pнечёт, причём ровно один раз (когда мы берём набор, состоящий из одного числа a1). Покажем, что все остальные множители, входящие в Pнечёт и в Pчёт, взаимно сокращаются. НОК набора чисел равно pk+1, если одно из этих чисел равно ak+1, а все остальные числа k k выбраны из a1,..., ak. Поэтому в Pнечёт множитель pk+1 входит + + 0 172 Глава 14. Комбинаторика k k k k + +... раз, в Pнечёт этот множитель входит + + +... раз.

4 1 3 Согласно задаче 14.9 б) каждая из этих сумм равна 2k-1.

14.27. О т в е т: 1 769 580. Будем отдельно подсчитывать сумму тысяч, сотен, десятков и единиц для рассматриваемых чисел. На первом месте может стоять любая из пяти цифр 1, 2, 3, 4, 5. Количество всех чисел с фиксированной первой цифрой равно 6 · 6 · 3 = 108, поскольку на втором и третьем месте может стоять любая из шести цифр, а на четвёртом месте может стоять любая из трёх цифр 0, 2, 4 (мы рассматриваем только чётные числа). Поэтому сумма тысяч равна (1 + 2 + 3 + 4 + 5) · 108 · 1000 = 1 620 000. Количество чисел с фиксированной второй цифрой равно 5 · 6 · 3 = 90 (на первом месте стоит любая из пяти цифр). Поэтому сумма сотен равна (1 + 2 + 3 + 4 + 5) · 90 · 100 = = 135 000. Аналогично сумма десятков равна (1+ 2+ 3+ 4+ 5) ·90·10 = 13 500, а сумма единиц равна (2 + 4) · 5 · 6 · 6 = 1 080.

14.28. О т в е т: 139. Пусть множители имеют вид 2a15b1, 2a25b2 и 2a35b3.

Тогда a1 + a2 + a3 = 6 и b1 + b2 + b3 = 6. При этом числа ai и bi могут быть равны нулю. Если a1 = k, то для разложения a2 + a3 = 6 - k получаем 7 - k вариантов. Поэтому для разложения a1 + a2 + a3 = 6 получаем 7 + 6 + 5 + 4 + + 3 + 2 + 1 = 28 вариантов. Всего получаем (28)2 = 784 способа.

Но мы пока не учли тождественность разложений, отличающихся лишь порядком множителей. Есть ровно одно разложение, не зависящее от порядка множителей, в котором все множители равны 100. Те разложения, в которых есть два равных множителя, мы посчитали трижды. В каждый из равных множителей 2 может входить в степени 0, 1, 2 или 3, т.е. всего четырьмя различными способами; столькими же способами может входить 5. Всего получаем 16 разложений такого вида, но одно из них рассмотренное выше разложение с тремя равными множителями. Остаётся 15 разложений, каждое из которых мы посчитали трижды. Количество разложений с попарно различными множителями равно 784 - 1 - 45 = 738. Каждое из них мы посчитали 6 раз, поэтому среди них будет 738/6 = 123 различных разложения.

Всего получаем 1 + 15 + 123 = 139 разложений.

2n 2n 14.29. С одной стороны, 22n = (1 + 1)2n = + +... + 0 2n 2n +. С другой стороны, 2n n 2n (2n)! 2n 2n - 1 n + = = · ·... · 2n, n n!n! n n - 1 2n - k поскольку 2 для k = 0, 1,..., n - 1.

n - k p p(p - 1)... (p - k + 1) 14.30. По определению =. Числитель делится на k 1 · 2... k p, а знаменатель не делится на p. Поэтому целое число, которое получается в результате деления числителя на знаменатель, делится на p.

Глава 14. Комбинаторика p p - 1 p - 14.31. Тождество = + показывает, что k - 1 k k m p m p p - 1 p - (-1)k = (-1)m, т.е. (-1)k = (-1)m - 1.

k=0 k=k m k m p Если 1 m p - 1, то согласно задаче 14.30 каждое слагаемое (-1)k k делится на p.

p 14.32. Тождество (1 + x)np = (1 + x)n показывает, что np p p =....

n k1 kn k1+...+kn=p p Согласно задаче 14.30 число делится на p, если 0 < k < p. Поэтому k в указанной сумме на p2 делятся все слагаемые, за исключением тех, для которых ki = p для некоторого i. Каждое из таких слагаемых равно 1, а их количество равно n.

n n(n - 1) 14.33. При m = 2 нужно доказать, что = делится на n; это m очевидно.

n n(n - 1)... (n - m + 1) Пусть m 3. В выражении = числитель деm 1 · 2 ·... · m лится на n p-2, а наивысшая степень p, на которую делится знаменатель, = m m m m m равна + +... + +... =.

p p2 p p2 p - n 3 Если m = 3, то делится на p в степени - 2 - + +... = m p p = - 2 - - 3 = - m.

p n m m Если m 4, то делится на p в степени - 2 - + + m p pm m +... - 2 - - 2 - - m.

p - 1 n n(n - 1)... (n - k + 1) 14.34. Ясно, что =. Рассматриваемое простое k k! число p делит числитель этой дроби. Пусть pr наибольшая степень p, которая делит хотя бы одно из чисел от n - k + 1 до n включительно; пусть это будет число m (если таких чисел несколько, то мы выбираем любое из них). Сосредоточим внимание на числе m и в соответствии с этим запишем числитель рассматриваемой дроби в виде (m + a)(m + a - 1)... (m + 1)m(m - 1)... (m - b);

здесь m + a = n и m - b = n - k + 1, поэтому k = a + b + 1. Множители знаменателя переставим в соответствии с записью числителя:

k! = a(a - 1) ·... · 1 · (a + 1)(a + 2)... (a + b + 1).

(a + 1)(a + 2)... (a + b + 1) a + b + Число = целое; обозначим его l. Итак, b! b n m + a m + a - 1 m + 1 m - 1 m - 2 m - b m = · ·... · · · ·... · · ;

k a a - 1 1 1 2 b l 174 Глава 14. Комбинаторика m множитель мы переставили в конец.

l Пусть x некоторое целое число, причём -b x a, а pr1 наибольшая степень p, делящая x. Если r1 < r, то наибольшая степень p, которая m + x делит числитель дроби, равна pr1. Степени p в числителе и в знамеx нателе сокращаются. Предположим теперь, что r1 r. Из неравенств для x следует, что n - k + 1 m + x n. Поэтому согласно выбору числа m наиm + x большая степень p, которая делит числитель дроби, не превосходит pr.

x В этом случае после сокращения степень p может остаться только в знаме n нателе. Таким образом, наибольшая степень p, делящая, не превосходит k наибольшей степени p, делящей m. Значит, p pr m n.

14.35. П е р в о е р е ш е н и е. Элемент, не обладающий ни одним из данных свойств, даёт вклад только в первый член N. Элемент, обладающий ровно одним свойством, даёт вклад в первые два члена; его общий вклад равен 1- 1 = 0. Элемент, обладающий ровно k 2 свойствами, даёт вклад в первые k k + 1 членов. В член Ni1...il он даёт вклад, поэтому его общий i1<...

1 2 l k В т о р о е р е ш е н и е. Положим 1, если K-й предмет обладает свойством Pi;

C(K, i) = 0, если не обладает.

Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |   ...   | 65 |



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

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