Mala has a coloring book in which each English letter is drawn two times.She wants to paint each of these 52 prints with one of the $k$ colors,such that the color pairs used to color any two letters are different.Both prints of the same color can be colored with the same color.What is the minimum number of $k$ that satisfies this requirement?

My progress so far : there is a pair of each letter which can be colored with same color. i.e. $k \cdot k =k^2$ ways to color pair of letters . But Now I don't find way to tackle it further. What is the connection b/w total letters pairs and $k^2$??

More Progress: I came to a conclusion ,see if we have k colors and 26 letters ,and we need every pair of colors to be different ,$k >=26$. But now we have $k^2$ instead of K ,hence $k^2>=26$ might be solution!!

More Progress:But it seems problem of coloring AA,BB.....ZZ is no different than A,B...Z. answer might be $k>=26$

  • $\begingroup$ Is {Red, Blue} and {Blue, Red} considered the same or different? $\endgroup$ – Masked Man Feb 11 '14 at 13:34
  • $\begingroup$ @Happy I indeed don't know ,Qus is very ambiguous in it's detail. But what if they are considered same and what if not? How would you solve it? Although what Ross Millikan has considered is that they are same. $\endgroup$ – Rishi Feb 11 '14 at 14:25

Given $k$ colors, we can color $k$ letters with both occurrences having the same color. We can also color ${k \choose 2}=\frac 12k(k-1)$ letters with two different colors. We need $k+\frac 12k(k-1)=\frac 12k(k+1) \ge 26$, so $k=7$ is sufficient.

  • $\begingroup$ ${k \choose 2}=\frac 12k(k-1)$ This might including first steps result also,in which you have calculated n different colors for n letters ,don't you thing we need to minus n from final result? $\endgroup$ – Rishi Feb 9 '14 at 8:54
  • 1
    $\begingroup$ No, the $k-1$ factor says we made the second one different from the first. The factor $\frac 12$ is because red/blue is the same as blue/red. It is the standard result of the number of ways to selec two different colors from $k$ $\endgroup$ – Ross Millikan Feb 9 '14 at 15:42

I find the problem difficult to understand. The letter A appears twice; suppose that the first time it appears, we color it blue. Suppose also the first time B appears, we color it green. Then, if I understand the problem, we can't color any other letter green; if we color, say, Q green, then A and Q have the same color pair as A and B. By the same reasoning, no two distinct letters can ever be given the same color. So, we need 26 colors, one for each letter.

  • $\begingroup$ it like AA it's a pair of same letter ,Both can have same color But AB is a pair of distinct letters and hence need to be colored with distinct colors. $\endgroup$ – Rishi Feb 9 '14 at 6:00
  • $\begingroup$ I know that, but I don't see what difference it makes. Both appearances of A can be colored blue, both appearances of B can be colored green, and so on. But the problem statement is so unclear, it is hard for me to know whether this meets the requirements. Maybe you could solve the problem for, say, a 3-letter alphabet, and we'd see more clearly what the question is. $\endgroup$ – Gerry Myerson Feb 9 '14 at 6:02
  • $\begingroup$ yes,I too think exactly like you I mean what's the difference will it make . for e.g AA,BB,CC you will need 3 colors atleast to color them distinctly.It doesn't make any difference to problem of A,B,C and color them distinctly . A and AA can be taken as single entity to be colored. And must be 3 in this case i.e. total no. of letter OR pairs. $\endgroup$ – Rishi Feb 9 '14 at 6:14
  • $\begingroup$ As I understood the question, you could have AA both blue, BB both green and CC blue and green. AB wouldn't come into it. $\endgroup$ – Empy2 Feb 9 '14 at 6:23
  • $\begingroup$ @Michael, then there would be a pair AC with the color pair blue & green, and also a pair AB with the color pair blue & green. So, the color pair used to color A & B doesn't differ from the color pair used to color A & C, violating (my interpretation of) the conditions. $\endgroup$ – Gerry Myerson Feb 9 '14 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.