# What is the minimum number of guesses in order to guarantee to win the prize?

Your friend will pick a $4$-letter word and you will make guesses in order to find it.

-A word can contain only the letters $A, B, C,\:\text {and} \:D$, and they can be used more than once. $(AAAA-DDDD)$.

-In your guess if at least three letters are in their correct places you will win a prize. What is the minimum number of guesses in order to guarantee to win the prize?

• Hint: count the number of winning guesses, $W$, count the total number of guesses, $T$. The minimum is $T-W+1$ – lulu Sep 10 '15 at 11:24
• You shouldn't ever have to go through all the wrong guesses. For instance if you guess ABCD as your first guess and its wrong, you can eliminate ABC?, AB?D, A?CD, and ?BCD words. – paw88789 Sep 10 '15 at 11:44
• I wondering whether this can be reduced to a domination number of some graph... Consider a graph where every vertex represents a possible 4 letter code. Now let two vertices be adjacent if their 2 codes differ by exactly 1 spot. Then, indeed, a dominating set would be a set of guesses where you are guaranteed success. – Paddling Ghost Sep 10 '15 at 12:39
• An upper bound is $64$ since there are $64$ combinations for the first three letters, and you can run through these in $64$ tries, with the fourth letter of each guess being arbitrary. – paw88789 Sep 10 '15 at 12:44
• A lower bound is 20, since each of your guesses rule out 13 combinations (itself, and the $3\times 4$ ways of changing one of the four letters). There are 256 possibilities in total, so since $19\times 13<256$, 19 guesses cannot rule out all possibilities. Unfortunately, this is still far from the upper bound above. – user264781 Sep 10 '15 at 12:51

You are looking for the covering code number $K_4(4,1)$. Finding such numbers are very hard problems in general.