GATE CSE 2003 | Question: 4

Question

Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such that

1. each is sorted in ascending order,
2. $B$ has $5$ and $C$ has $3$ elements, and
3. the result of merging $B$ and $C$ gives $A$

• A. $2$
• B. $30$
• C. $56$
• D. $256$

Comments

Very useful conceptual clarity. @Tushar Rana

---

Select one of them B or C next will automatic arrange
So

8C3 = 56
Option C

---

https://youtu.be/C1CjtxYEbeM?t=784

Answer 1

If you pick any $3$ numbers in the given order from the array(sorted) remaining $5$ elements are already sorted. You can not change the relative position of those $5$ elements because they are distinct and already sorted. So no of ways $= {}^8C_3.$

Same argument holds for picking up $5$ elements initially. No of ways $= {}^8C_5.$

Correct Answer: $C$

Comments

Thanks @ Debashish Deka

 here the question asks only for selection and not for an arrangement of the selected nos. This is where I got confused. pick 3 or 5 elements, remaining elements will remain sorted since all are distinct nos.

---

(1) Let A be a sequence of 8 distinct integers sorted in descending order. How many distinct pairs of sequences, B and C are there such that each is shorted in a descending order?

(2) Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that B has 3 and C has 5 elements?

(3) Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that result of merging B and C gives A?

---

merging part make me confused to select option A->2

---

nice explaination bro

Answer 2

answer - C

select any $3$ elements from given $8$ elements - $^8C_3$

Comments

You're counting same thing twice na. If you've picked up 3 elements for C, then by default 5 left out elements would be for set B.

Let's say we've three elements instead of 8 = {1,2,3}

For B you chose two elements out of 3, 3C2= {1,2} or {1,3} or {2,3} (not 3P2 since you can't rearrange them) So for C, you've got only one choice = {3}, {2}, {1} ) So total possible combinations are 3.

Say you chose elements for C first i.e., {1}, {2}, {3}

For B again, you've got to choose {2,3}, {1,3}, {1,2} only.

So you can see, if you consider choosing B and C as separate events, you'd have counted same possibilities twice.

Whenever such confusions occur, just try breaking the problem into smaller one.

---

How come it's interpreted that we are selecting any 3 only in the given order. It's not specified in the question. So I am not sure how come it's 8C3.
8C3 would mean that I can select any 3 irrespective of the order.

Can anyone explain this?

---

In this question it is important to note that combination sequences do not have order.

for B sequences possible would be ->n-1C4+n-2C4+n-3C4+n-4C4  if you cal you get ->56

for C sequences possible would be ->n-1C2+n-2C2+n-3C2+n-4C2+n-5C2+n-6C2→ if you cal you get ->56

everytime you pick from the remainning elements ,you get another order so consider that order to be in increasing order .

now small observation here is for all B sequences there should be set C such that on merging you get A here you can think that for every possible sequence of B of 5 elements there will be a sequence of 3 elements in C such that on B intersection C is empty or null ,hence these sequence will also be 56 ,hence the answer would be 56  only

Answer 3

The question actually is based on combinations not merging.Firstl y two arrays are taken : B having 3 elements and C having 5 elements sorted in ascending order and then merged into a single array A having 8 elements.We have to find no of distinct sequences. 8 elements can be arranged in 8! ways out of that 3 elements of array B can be arranged in 3! ways and 5 elements of C can be arranged in 5! ways. Now, No. of distinct sequences = 8!/3! 5! = 56 Ans.

Comments

@arjun sir "We have to find no of distinct sequences. "

could u plz explain this ?what does it mean

---

C(8,5)  produces distinct sequences

---

Jitendra Verma

but we want them in sorted order ryt?

Answer 4

A can have sequence of 8 distinct integers which are sorted in ascending order.
→ If we are pick 3 elements from 8 sequence integers then remaining 5 elements are already in ascending order. After merging these elements then it gives A.
→ No. of possibilities of choosing 3 elements from total of 8 = $^8C$$_3$
= 8!/3!5!
= 8 * 7
= 56

Comments

It should be no of ways of choosing 3 integers from 8 integers

Correction required

---

Corrected
Thanks !!

Answer 5

.

Answer 6

You can think this way also