6_3

ВВЕРХ

Комбинаторные задачи

Задачи, сводящиеся к уравнению или системе

Задачи, с использованием бинома Ньютона

Задачи, с использованием биномиальных коэффициентов

Оглавление

Предметный указатель

Литература

Для доступа к меню нажмите правую кнопку мыши

§ 3. ЗАДАЧИ

Задачи, связанные с определением числа различных способов образования каких-либо групп из заданного множества элементов, относятся к классу так называемых комбинаторных задач. Их решение требует применения логических рассуждений и аппарата теории соединений.
   Проиллюстрируем сказанное следующими задачами.
   Задача 1.На десяти карточках записаны цифры 0, 1, 2, 3, ..., 9. Берут четыре карточки и составляют из цифр, записанных на них, четырехзначное число. Сколько различных четырехзначных чисел можно составить таким образом?
   Решение. Всего различных комбинаций из четырех карточек можно составить столько, сколько существует размещений из 10 элементов по 4. Но условиям задачи не удовлетворяют комбинации цифр, начинающихся нулем. Таких комбинаций будет . Вычтя их из общего числа размещений , получаем искомое:    Задача 2. Сколько различных правильных дробей можно составить из чисел 3, 5, 7, 11, 13, 17, 19, 23 так, чтобы в каждую дробь входило два числа?
   Решение. Очевидно, всего различных дробей из данных чисел можно составить столько, сколько существует размещений из 8 элементов по 2 (), но нас интересуют лишь правильные дроби, которых будет в два раза меньше, т. е.    Эту задачу можно решить иначе.
   Любая пара данных чисел образует только одну правильную дробь. Всего же различных пар, в которых первый элемент меньше второго, будет столько, сколько существует сочетаний из 8 элементов по 2, т. е.    Задача 3. Сколькими способами можно поставить на книжную полку n книг так, чтобы m определенных книг оказались рядом?
   Решение. Пусть m определенных книг оказались в крайнем правом положении. Остальные n - m книг можно расставить (n - m)! способами (число перестановок из n - m элементов). Но m интересующих нас книг можно поставить m! различными способами так, чтобы они занимали крайнее правое положение. Комбинируя каждую из расстановок m интересующих нас книг с расстановками остальных книг, мы имеем m!·(n - m)! способов расстановки книг, при которых интересующие нас книги занимают крайнее правое положение. Но группу из m рядом стоящих книг, как единое целое, можно поставить (n - m + 1)- ю способами (первая из этих книг занимает первое, второе, .. .,(n - m + 1) - е место). Таким образом, число всех способов расстановки книг равно (n - m + 1)·m!·(n - m)!.
   Задача 4. Сколько различных вариантов хоккейной команды можно составить из 9 нападающих, 5 защитников и 3 вратарей, если в состав команды должны войти 3 нападающих, 2 защитника и 1 вратарь?
   Решение. Из 9 нападающих можно выбрать трех различными способами. Из 5 защитников можно выбрать двух различными способами. Из трех вратарей можно выбрать одного вратаря тремя способами. Комбинируя каждую тройку нападающих с парами защитников, получаем различных команд без вратаря. Комбинируя эти команды с каждым из вратарей, имеем различных команд.
   Задача 5. Некто забыл нужный ему номер телефона, который состоит из одной из десяти букв и пяти цифр, но он помнит, что в образовании этого номера участвуют цифры 2, 3, 6, 7. Какое наибольшее число проб надо сделать, чтобы дозвониться нужному абоненту?
   Решение. В искомый телефонный номер должны войти четыре цифры, которые можно разместить на пяти местах личными способами; но пятая цифра может быть любой из десяти. Поэтому число комбинаций из таких пяти цифр равно 10·. Среди них есть и одинаковые. Эти одинаковые комбинации появляются в том случае, когда забытая пятая цифра – 2, 3, 6, 7. Таких комбинаций будет 4·. Исключая из всего количества комбинаций повторяющиеся, получим число различных телефонных номеров без буквы 10· - 2· = 8·. Комбинируя эти номера с каждой из десяти букв, находим число различных проб: 10·8· = 9600.    Задача 6. Сколькими способами можно из 40 человек, поступающих в вуз, создать 4 группы разных специальностей по 10 человек в каждой?
   Решение. Первую группу можно создать способами. Вторую группу можно создать из оставшихся 30 человек способами. Третью группу можно создать из оставшихся 20 человек способами. Оставшиеся 10 человек составят четвертую группу. Итак, число всех различных способов составления четырех групп из 40 человек равно    Задача 7. Группа из 14 юношей и 15 девушек решила посетить театр, но в кассе оказалось лишь 20 билетов (12-й ряд с 1 по 20 - е место). Сколькими способами можно распределить 20 билетов между юношами и девушками так, чтобы никакие две девушки и два юноши не сидели бы рядом?
   Решение. Допустим, 10 юношей займут нечетные места, а девушки четные. В этом случае никакие две девушки не окажутся рядом. Количество способов, которыми можно 10 юношей из 14 рассадить по 10 нечетным местам, есть число размещений из 14 по 10·. 15 девушек при этом по 10 четным местам можно рассадить способами. Таким образом, будет · способов. Такое же число способов будет, если юноши займут четные места, а девушки нечетные. Общее число способов равно 2··.
