Смешанные задачи

Задача 1. В классе обучаются 42 ученика. Из них 16 участвуют в секции по легкой атлетике, 24 – в футбольной секции, 15 – в шахматной секции, 11 – и в секции по легкой атлетике и в футбольной, 8 – и легкоатлетической и в шахматной, а 6 – во всех трех секциях. Остальные школьники увлекаются только туризмом. Сколько школьников являются туристами?

Решение:

Обозначим через U множество всех учащихся, через А – членов легкоатлетической секции, через В – футбольной, через С – шахматной и через D – туристической. По условию задачи имеем:

U = A È B È C È D,

причем

D Ç (A È B È C) = Æ

и n(U) = 42, n(A) = 16, n(B) = 24, n(C) = 15, n(A Ç B) = 11, n(A Ç C) = 8,

n(B Ç C) = 12, n(A Ç B Ç C) = 6.

По формуле

n(A È B È C) = n(A) + n(B) + n(C) + n(A Ç B) - n(A Ç C) -

- n(B Ç C) + n(A Ç B Ç C).

получаем, что

n(A È B È C) = 16 + 24 + 15 - 11 - 8 - 12 + 6 = 30,

и потому

n(D) = n(U) - n(A È B È C) = 42 - 30 = 12

Значит, туризмом занимаются 12 школьников.

Задача 2. Сколько номеров, состоящих из двух букв, за которыми идут пять цифр, можно составить, использовав 32 буквы и 10 цифр?

Решение:

. Обозначим множество из 32 букв через А, а множество из 10 цифр через В. Каждый номер требуемого вида является кортежем из декартова произведения A ´ A ´ B ´ B Ч B. Так как n(A) = 32, n(B)= 10, то по правилу произведения имеем:

n(A Ч A Ч B Ч B Ч B) = 32 × 32 × 10 × 10 × 10 = 1 024 000.

Задача 3. На книжной полке стоят 10 книг по математике и 10 по логике. Доказать, что наибольшее количество вариантов комплекта, содержащего 10 книг, возможно в том случае, когда число книг по каждому предмету равно 5.

Решение:

. Сначала найдем число вариантов комплекта, содержащего 5 книг по каждому из предметов. Для этого пронумеруем все книги. Получим, что номера 1 - 5 – книги по математике, 6 - 10 – книги по логике. Отобрать 5 книг по математике мы можем способами (число сочетаний без повторений). При каждом варианте отбора, книги по логике мы можем отобрать также способами. Значит, всего вариантов отбора будет . Но отсчет книг можно вести и в обратном порядке, значит число вариантов возрастет вдвое. Это и будет число вариантов комплекта из 5 книг по каждому предмету. Докажем теперь, что наибольшее кол-во вариантов будет в том случае, когда книг по каждому предмету - 5. Действительно, если бы кол-во книг по одному из предметов было больше 5, то по другому стало бы меньше 5 (т.к. кол-во книг комплекта - 10). Рассмотрим частный случай, когда комплект составляется из 6 книг по одному из предметов. Общее число вариантов тогда будет , а это меньше, чем в предыдущем случае. При дальнейшем увеличении числа книг по одному предмету в комплекте общее число вариантов будет уменьшаться, следовательно наибольшее число вариантов комплекта содержащего 10 книг, возможно в том случае, когда число книг по каждому предмету равно 5.

Задача 4. Имеется n абонентов телефонной сети. Сколькими способами можно одновременно соединить три пары?

Решение:

Сначала выбираем 6 абонентов С ⁶_n способами. Располагаем этих абонентов в любом порядке и разбиваем на пары (первый, второй, потом третий и четвертый и, наконец, пятый и шестой). Это можно рассчитать , используя формулу перестановки без повторений, то есть 6! способами. Так как абонентов можно переставлять внутри каждой пары, а также несущественен порядок пар, то общее число способов надо разделить на 2 ³*3!=48 (3! - количество способов перестановки внутри каждой из пар). Всего получаем n!/(48*(n-6)!) способов.

