The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2.4k 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$
asked in Combinatory by Veteran (59.6k points)
edited by | 2.4k views
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.

+1
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.)
0
@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
+3

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 colors like if AA(blue,blue) then BB can not be colored with (blue,blue)

How answer is 7?

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,

4 Answers

+36 votes
Best answer

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

answered by Loyal (5.9k points)
edited by
+7
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??
+1
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.
0
someone please explain question itself in easy way
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.

+7

@ Prateek K  

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)

So, adding 14+42=56>52

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

explain this please

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). 

0
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.
+3 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) 

answered by Boss (14k points)
0
Option C
+2 votes
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.
answered by Active (3.2k points)
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.
0 votes
K² should be at least 52 to color all colors.
=> K >= 7
Therefore minimum 7 colors are required.
answered by (39 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,994 questions
47,622 answers
146,900 comments
62,346 users