Книги по разным темам Pages:     | 1 |   ...   | 17 | 18 | 19 | 20 | 21 |   ...   | 65 |

13.11. Для n = 2, 4 и 5 требуемое неравенство несложно проверить. Покажем, что при n 5 из неравенства 3n > n3 следует неравенство 3n+1 > (n + + 1)3. По предположению индукции 3n+1 > 3n3, поэтому нужно лишь проверить неравенство 2n3 > 3n2 + 3n + 1. При n 5 выполняются неравенства 1 < 3n < 3n2 < 2n3/3, поэтому 3n2 + 3n + 1 < 3(2n3/3) = 2n3.

13.12. Пусть a = 2 + 2 +... + 2. Тогда 2 + 2 +... + 2 = n-1 n = 2 + a.

Таким образом, требуется доказать, что 2 - 2 + a >.

2 - a Индукцией по n легко доказать, что a < 2. Поэтому следующие неравенства эквивалентны требуемому:

8 - 4 2 + a > 2 - a, 6 + a > 4 2 + a.

После возведения в квадрат получаем неравенство 36 + 12a + a2 > 32 + 16a, т.е. (a - 2)2 > 0.

13.13. Применим индукцию по n. При n = 1 получаем очевидное тождество. Равенство a1a2 a1a2a3 a1a2 ... anan+2 a1 + + +... + = 2 4 2n a2a3 a2a3 ... an+= a1 + a1 a2 + +... + 2 2 2n-1 показывает, что a1a2 a1a2a3 a1a2 ... anan+cos 2 a1 + + +... + = 2 4 2n a2a3 a2a3 ... an+= - sin a2 + +... +.

2 2n-1 Воспользовавшись этой формулой и тождеством 2 sin = 2 - 2 cos, получим a1a2 a1a2a3 a1a2 ... anan+2 sin a1 + + +... + = 2 4 2n a2a3 a2a3 ... anan+= a1 2 + 2 sin a2 + +... +.

2 2n-1 Глава 13. Индукция Нетрудно также убедиться, что в действительности всегда берётся знак плюс, a1a2 a1a2a3 a1a2 ... anan+поскольку знак числа a1 + + +... + совпадает 2 4 2n со знаком числа a1. Теперь, воспользовавшись предположением индукции, получаем требуемое тождество.

13.14. Применим индукцию по числу автомобилей n. При n = 1 утверждение очевидно. Предположим, что утверждение доказано для n автомобилей. Рассмотрим теперь n + 1 автомобиль. Ясно, что среди них обязательно найдётся автомобиль A, который может доехать до следующего за ним автомобиля B, поскольку иначе бензина во всех автомобилях не хватило бы для того, чтобы проехать один раз по всей кольцевой дороге. Выльем бензин из B в A и уберём B. Среди оставшихся n автомобилей по предположению индукции найдётся автомобиль, который может проехать по всей кольцевой дороге, забирая по пути бензин у остальных автомобилей. Тогда тот же самый автомобиль сможет проехать по всей кольцевой дороге и в исходной ситуации, до переливания бензина из B в A. Действительно, доехать от A до B он сможет, а на всех остальных участках дороги бензина у него будет ровно столько же, сколько и в ситуации с n автомобилями.

13.15. Будем считать, что дробь m/n несократимая. Применим индукцию по m. При m = 1 доказывать нечего. Пусть m > 1. Разделим n на m с остатком, причём частное запишем в виде d0 - 1, а остаток запишем в виде m m-k, т.е. n = m(d0-1)+(m-k) = md0-k, где d0 > 1 и 0 < k < m. Тогда = n 1 k = 1 +. По предположению индукции дробь k/n можно представить d0 n в требуемом виде:

k 1 1 = + +... +.

n d1 d1d2 d1d2... dr Поэтому дробь m 1 1 1 = + + +... + n d0 d0d1 d0d1d2 d0d1d2... dr тоже можно представить в требуемом виде.

Глава 14.

Комбинаторика 14.1. Элементы комбинаторики 14.1. Сколькими способами можно выбрать k предметов из n различных предметов, если порядок, в котором выбираются предметы: а) учитывается; б) не учитывается.

n n n 14.2. Докажите, что (x + y)n = xkyn-k, где = k=k k n! =.

k!(n - k)! n n! Число = называют биномиальным коэффициентом.

