# GATE2004-75

6.6k views

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
0

@Arjun  @Anu

7C2 = 21, then how can we color 26 letters distinctively using  21 color combinations. If we consider that pair (Red, Green) and (Green, Red) as two different pair then we will get 42 combinations. However , by this logic we get 6C2 = 15 that means 30 color combinations. Since, in question it is asked minimum value of k, then the answer should be 6(Option D).

Now if consider that color pair (Red, Green) = (Green , Red ) then 8C2 = 28 , then by this logic answer should be 8(Option B).

In either case, 7(option C) can't be the correct answer. Am I missing anything here? Please explain.

Thank you.

2
Important point is --> question is to find minimum no. of colors, so that we could color all 26 letters(such that one pair(like AA, BB etc) color combination is not same as any other pair.)
1
@Arjun sir can it be done with combinations with repetitions as I interpret the problem as (AA, BB, CC...) pairs are allowed and also some other color combinations like (AB, BC, AC, CD, ....). therefore I applied $\binom{n-1+r}{r}$ where n = number of colors and r = 2 (choosing pair of colors)

If n = 7 then $\binom{8}{2}$ = 28 different combination pairs and

as we have 26 such pairs, therefore, it will suffice.

Any suggestions on whether what I am thinking is correct or not?
0
@Prateek K HINT: red,green   green,green   red,red  are all different
24

Question in easy language :

1. Mala has the colouring book in which each English letter is drawn two times
2. {AA,BB,CC,DD,EE,.........,YY,ZZ}
3. There are 26 pairs
4. Each of two letters of these pairs can be colored by same or different colors
5. For example if we have 2 colors red and blue then AA(Blue,Red) or (Red,Blue) or (Blue,Blue) or (Red,Red)
6. But pairs should not have same combination like if AA(blue,red) then BB can not be colored with (blue,red)

with 7 we can create $\binom{7}{2}$ and also 7 pairs of same colors which sums up 28 and we have 26 pairs to color

0
if AA AB AC ...BB BC ....YZ DONE THEIR WILL BE 26C2 combinations +26 combinations,
0

how can (red,red) be a pair of colors?? it's not a pair it's single color answer should be 8.

0

@Mk Utkarsh how can {BB} or {R,R} considered a pair? this is a single color not a pair

0

Both prints of a letter can also be coloured with the same colour

0

@Mk Utkarsh it means we can color BOTH COPIES of a letter, with same combination, it doesn't mean that we can make a pair of same color, right?

That's why have considered 26 and not 52 letters.

7

it doesn't mean that we can make a pair of same color, right?

yes we can that's why 7 is the answer

if pairs are made of distinct colors, then there are $\binom{7}{2} = 21$ combinations

and $7$ more combinations such as (red,red), (blue,blue)

which adds upto $28$ and total english letters are $26$.

So requirement is fulfilled with $7$ colors

0

@Mk Utkarsh this is only my concern, how can you consider "and 7 more combinations such as (red,red), (blue,blue)" these as pairs? {blue,blue} is not a pair it's a single color.

0

it means we can color BOTH COPIES of a letter, with same combination,

a letter can be colored with a color so if both copies are colored with same color then it is a valid combination.

0

every combination is a pair right? you are coloring both letters with some color $(x,y)$

I don't think question is ambiguous in any sense

Question explicitly mentions to remove confusion that

Both prints of a letter can also be coloured with the same colour

which tells us that (red,red) is a valid pair

0

