7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Hint: count the number of winning guesses, $W$, count the total number of guesses, $T$. The minimum is $T-W+1$ $\endgroup$ – lulu Sep 10 '15 at 11:24
  • 2
    $\begingroup$ 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. $\endgroup$ – paw88789 Sep 10 '15 at 11:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Paddling Ghost Sep 10 '15 at 12:39
  • 4
    $\begingroup$ 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. $\endgroup$ – paw88789 Sep 10 '15 at 12:44
  • 2
    $\begingroup$ 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. $\endgroup$ – user264781 Sep 10 '15 at 12:51
5
$\begingroup$

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

This particular one can be found in this paper, and it is equal to 24.

The covering table is also given, I reproduce it here:

AAAA AABB ABAB ABBA ACCC ADDD CACD CCDA CDAC DDCA DADC DCAD BAAB BABA BBAA BBBB BCCC BDDD CBCD CCDB CDBC DDCB DBDC DCBD

Reference: Covering theorems for vectors with special reference to the case of four and five components. R. G. Stanton, J. D. Horton and J. G. Kalbfleisch

$\endgroup$
  • 1
    $\begingroup$ This question is from an ongoing competition: puzzleup.com/2015. I've flagged it for moderator attention; you might want to delete your answer before the moderators get around to it. (Here's the math.SE policy on ongoing contest questions: meta.math.stackexchange.com/questions/16774/…) $\endgroup$ – joriki Sep 11 '15 at 17:23

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.