Задача 5. Несколько человек садятся за круглый стол. Будем считать, что два способа рассадки совпадают, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколькими различными способами можно посадить четырех человек? А семь человек? Во скольких случаях два данных человека из семи оказываются соседями? Во скольких случаях данный человек (из семи) имеет двух данных соседей?

Решение:

Отношение соседства сохраняется при циклических перестановках и при симметричном отражении. В случае 4 человек мы имеем 2*4=8 преобразований, сохраняющих отношение соседства. Так как общее число перестановок 4 человек равно 4!=24, то имеем 24/8=3 различных способа рассадки. Если за столом сидят 7 человек, то имеем 7!/14=360 способов, вообще, в случае n человек ( n-1)!/2 способов. Число способов, при которых 2 данных человека сидят рядом, вдвое больше числа способов посадить 6 человек(в силу возможности поменять этих людей местами). Значит, оно равно 5!=120. Аналогично, число способов, при которых данный человек имеет двух соседей, равно 4!=24.

Задача 6. Сколькими способами можно вынуть 4 карты из полной колоды так, чтобы были 3 масти? Так, чтобы были 2 масти?

Решение:

4 карты из полной колоды можно вынуть С ⁴₅₂ способами. Ровно 3 масти будут в А ²₄(С ¹₁₃)²С ²₁₃=518184 случаях - мы выбираем отсутствующую и повторяющуюся масти А ²₄ способами, после чего выбираем две карты повторяющейся масти С ²₁₃ способами и по одной карте двух мастей (С ¹₁₃)² способами. Ровно две масти будут в С ²₄(С ²₁₃)²+А²₄С ³₁₃С ¹₁₃=81120 случаях. В самом деле, это возможно либо если имеем по две карты двух мастей, либо одна карта одной масти и три другой. В первом случае надо выбрать две масти и по две карты каждой из этих мастей, а во втором выбрать первую и вторую масти(здесь уже играет роль порядок мастей), а потом взять три карты первой и одну карту второй масти.

Задача 7 В шахматной олимпиаде участвуют представители n стран по 4 представителя от каждой страны. Сколькими способами можно они могут встать в ряд так, чтобы рядом с каждым был представитель той же страны?

Решение:

Разобьем сначала игроков каждой страны на упорядоченные пары. Для каждой страны это можно сделать 4!/2=12 способами(порядок самих пар не существенен). Всего получим 12 ⁿ способов разбиения. Пары можно переставлять друг с другом (2n)! способами. Поэтому общее число допустимых перестановок равно 12 ⁿ(2n)!

Задача 8. Во скольких случаях данные двое мужчин окажутся во одной лодке со своими женами?

Решение:

Если данные двое мужчин попадают в одну и ту же группу (и в ней находятся их жены), то остальные могут разбиться на группы (8!)²/(2⁸*4!) способами. Если же они попадают в разные группы, то эти группы можно дополнить (А²₈)² способами, после чего разбить остальных на группы 6!/(2⁶*3!) способами. Всего получаем 17(8!)²/2⁸4! способов.

Задача 9. Укротитель хочет вывести на арену цирка n львов и k тигров; при этом нельзя, чтобы два тигра шли друг за другом. Сколькими способами он может расположить зверей?

Решение:

Поставим сначала всех львов так, чтобы между каждыми двумя львами был промежуток. Это можно сделать n! способами. Число промежутков равно k. Если присоединить к ним еще 2 места - впереди всех львов и позади них, то получится n+1 мест, на которые можно поставить тигров, причем никакие два тигра не окажутся рядом друг с другом. Так как порядок тигров существенен, то число способов их расстановки равно числу размещений из n+1 по k, то есть А ^k_n+1. Комбинируя каждый способ расстановки львов с одним из способов расстановки тигров, получаем Р_nA^k_n+1=n!(n+1)!/(n-k+1)! способами. Это возможно лишь при условии, что k<=n+1 - иначе два тигра обязательно окажутся рядом.