Уравнение или система, содержащие выражения , и Р_n, где один или оба индекса n и m содержат неизвестное, с помощью формул (1) - (8) сводятся к уравнению или системе, равносильным данным при одном ограничении, что m и n - натуральные.
   В некоторых случаях формулу для удобно записать в факториальной форме:                         (18) Заметим, что из равенства P_n = P_k следует, что n = k, из равенства = следует, что m = l, а из равенства = следует, что либо m = l, либо n - m = l.
   Задача 8. Найти х из уравнения , где n ≥ 10 – натуральное.
   Решение. Согласно формулам (1) и (18) имеем   или   , где x + 2 ≥ 0, х - n ≥ 0 и x ≥ О. Сокращая дробь на х! [(x + 2)! = х!·(х + 1)·(х + 2)], получаем квадратное уравнение х² + З х - 130 = 0, равносильное данному, если х - натуральное. Решая это уравнение, находим, что x = 10 (корень х = - 13 < 0 отбрасывается).
   Задача 9. Найти х из уравнения .
   Решение. Учитывая, что , перепишем данное уравнение в виде   или  , где х ≥ 4.
   Согласно формулам (6) и (7)   и  , поэтому уравнение примет вид откуда следует, что х - 4 = 2, т. е. х = 6.
   Задача 10. Решить уравнение    Решение. Согласно формуле (5) имеем Так как 0 < х < 4 (х = 0 и х = 4 не удовлетворяют уравнению) и (6 - х)! = (6 - х)·(5 - х)·(4 - x)!, то после сокращения на , получаем уравнение равносильное данному при условии, что х < 4 и натуральное. Решая его, находим х² - 17 x + 30 = 0, откуда х = 2 (х = 15 отбрасываем).
   Задача 11. Найти х и у из условия    Решение. Данное условие равносильно системе уравнений где х ≥ у - натуральные числа.
   Из первого уравнения следует, что у + 1 + у = х + 1, т. е. х = 2 у. Тогда из второго уравнения получаем   или  . Сокращая на общий множитель (положительный), имеем 3 (y + 2) = 5 y, откуда y = 3 и х = 6.
