Discrete Mathematics Combinatories GATE Previous Years Solved Questions / Garg's Academy

Ques 1: How many substrings (of all lengths inclusive) can be formed from a character string of length n?

GATE 1989

Ans: 1+[n(n+1)/2]

Solution: Lets take an example .

Lets consider the given string is {GATE}.

So, set of string of length 1={G,A,T,E} cardinality of set =4

Set of strings of length 2={GA,AT,TE}.

Set of strings of length 3={GAT,ATE}.

Set of strings of length 4={GATE}.

Set of strings of length 0={}.

We cannot have any substring of length 5 as the given string has only 4 length.

So total no of substrings possible

=0length substring+1length substrings+2length substrings+3length substrings+4length substrings.

=(1+4+3+2+1).

This means for 1 length substring to n length substrings, count will sum of the n natural numbers from 1 to n.

=1+2+3+…+n

=n(n+1)2
So total no. of substrings possible =0length strings+n(n+1)2=1+[n(n+1)/2].

Ques 2: In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada. 9 persons speak both English and Hindi, 11 persons speak both Hindi and Kannada whereas 13 persons speak both Kannada and English. How many speak all three languages?

GATE 1998

(A) 9

(B) 8

(D) 6

Ans: (D) 6

Solution: Apply set formula of A U B U C

28=(18+15+22)−(9+11+13)+x

28=55−33+x

28=22+x

x=28-22

x=6

Ques 3: Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers among themselves?

GATE 1999

(A) 1638

(B) 2100

(D) None of these

Ans: 2640

Solution: Number Of ways Roses Can Be Distributed ={(0,10),(1,9),(2,8),…,(10,0)}=11

Similarly, Sunflowers And Daffodils Can Be Distributed In 16 and 15 ways each.

So, Total Number Of Ways =11×16×15=2640

Ques 4: The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is

GATE 2000

(A) 3

(B) 8

(D) 12

Ans: 9

Solution: There are 4 suits of cards. Space, Ace, Diamond, Hearts

So, upto 4 cards there is a chance that no more than 1 card are from a given suite

and, upto 8 cards there is a chance that no more than 2 cards are from a given suite.

But, once we pick the 9th one, it should make 3 cards from any one of the sets.

So, (C)is the answer.

Ques 5: How many 4-digit even numbers have all 4 digits distinct?

GATE 2001

(A) 2240

(B) 2296

(D) 4536

Ans: (B) 2296

Solution: If the number ends with a 0 then there are 9 choices for the first digit, 8 for the second and 7 for the third

which makes 1×9×8×7=504 possibilities.

If the number is even ending with something else than 0 then

there are 4 choices (2,4,6,8) for the last digit,

8 choices for the first digit (no 0 nor the last digit),

8 for the second digit and

7 for the third digit, which makes 4×8×8×7

=1792

Together, this gives 1792+504=2296 numbers with 4 distinct digits that are even.

Note that this does not allow leading 0, as you see to want it based from the question.

So, Correct Answer: B

Ques 6: 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

GATE 2003

each is sorted in ascending order

B has 5 and C has 3 elements, and

the result of merging B and C gives A

(A) 2

(B) 30

(D) 256

Ans: (C) 56

Solution: Required no=8!/(5! x 3!)=56

Ques 7: n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

GATE 2003

(A) ²ⁿC_n×2ⁿ

(B) 3ⁿ

(D) ²ⁿC_n

Ans: (B) 3ⁿ

Solution:Possible outcomes for a couple:

only wife comes
both husband and wife come
neither husband nor wife comes

Thus 3 possibilities for each couple, so 3×3×3×⋯×3……………⏟n times=3ⁿ

Correct Answer: B

Ques 8: Mala has the colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colour pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?

GATE 2004

(A) 9

(B) 8

(D) 6

Ans: (C) 7

Sloution: This question is slightly ambiguous. So, first, let us understand what the question is asking. So in a book, we have letters A to Z and each letter is printed twice, so there are 52 letters. Now we have to color each letter, so we need a pair of colors for that because each letter is printed twice. Also in a pair, both colors can be the same. Now the condition is that a pair of colors can’t be used more than once.

So, suppose Mala has 3 colors :Red, Blue, Green ,She can color as follows :

(Red, Red)(Red, Red)
(Blue, Blue)(Blue, Blue)
(Green, Green)(Green, Green)
(Red, Blue)(Red, Blue)
(Red, Green)(Red, Green)
(Blue, Green)(Blue, Green)

Now we don’t have more pairs of colors left, we have used all pairs, but could color only 6 letters out of 26.

Now, question is to find minimum no. of colors, so that we could color all 26 letters.

So, if Mala has k colors, she can have k pairs of the same colors, thus coloring k letters, and ^kC₂ other pairs of colors, thus coloring ^kC₂ more letters.
So, total no. of letters colored = k+^kC₂

=k+k(k−1)/2

=k(k+1)/2

Now k(k+1)/2≥26

k(k+1)≥52

So,k≥7.

So, option (C) is correct.

Ques 9: In how many ways can we distribute 5 distinct balls, B1,B2,…,B5 in 5 distinct cells, C1,C2,…,C5 such that Ball Bi is not in cell Ci, ∀i=1,2,…5 and each cell contains exactly one ball?

GATE 2004 IT

(A) 44

(B) 96

(D) 3125

Ans: (A) 44

Solution: Total arrangements possible = 5! = 120

1 combination when all balls are at their respective places

so remaining arrangements = 120 – 1 = 119

this eliminates Options C & D

when B1 is placed at C1

no. of arrangements = 1 * 4 ! = 24

so remaining arrangements = 119 – 24 = 95

this eliminates Options B

So Answer is A

Ques 10: The exponent of 11 in the prime factorization of 300! is

GATE IT 2008

(A) 27

(B) 28

(D) 30

Ans: (C) 29

Solution: The numbers from 1 to 300 , divisible by 11 =27

The numbers 121 and 242 are further divisible by 11

So total= 29

Ques 11: The number of divisors of 2100 is?

GATE 2015 Set 2

Ans: 36

Given number 2100

=2×1050

=2x2x525

=2x2x3x175

=2x2x3x5x35

=2x2x3x5x5x7

Hence, total number of factors will be =3×2×3×2=36

because any factor is obtained by multiplying the prime factors zero or more times. (one extra for zero)

Ques 1: How many substrings (of all lengths inclusive) can be formed from a character string of length n?

Ques 3: Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers among themselves?

Ques 4: The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is

Ques 5: How many 4-digit even numbers have all 4 digits distinct?

Ques 6: 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

Ques 7: n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

Ques 9: In how many ways can we distribute 5 distinct balls, B1,B2,…,B5 in 5 distinct cells, C1,C2,…,C5 such that Ball Bi is not in cell Ci, ∀i=1,2,…5 and each cell contains exactly one ball?

Ques 10: The exponent of 11 in the prime factorization of 300! is

Ques 11: The number of divisors of 2100 is?

Related Posts