Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 24

Для заданного набора элементов N = {1, 2,…, n} и двух произвольных подмножеств A⊆N и B⊆N, сколько из n! перестановки π из N в N удовлетворяют min (π (A)) = min (π (B)), где min (S) — наименьшее целое число в наборе целых чисел S, а π (S) — множество получаемых целых чисел применяя перестановку π к каждому элементу S?

(A) (n — | A ∪ B |) | A | | B |
(B) (| A | 2 + | B | 2 ) n 2
(С) n! | A∩B | / | A∪B |
(D) | A∩B | 2 нКл | A∪B |

Ответ: (с)
Пояснение: Сначала давайте поймем, какой вопрос задают. Таким образом, π — это функция от N до N, которая просто переставляет элементы N, поэтому будет n! такие перестановки. Теперь, учитывая конкретное π, т.е. конкретную схему перестановок, мы должны найти число перестановок из этих n! перестановки, в которых минимальные элементы A и B после применения к ним одинаковы.
Так, например, если N = {1,2,3}, π равно {2,3,1}, а если A равно {1,3}, то π (A) = {2,1}.
Теперь число элементов в A ∪ B равно | A ∪ B |. Мы можем выбрать перестановки для A ∪ B в nC | A∪B | пути. Обратите внимание, что здесь мы просто выбираем элементы для перестановки, а не переставляем. Пусть это выбранное множество будет P. Теперь, когда мы выбрали числа для перестановок, мы должны выбрать отображение из каждого элемента A ∪ B в некоторый элемент P.
Поэтому, прежде всего, для достижения требуемого условия, указанного в вопросе, мы должны отобразить минимальное число в P на любое число в A ∩ B, так что min (π (A)) = min (π (B)). Мы можем сделать это в | A∩B | пути, так как мы можем выбрать любой элемент | A∩B | сопоставляться с минимальным числом в P.
Теперь мы подошли к перестановке. Мы можем переставлять числа в P в | A∪B-1 |! пути, так как один номер (минимум) уже зафиксирован.
Кроме того, мы также можем переставить оставшиеся n — | A∪B-1 | в (n — | A∪B-1 |)! пути, так что всего нет. путей =
нКл | A∪B | * | A∩B | * | A∪B-1 |! * (п | A∪B-1 |)! = п |! A∩B || A∪B |
Таким образом, вариант (C) является правильным.
Примечание. На некоторых ключах ответов в Интернете ответ отображается как опция (D), что явно неверно. Предположим, что | A ∪ B | = 3 и | A ∩ B | = 1 и n = 4, тогда опция (D) оценивается как 14 = 0,25, что не имеет смысла.

Источник: http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2006.html.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2006 | Вопрос 24

0.00 (0%) 0 votes