Skip to content
GATETECH
Official PYQ · 2004Q75Combinatorics: Counting, Recurrence Relations, Generating FunctionsMCQ1 mark

GATE CS 2004 Q75 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Explain with AI

Mala has the colouring book in which each English letter is drawn two times. She wants to paint each of these 5252 prints with one of kk 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 kk that satisfies this requirement?

Choose one option
View worked solution

Answer: C

To find the minimum number of colours kk required, let us model the problem mathematically:

  1. There are 2626 English letters, each having 22 prints.
  2. For each letter, we need to choose a pair of colours from the kk available colours.
  3. Since the order of the prints for a single letter does not distinguish the pair, and both prints can be coloured with the same colour, the colour pair is an unordered combination of 22 colours chosen from kk colours with repetition allowed.

The number of ways to choose an unordered pair of colours from kk colours (allowing repetition) is:

Total unique colour pairs=(k2)+k=k(k−1)2+k=k(k+1)2\text{Total unique colour pairs} = \binom{k}{2} + k = \frac{k(k-1)}{2} + k = \frac{k(k+1)}{2}

To ensure that each of the 2626 letters is assigned a unique colour pair, the number of available unique colour pairs must be at least 2626:

k(k+1)2≥26  ⟹  k(k+1)≥52\frac{k(k+1)}{2} \ge 26 \implies k(k+1) \ge 52

Now, we test the minimum integer value of kk that satisfies this inequality:

  • For k=6k = 6: 6×7=42<526 \times 7 = 42 < 52 (Insufficient)
  • For k=7k = 7: 7×8=56≥527 \times 8 = 56 \ge 52 (Sufficient)

Thus, the minimum value of kk is 77.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Combinatorics: Counting, Recurrence Relations, Generating Functions questions