edited by
16,466 views
65 votes
65 votes

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?

  1. $9$
  2. $8$
  3. $7$
  4. $6$
edited by

9 Answers

Best answer
94 votes
94 votes

This question is slightly ambiguous. So, first, let us understand what the question is asking. So in a book, we have letters $\text{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 $:\text{Red, Blue, Green}$.

She can color as follows :

  1. $\left(\text{Red, Red}\right)$
  2. $\left(\text{Blue, Blue}\right)$
  3. $\left(\text{Green, Green}\right)$
  4. $\left(\text{Red, Blue}\right)$
  5. $\left(\text{Red, Green}\right)$
  6. $\left(\text{Blue, Green}\right)$

Now we don't have more pairs of colors left, we have used all pairs, but could color only $6$ letters out of ${26}$. So, 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, then $^kC_2$ other pairs of colors, thus coloring $^kC_2$ more letters. 
So, total no. of letters colored = $k + \binom{k}{2} = k+ k \left( \frac{k−1}{2} \right) = k \left( \frac{k+1}{2} \right)$. 
So, we want $k \left( \frac{k+1}{ 2} \right) \geq 26$ i.e. $k \left(k+1\right) \geq 52 \implies k \geq  7$.

So, option (C) is correct.

Ref: http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2004.html

edited by
26 votes
26 votes

In this question are two important lines

(1)Color pairs used to color any two letters are different- Means Say (A,A) is painted with (c1,c2) and (B,B) is painted with (c3,c4) then it should not be the case for any such letter pair that (c1=c3 and c2=c4). 

(2)Both prints of a letter can be colored with same color- Means (A,A) can be colored using single color also say c1.

Now, since options are given, we start with minimum possible option that is 6.

First, since pairs of Same letter can go with 1 color, A-F pairs are colored with 6 colors C1-C6.

Now using 6 colors, we can form 6C2=15 pairs which can further be used to color the letter pairs from (GG) to (UU)

Now we have exhausted all ways in which we can use 6 colors to paint our letterbook, but still some letters are remaining (5 of them)

Using one extra color, say C7, we can form  6 new color pairs from existing colors C1-C6

(C1,C7),(C2,C7).......(C6,C7)- 6 of new color pairs.

5 pairs of letters can be colored with this.

Hence, we need only 7 colors.

Ans -(c) 

13 votes
13 votes
The question converts to combination question.

Suppose we have k colors and we are required to select 2 colors from k colors with repetitions since AA,BB .... ZZ can be colored with same color.

$\binom{k+2-1}{2}>=26$

 

solving the above equation gives k=7
3 votes
3 votes
Use this by option elimination :

k=6 : We can use same color pairs (c1,c1),(c2,c2).......(c6,c6) so 6 alphabets can be colored. Now to color remaining alphabets we will use cobination of different color now total pairs c(6,2)=15 so now only 21 alphabets can  be colored.

k=7- 7 alphabets having same color comb.and remaining comb.=c(7,2)=21 so all alphabets can be colored.

so minimum 7 colors
Answer:

Related questions

59 votes
59 votes
4 answers
3
go_editor asked Apr 24, 2016
19,515 views
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$\begin{array}{|l|l|c|} \hline \text {Instruction} & \text...