[RESOLVED] distinct pairs of sequences

[Harsh Gupta]

hi all!!

i m preparing for post-graduation..........just checking prev years' papers n found this interesting ques!! but can't figure out the answer.....plz help me!!

Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, Band C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 8 elements, and (iii) the result of merging B and C, gives A ?

thnx!!

[zaza]

B has 5 and C has 8 elements

Do you mean "C has 3 elements"?

If so, then effectively you are saying "how do I choose 5 integers from 8 (the other 3 being determined by elimination) and ensure that both sets are in ascending order?"

In other words, you want only 1 permutation out of each possible combination...

zaza

[Harsh Gupta]

Do you mean "C has 3 elements"?

If so, then effectively you are saying "how do I choose 5 integers from 8 (the other 3 being determined by elimination) and ensure that both sets are in ascending order?"

In other words, you want only 1 permutation out of each possible combination...

zaza

thnx for your reply zaza............i m sorry i cant help u in this!!!
i saw this question in one of the previous competitive papers i downloaded from the net............so possibly u r right...........possibly wrong!!

[Harsh Gupta]

ok if we agree that "C has 3 elements", then wot will be the probability??

PS - i usually make mistakes in probability!!!

[Harsh Gupta]

hey..............no one interested???

[krtxmrtz]

How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order?

Are the sequences B and C to be considered distinguishable?

For example:

A = (1,3,4,6) ; B = (2,5,7,8)

and

A = (2,5,7,8) ; B = (1,3,4,6)

are counted as one pair or as two?

[krtxmrtz]

Are the sequences B and C to be considered distinguishable?

I guess not... then, there will be C(8,1) + C(8,2) + C(8,3) + C(8,4) sequences, where C(I,J) = I! / [J! * (I - J)!]

Total: 162

[Harsh Gupta]

oh sorry.........for such a late reply!!!

i m sorry krtxmrtz that i cannot help u if B n C are distinguishable coz i found this question in some previous set of papers so i copy-pasted the exact question!!!

plus it showed 4 options which are 2, 30, 56 or 256............so ur answer doesn't seem to fit newhere (i tried modifying your concept but in vain)

thnx

[krtxmrtz]

... it showed 4 options which are 2, 30, 56 or 256............so ur answer doesn't seem to fit newhere (i tried modifying your concept but in vain)

Well, these problems are certainly tricky and I may have overlooked something... I'll have a go at it again as soon as I can.

[zaza]

Er...krtxmrtz has already given the answer:

nCr = n! / [r! * (n - r)!]

You need the number of ways of picking 5 distinct objects from 8 object. The remaining 3 objects are determined simply because they are the ones left over. When you have picked those 5 objects, you can arrange them in a number of different ways. However, you want them in ascending order which means that you want them in only one way.
nCr tells you how many different combinations there are of individual items. Hence for each possible combination, the order is irrelevant as far as nCr is concerned.

So the answer is simply the number of combinations, 8C5, which is to say, 56.

To make it a bit easier, consider 3 objects. How many ways can you pick 2 objects from those 3? 1&2. 1&3. 2&3. That's 3 ways. nCr does not include 2&1, because this is the same as the first combination. And 3C2 is, you guessed it, 3. Try it using the formula above.

zaza

[Harsh Gupta]

Er...krtxmrtz has already given the answer:

nCr = n! / [r! * (n - r)!]

You need the number of ways of picking 5 distinct objects from 8 object. The remaining 3 objects are determined simply because they are the ones left over. When you have picked those 5 objects, you can arrange them in a number of different ways. However, you want them in ascending order which means that you want them in only one way.
nCr tells you how many different combinations there are of individual items. Hence for each possible combination, the order is irrelevant as far as nCr is concerned.

So the answer is simply the number of combinations, 8C5, which is to say, 56.

To make it a bit easier, consider 3 objects. How many ways can you pick 2 objects from those 3? 1&2. 1&3. 2&3. That's 3 ways. nCr does not include 2&1, because this is the same as the first combination. And 3C2 is, you guessed it, 3. Try it using the formula above.

zaza

ummmm the question says that A has 8 distinct integers in ascending order so i think u r not on the right track!!! (sorry if my language hurts you)

plus i think that there is some error in the question!!?!?!? i think the answer is 2 (if we agree that the ques is correct)

PS - i will come tomorrow to explain why i think so!!!

[zaza]

Hm, maybe I misunderstood then.
According to your original post, you say that A has 8 distinct integers sorted in ascending order. Choose B and C such that B has 5 elements and C has (3) and merging B and C gives A.

I take this to mean that elements from B and C can be intermingled to give A, hence my previous answer.
If, by the question, you require B and C to remain as entities then of course there are only two possible answers because there are only two selection groups, B and C. You can then have B containing the first 5 elements of A and C containing the last 3, or C containing the first 3 and B the last 5.

However, that seems a bit of a trivial question to me...

zaza

[krtxmrtz]

Maybe I misunderstood the question too. Why don't you post a few pairs of sequences as an example?

[Harsh Gupta]

sorry but i m marking this thread resolved, probably the question was misprinted or there is some other error!!