k k!(n k)! - n Удобно считать, что = 0, если n < 0 или k > n.

k n n n + 14.3. Докажите, что + =.

k k - 1 k 14.4. Сколько ожерелий можно составить из пяти белых бусинок и двух чёрных 14.5. а) Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг б) Сколько ожерелий можно составить из семи различных бусин 14.6. Сколько существует различных путей на плоскости, ведущих из точки с координатами (0, n) в точку с координатами (m, m), если двигаться разрешено каждый раз либо на 1 вверх (координата y увеличивается на 1), либо на 1 влево (координата x уменьшается на 1) 14.7. а) Сколькими способами натуральное число n можно представить в виде суммы m целых неотрицательных чисел, если представлеГлава 14. Комбинаторика ния n = x1 +... + xm и n = y1 +... + ym считаются одинаковыми тогда и только тогда, когда x1 = y1,..., xm = ym б) Тот же вопрос для представлений в виде суммы натуральных чисел.

14.8. Докажите, что n! 1 k (x1 +... + xk)n = xl ... xl.

1 k l1! ... lk! l1+...+lk=n 14.2. Тождества для биномиальных коэффициентов 14.9. Докажите, что:

n n n а) + +... + = 2n.

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

0 2 4 6 1 3 n n + m m n m 14.10. Докажите, что = + +... + k 0 k 1 k - m n + (Вандермонд).

k 2n n n n 14.11. Докажите, что = ( )2 + ( )2 +... + ( )2.

n 0 1 n n - i 2n n 14.12. Докажите, что = 2n-k-2i.

i n + k k i + k n - 1 n n + 14.13. Докажите, что = k - 1 k + 1 k n - 1 n + 1 n =.

k k + 1 k - n - r 14.14. Докажите, что если p+q = 1, то (-1)r prqr = 0 r n/r pn+1 - qn+=.

p - q 14.15. Пусть P (x) многочлен степени n, причём P (x) = 2x для x = 1, 2,..., n + 1. Вычислите P (n + 2).

14.16. Докажите, что n n n n m = n2n-1 и m2 = n(n + 1)2n-2.

m m m=1 m=162 Глава 14. Комбинаторика 14.17. Докажите, что n n 1 n 2n+1 - 1 (-1)m n = и =.

m + 1 m n + 1 m + 1 m n + m=1 m=14.18. Докажите, что если |x| < 1, то n n + k - = 1 + xk.

1 - x n - k=См. также задачи 29.53, 29.54.

14.3. Бином Ньютона в арифметике n n 14.19. Докажите, что числа (a + 1)a - 1 и (a - 1)a + 1 делятся на an+1 и не делятся на an+2.

14.20. Пусть p1 = 2, p2 = 3,... последовательные простые числа.

k Докажите, что p1... pk 4p.

14.4. Комбинаторика в арифметике 14.21. Сколько существует четырёхзначных номеров (от 0001 до 9999), у которых сумма двух первых цифр равна сумме двух последних цифр 14.22. Сколько существует таких пар целых чисел x, y, заключённых между 1 и 1000, что x2 + y2 делится на 7 14.23. Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7 14.24. Сколько различных целочисленных решений имеет неравенство |x| + |y| < 100 14.25. Сколько существует натуральных чисел x, меньших 10 000, для которых 2x - x2 делится на 7 14.26. Докажите, что НОД(a1,..., an) = Pнечёт/Pчёт, где Pнечёт произведение НОК всех наборов, состоящих из нечётного числа различных чисел a1,..., an, а Pчёт произведение НОК всех наборов, состоящих из чётного числа различных чисел a1,..., an. (Предполагается, что числа a1,..., an попарно различны.) Глава 14. Комбинаторика 14.27. Даны 6 цифр: 0, 1, 2, 3, 4, 5. Найдите сумму всех четырёхзначных чётных чисел, которые можно написать этими цифрами (одна и та же цифра в числе может повторяться).

14.28. Сколькими различными способами можно представить 1 000 000 в виде произведения трёх натуральных чисел Произведения, отличающиеся лишь порядком сомножителей, считаются одинаковыми.

14.5. Неравенства для биномиальных коэффициентов 2n 14.29. Докажите, что 2n 22n.