what to say now? :(

you're using this definition "Both prints of a letter can also be coloured with the same colour" at two places, at one place to consider {red,red} as a pair and at second place to consider 52 letters as 26 pairs.

0

@Mk Utkarsh now i got it, the correct answer is 7 and we can use {red,red} I misinterpreted the question.

0

yes question is very confusing and tough to solve it in first go

0

0

with 7 colours we can paint 7C2 +7=28( here 7 is added coz " Both prints of a letter can also be coloured with the same colour" ) sheets (each containing two same letters).

This question is slightly ambigous. So first let us understand what 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 same. Now 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(Red,Red\right),2:\left(Blue,Blue\right),3:\left(Green,Green\right),$

$4:\left(Red,Blue\right),5:\left(Red,Green\right),6:\left(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 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
0
We won't consider ordered pairs .. like (red, blue) is same as (blue, red ).

Right ?
0
why have we used " >= " ?
0
@arjun sir
so with 7 colours . maximum I can colour for 28 order pair ?
0

Didn't understand

if Mala has k colors, she can have k pairs of same colors, thus coloring k letters, then kC2 other pairs of colors,

3 colors => 6 pairs of colors not 3 !

How come  " coloring k letters, then kC2 other pairs of colors,  " ?

Not getting it properly

0
is every letter colored with 2 colors??
2
LETTERS ARE WRITTEN IN THE FOLLOWING WAY-

AA BB CC DD EE FF ..... AND SO ON.

WE CAN USE SAME COLOR FOR SAME LETTERS,

so with k colors we can color k letters and then we can pair them in KC2 ways. Every pair needs to be distinct. So kC2 letters can be further colored.
1
someone please explain question itself in easy way
1

@Arjun  @Anu

7C2 = 21, then how can we color 26 letters distinctively using  21 color combinations. If we consider that pair (Red, Green) and (Green, Red) as two different pair then we will get 42 combinations. However , by this logic we get 6C2 = 15 that means 30 color combinations. Since, in question it is asked minimum value of k, then the answer should be 6(Option D).

Now if consider that color pair (Red, Green) = (Green , Red ) then 8C2 = 28 , then by this logic answer should be 8(Option B).

In either case, 7(option C) can't be the correct answer. Am I missing anything here? Please explain.

Thank you.

19

Actually we are coloring 52 letters

not 26 letters

Now here work with pair of letters

so, with 7 colors we can make 21 color pair

Now as here (Red,Blue) is distinct from (Blue,Red)

So, by this 21 color pair we can actually color 42 letters, where all pairs are distinct..................(i)

Now, we can do two pair of letter with same color

So, (Red,Red) also makes a pair

With 7 colors we can make 14 letters.........(ii)

WE can say from this with 7 colors we can definitely colors 52 letters

0
Thanks...
0

One color pair can color only A or both AB as it has two colors?

@Srestha,why should we consider 52 letters?Question says that  both prints of a letter can be colored with same letters, so if i write letters as:-

AB CD EF GH IJ KL MN OP QR ST ..............AB CD

Now, i can use the same pair to color both AB,as it says same both prints can be colored with same letters?

Now in 26 alphabets i can have 13 pairs. If k colors i choose, then k+C(k,2) will be number of pairs and this should be >= 13?

Question says both prints can be colored with same letter,why are we not using that information

0

k(k+12)≥26

0
@rajesh raj sir...with 7 colours we can print 28 letters...what to conclude from this..anybody pls reply
0
@rambo
With seven colors we can  have 28 unique pairs.
Each pair can be used to color both instances of single alphabet. eg (green,  red) can be used to color alphabet 'A'(1st copy, with green color)  as well as 'A'(2nd copy with Red color)
0

I didnt understood how we have written this line. Kindly elaborate. Thanks in advance.

So total no. of letters colored = k+(k2)=k+k(k−12)=k(k+12).

2
Since there are $k$ colors so total pairs would be  $k{^2}$

Total letters=$52$

Since both prints of a letter can also be with the same color . Such $(a,a)$ color pairs are $k$ times.

So $1$ same color pair paint two same letters. So such same color pairs can be used to color $2k$ letters.

Now remaining color pairs are $k^{2} - k$

But for this remaining pair I shouldn't multiply by $2$ as in these remaining pairs I already have both $(a,b) , (b,a)$ pairs.

So  let's say $(a,b)$ color two letters.

In the same way $(b,a)$ color same two letters.

So both of this pairs are will color two letters only and this two pairs are there in the $k^{2} - k$ list.

So total no of letters are colored is  $k^{2} - k + 2k = k^{2} +k$ which must be greater than equals to $52$ else all the $52$ letters won't be covered by $K$ colors or in other words by all the pairs of $k$ colors.

So, $k^{2} +k>=52$

$k(k+1)>=52$

So $k>=7$ is the min solution of this inequality.
0

So @srestha it means here we have to consider color pairs to be different which means permutation of colors in a pair matters rather than combination right?

I mean like AA and BB can be colored with (Red,Green) and (Green,Red) because pair (Red,Green) is different from pair (Green,Red) in arrangement but not in combination right?

0
yes, right.
0
0
@srestha I think (R,G) is same as (G,R), hence we are taking (k + kC2) and not (k + kP2). If you think both pairs are different, then in the example above we would have got 9 pairs from 3 colors and not 6. Please verify as colouring AA with (red, green) or (green, red) is basically one and the same thing.
0

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) 0
Option C
0

My doubt is in this line :

colour pairs used to colour any two letters are different

Why is it that we compare color pairs used for AA with BB? Like for example there are 2 colors c1 and c2.

According to your solution, $A_1 A_2$->(c1,c1), $B_1 B_2$->(c2,c2), $C_1 C_2$->(c1,c2).

$X_1$ denotes letter X from $1^{st}$ set and 2 from the next set.

My doubt is that why aren't we comparing color pairs used for $A_1 B_1$ with  $C_1 C_2$ because it says that color pairs for "any two letters" are different..? :/

2

@MiNiPanda-Color pair used to color any two letters are different and not two letter pairs.

0

@Ayush Upadhyaya I wonder why i wrote that  when I see my doubt now :P

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
0
Why this isn’t the Best Answer.
I was doing K(K-1)>=26

but i understood that this is wrong because=>BECAUSE k(k-1) would give only the distinct pairs.  and not the repeated pairs.
0
It also overcounts. K(K-1) gives the total no arrangements of 2 colours out of k colours i.e. P(k,2).

It counts (red, blue) And (blue, red) both.
1 vote
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
K² should be at least 52 to color all colors.
=> K >= 7
Therefore minimum 7 colors are required.

Let say we just have 6 English letters, A, B, C, D, E, F  and k = 3(Assuming I have red, green, black color) with 3c2 = we get just 3 combinations, i.e p1(red, green), p2(black, green) and p3(red, black) with these three pairs we can assign to 3 pair of letters  p1(AA) , p2(BB), p3(CC) but wait what about other 3 more pairs CC, EE, FF they can be assigned 3 colored as follows(Red Red ) , (Green Green) and (Black Black),   hence we can use same approach.

For our problem we have 26pairs and if k = 6 we can just have 6c2 = 15 can be colored and 6 more with same color for pair so this is invalid we could not color all 26 pairs.

with k = 7, we can color 7C2 = 21 and plus 7 more so we have covered all 26 pairs.

 LETTERS COLOURS(Ci) A A C1 C1 B B C2 C2 C C C1 C2 D D C3 C3 E E C1 C3 F F C2 C3 G G C4 C4 H H C1 C4 I I C2 C4 J J C3 C4 K K C5 C5 L L C1 C5 M M C2 C5 N N C3 C5 O O C4 C5 P P C6 C6 Q Q C1 C6 R R C2 C6 S S C3 C6 T T C4 C6 U U C5 C6 V V C7 C7 W W C1 C7 X X C2 C7 Y Y C3 C7 Z Z C4 C7

=> Minimum 7 colours are needed.

## Related questions

1
7.3k views
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
Consider three IP networks $A, B$ and $C$. Host $H_A$ in network $A$ sends messages each containing $180$ $bytes$ of application data to a host $H_C$ in network $C$. The TCP layer prefixes $20$ byte header to the message. This passes through an intermediate network $B$. The maximum packet ... other overheads. $325.5$ $\text{Kbps}$ $354.5$ $\text{Kbps}$ $409.6$ $\text{Kbps}$ $512.0$ $\text{Kbps}$
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{Operation }& \text{Instruction size (in Words)} \\\hline \text{MOV $R_1,5000$} & \text{$R1$} \ ... text{2 clock cycles }\\\hline \end{array} The total number of clock cycles required to execute the program is $29$ $24$ $23$ $20$
Consider the grammar rule $E \rightarrow E1 - E2$ for arith­metic expressions. The code generated is targeted to a CPU having a single user register. The sub­traction operation requires the first operand to be in the register. If $E1$ and $E2$ do not have any com­mon ... first Evaluation of $E1$ and $E2$ should necessarily be interleaved Order of evaluation of $E1$ and $E2$ is of no consequence