Формула общего члена бинома (х + а)ⁿ позволяет, не производя всего разложения целиком, записать любой член разложения, если указан его номер, или найти член, имеющий заданный коэффициент или заданный показатель, если таковые существуют, и т. д.
   Задача 12. Найти все рациональные члены разложения бинома .
   Решение. Пусть искомый член есть Т_{k + 1}. Тогда где k = 0, 1, 2, 3, 4, 5. Из этих чисел нужно выбрать такое k, при котором показатели и суть целые числа. Очевидно, что k = 2 и искомый член .
   Задача 13. Найти х, если известно, что третий член разложения бинома (1 + х^{lg х})⁵ равен 1 000 000.
   Решение. Имеем По условию 10 x^{3 + 2 lg x} = 1 000 000. Логарифмируя данное равенство по основанию 10 ( х > 0) (см. гл. VIII), получаем уравнение 2 lg²x + 3 lg x - 5 = 0, откуда находим, что х₁ = 10, x₂ = 10^{- 5/2}.
   Задача 14. Найти коэффициент при х⁴ в разложении (1 + 2 x + 3 x²)¹⁰.    Решение. Записав данное выражение в виде [(1 + 2 x) + З x²]¹⁰, имеем [(1 + 2 x) + З x²]¹⁰ = (1 + 2 x)¹⁰ + 10·З x²·(1 + 2 x)⁹ + 45·9·x⁴·(1 + 2 x)⁸ + … Следующие члены не выписываем, так как они содержат х в степени выше четвертой. Выписывая коэффициенты при х⁴ у каждого слагаемого правой части, находим    Задача 15. Определить показатель n (n - натуральное) разложения по убывающим степеням величины х, если 10-й от начала член разложения имеет наибольший коэффициент.
   Решение. Имеем Так как коэффициент этого члена наибольший, а коэффициенты 11 и 9-го членов равны соответственно и , то или Раскрывая символы и производя все сокращения, получаем где n - натуральное.
   Таким образом, если решение задачи существует, то оно единственное и равно 13. Остается показать, что решение существует, т. е. для всех k = 0, 1, 2, ..., 13. Беря отношение коэффициентов предыдущего и последующего членов, имеем так как при k < 9 и при k > 9, то отсюда следует, что при k < 9 коэффициенты членов возрастают, с ростом k при k > 9 они убывают. Поэтому коэффициент 10-го члена от начала – наибольший.
   Задача 16. Найти показатель бинома (а + 5)^т и номер члена, коэффициент которого при степени а равен 853 125, если его биномиальный коэффициент равен 1365.
   Решение. Допустим, что искомый номер равен р + 1. Тогда , причем = 1365, а ·5^p = 853 125. Отсюда следует, что 5^p = 625 = 5⁴ и р = 4.
   Для определения n имеем уравнение , или n·(n - 1)·(n - 2)·(n - 3) = 4!·1365. Разложим 1365 на простые множители: 1365= 13·7·5·3. Тогда n·(n - 1)·(n - 2)·(n - 3) = 13·15·7·3·2³=15·14·13·12. Так как n целое, то n = 15. Это решение единственное, так как при n > 15 величина n·(n - 1)·(n - 2)·(n - 3) > 15·14·13·12, а при n < 15 величина n·(n - 1)·(n - 2)·(n - 3) < 15·14·13·12,
Используя формулы (6), (7) и (8), (10) и свойства биномиальных коэффициентов, удается получить ряд соотношений между числами .
   Задача 17. Вычислить сумму    Решение. Согласно формуле (10) Полагая х = 1, имеем    Задача 18. Доказать, что при n > p    Решение. Согласно формуле (9) для любого 0 ≤ k ≤ n. Поэтому Складывая левые и правые части всех этих равенств, после приведения подобных получаем что и требовалось доказать.
   Задача 19. Вычислить сумму    Решение. Согласно формуле (8) Полагая k = 0, 1, 2, ..., n, имеем откуда В квадратных скобках стоит сумма всех биномиальных коэффициентов бинома (х + а)ⁿ⁺¹, кроме первого . По свойству биномиальных коэффициентов она равна 2^{n + 1} - 1 и    Задача 20. Вычислить сумму    Решение. Вновь используя формулу (8), для m = 1, 2, ...,n имеем Поэтому так как по свойству биномиальных коэффициентов выражение, стоящее в квадратных скобках, равно нулю.
   В некоторых случаях выгодно подобрать такой многочлен, чтобы искомая сумма была коэффициентом при некоторой степени х.
   Задача 21. Вычислить сумму    Решение. Искомая сумма является коэффициентом при хⁿ в многочлене Учитывая, что , имеем причем xⁿ содержит (n + 1) - й член: Следовательно, искомая сумма .