n 14.6. Арифметика биномиальных коэффициентов p 14.30. Пусть p простое число и 1 k p - 1. Докажите, что k делится на p.

14.31. Пусть p простое число. Докажите, что для всех натураль p - ных m p - 1 число (-1)m - 1 делится на p.

m np 14.32. Докажите, что если p простое число, то n n (mod p2).

14.33. Пусть p нечётное простое число, n = p-2, где 2.

n Докажите, что если m 2, то делится на p-m.

m n 14.34. Пусть p простое число. Докажите, что если p делит, k то p n.

См. также задачи 21.31, 21.32.

14.7. Формула включений и исключений 14.35. Дано N предметов и некоторый набор свойств P1,..., Pn.

Пусть Ni количество предметов, обладающих свойством Pi, Nij количество предметов, обладающих свойствами Pi и Pj, и т.д. Докажите, что количество предметов, не обладающих ни одним из данных 164 Глава 14. Комбинаторика свойств, равно N - Ni + Ni i2 - Ni i2i3 +... + (-1)nN123...n 1 i1

1 k 14.36. Пусть n = pa... pa разложение числа на различные про1 k стые множители, (n) количество чисел от 1 до n, взаимно простых с n. Докажите, что 1 1 (n) = n 1 - 1 -... 1 -.

p1 p2 pk 14.37. а) Докажите, что количество перестановок a1,..., an чисел 1,..., n, для которых ai = i при всех i, равно 1 1 (-1)k (-1)n n! 1 - 1 + - +... + +... +.

2! 3! k! n! б) Докажите, что доля таких перестановок среди всех перестановок стремится к 1/e при n.

14.8. Аналоги биномиальных коэффициентов 14.38. Пусть m и n целые неотрицательные числа. Докажите, что m!(2n + 2m)! число целое.

(2m)!n!(n + m)! 14.9. Числа Каталана Пусть c0 = 1, c1 = c0c0 = 1, c2 = c0c1 + c1c0 = 2, c3 = c0c2 + c1c1 + +c2c0 = 5 и вообще ck = c0ck-1+c1ck-2+...+ck-1c0. Числа ck, заданные таким рекуррентным соотношением, называют числами Каталана.

14.39. Докажите, что количество различных способов разрезать выпуклый n-угольник на треугольники непересекающимися диагоналями равно cn-2. (Эйлер) 14.40. В строку записана n + 1 буква. Требуется расставить n пар круглых скобок так, чтобы внутри каждой пары скобок стояли либо две соседние буквы, либо буква и соседнее выражение в скобках, либо два Глава 14. Комбинаторика соседних выражения в скобках1. Докажите, что количество различных расстановок скобок равно cn. (Каталан) 14.41. В расстановке скобок из задачи 14.40 сотрём все буквы и две крайние скобки (правую и левую). То, что получится, назовём правильной скобочной структурой. Докажите, что количество правильных скобочных структур из n пар скобок равно cn.

Путём Дика из 2n звеньев называют ломаную на плоскости, которая соединяет точки с координатами (0, 0) и (0, 2n), имеет векторы звеньев (1, 1) и целиком лежит в верхней полуплоскости x 0. (Векторы последовательных звеньев могут быть одинаковыми.) Один из путей Дика изображён на рис. 14.1.

Рис. 14.1.

14.42. а) Докажите, что число различных путей Дика из 2n звеньев равно cn.

б) Докажите, что число различных путей Дика из 2n звеньев равно 1 2n.

n + 1 n 14.43. а) Докажите, что количество различных последовательностей a1, a2,..., a2n, для которых ai = 1, a1 0, a1 + a2 0,..., a1 + a2 +... + a2n-1 0 и a1 + a2 +... + a2n = 0, равно cn.

б) Кассир, у которого в начальный момент времени денег нет, продаёт билеты по 50 рублей. Очередь состоит из 2n человек, у половины из которых есть только одна купюра 100 рублей, а у другой половины 50 рублей. Докажите, что количество различных порядков очереди, для которых кассир сможет всем дать сдачу, равно cn.

14.44. Шахматная ладья движется из левого нижнего угла доски nn в правый верхний угол. При этом она делает ходы только вправо и Вот пример такой расстановки скобок: ((a((bc)d))(ef)).

166 Глава 14. Комбинаторика вверх. Докажите, что количество различных путей, при которых ладья никогда не попадает на главную диагональ, за исключением исходного и конечного положения, равно cn-2.

