The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2.2k 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.5k points)
edited by | 2.2k 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
+1

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 42 ordered pairs and also 14 pairs of same colours which sums up 52 and we have 52 prints to color

3 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
+6
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.

+6

@ 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)
+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.
+2 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 (11k 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

38,040 questions
45,536 answers
131,819 comments
48,853 users