14.45. Плоским бинарным деревом называют граф на плоскости, у которого нет циклов и из каждой вершины выходят либо три ребра, либо одно ребро. Фиксируем одну вершину, из которой выходит одно ребро, и будем называть её корнем. Все остальные вершины, из которых выходит ровно одно ребро, будем называть листьями. Докажите, что количество различных плоских бинарных деревьев с одним корнем и n листьями равно cn-1. (Кэли) 14.46. Вершины правильного (2n + 1)-угольника помечены нулями и единицами. Всего есть n + 1 нуль и n единиц. Будем считать два таких набора пометок одинаковыми, если они получаются друг из друга поворотом многоугольника.

а) Докажите, что количество различных наборов пометок равно 1 2n + 1 1 2n =.

2n + 1 n n + 1 n б) Докажите, что количество различных наборов пометок равно cn.

14.47. Пусть = ap,qxpyq. Докажите, что p,q=1 - x - y 2xy + 1 2n (-1)na2n,2n+2 = число Каталана cn.

n + 1 n 14.10. Элементы теории вероятностей 14.48. Какая сумма выпавших чисел более вероятна при бросании двух игральных костей: 9 или 10 14.49. Мальчик должен сыграть в теннис три матча со своими родителями. Он будет считаться победителем, если выиграет подряд два матча. Отец играет лучше, чем мать. Какой порядок матчей предпочтительнее для мальчика: отецЦматьЦотец или матьЦотецЦмать 14.50. Силы двух игроков равны, т.е. они имеют равные шансы на победу в каждой партии. Они договорились, что приз получит тот, кто первым выиграет 6 партий. Им пришлось прервать игру после того, как первый игрок выиграл 5 партий, а второй 3. В каком отношении справедливо разделить приз 14.51. В ящике лежат красные и чёрные носки. Если из ящика наугад вытащить два носка, то вероятность того, что они оба красные, равна 1/2.

Глава 14. Комбинаторика а) Какое наименьшее число носков может быть в ящике б) Какое наименьшее число носков может быть в ящике, если известно, что число чёрных носков чётно 14.52. На каждой грани игральной доски написано одно из чисел от 1 до 6, но некоторые числа могут быть написаны несколько раз. Будем говорить, что кость X выигрывает у Y, если при одновременном бросании этих костей на X выпадает большее число, чем на Y, с вероятностью больше 1/2. Могут ли три кости A, B, C обладать следующими свойствами: B выигрывает у A, C выигрывает у B, A выигрывает у C Решения 14.1. а) Первый предмет можно выбрать n способами, второй предмет n - 1 способами,..., k-й предмет n - k + 1 способами. Всего получаем n! n(n - 1)... (n - k + 1) = способов.

(n - k)! б) Каждому набору из k предметов, в котором порядок предметов не учитывается, соответствует k! наборов, которых порядок предметов учитывается (это соответствует выбору k предметов из k различных предметов). Всего по 1 n! n лучаем = способов.

k! (n - k)! k 14.2. Коэффициент при xkyn-k в разложении (x + y)n равен количеству способов пометить k множителей в произведении n множителей x + y. Действительно, в каждом отмеченном множителе мы берём x, а в каждом неотмеченном множителе мы берём y. Остаётся воспользоваться результатом задачи 14.1 б).

14.3. Воспользуемся тождеством (1+x)n(1+x) = (1+x)n+1. Коэффициент n n n + при xk в левой части равен +, а в правой части равен.

k k - 1 k 14.4. О т в е т: 3. Чёрные бусинки разбивают белые бусинки на две группы (одна из этих групп может содержать 0 бусинок). Вид ожерелья полностью определяется количеством бусинок в меньшей группе. Это количество может быть равно 0, 1 или 2.

14.5. а) О т в е т: 720. Семь девушек на семь разных мест в хороводе можно расставить 7! = 5040 способами. Но в хороводе расположения, которые получаются при движении хоровода, не различаются. Поворотами хоровода из одного расположения можно получить 7 других расположений. Поэтому всего получается 7!/7 = 6! = 720 способов.

Pages:     | 1 |   ...   | 17 | 18 | 19 | 20 | 21 |   ...   | 65 |    Книги по разным темам