Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Followup on 5-letter Mastermind

Consider the word list: CODES COKES COLES COMES CONES COPES CORES COSES COTES COVES COXES COZES. How many 5-letter words do you have to guess to identify one of them? (Reminder: for each guess you are told which letters are exact matches, and which are present elsewhere in the word.)

You need to test for the presence of all but one of DKLMNPRSTVXZ. Note that even if you could guess arbitrary 5-letter strings it would still take you three rounds to identify the word! I will demonstrate that it takes at least four rounds, given the restriction to only use valid five-letter words as guesses.

To find a K-word solution, we need to partition the 12 letters into K+1 groups. One group consists only of a single letter--- this is the "nothing else matches" case. The other groups should have at least one and no more than 5 letters. We can restrict this further to no more than 4 letters by observing that there are no vowels in the set of letters.

(SOWPODS does include three words with no vowels: CRWTH, CWTCH, and PHPHT. But none of these consist of 5 letters from our set of interest.)

But, rather than generating all partitions and then looking for words that match, let's look for all words that match any subset of the letters. Then we can try building partitions.

Subsets of size 1: (trivially) all have words

Subsets of size 2: (nontrivially) all 66 pairs have valid words

Subsets of size 3: 188 of the 220 triples have valid words

Subsets of size 4: 89 of the 495 combinations have valid words. DKLS DKNR DKNS DKRS DKST DLMS DLNS DLPS DLRS DLRT DLST DLSV DLTV DMNS DMPS DMPT DMRS DMST DNPS DNRS DNRT DNST DNSV DPRS DPRT DRST DRSV KLMS KLNP KLNR KLNS KLNT KLPS KLRS KLST KLSV KLTZ KMNS KMPS KMPT KMRS KNPR KNPS KNRS KNRT KNRZ KNST KNSZ KPRS KRST KRSZ LMNS LMPS LMRS LMST LMTZ LNPS LNPT LNRS LNST LNSV LPRS LPST LPTZ LRST LRSV LSTV MNPS MNPT MNRS MNST MPRS MPRT MPST MPSV MRST MRSV NPRS NPRT NPST NRST NRTZ NSTV NSTX PRST PRSV PSTZ RSTV RSTZ

Great! Do any of three of these four-letter words partition the 12-letter set with one word left over?

No, the best we can do is 10 of the letters, for example SKaLD, NiMPS, TZaRS. Thus, it requires 4 guesses to identify every word from this set of 12.

This strongly suggests (but does not rigorously prove) that it is impossible to always win the game when the first letter is C. It's probably feasible to prove this by expanding the word set through careful choices, but the reasoning gets more complex.

The same proof-method works for L with word set LOBES LODES LOGES LOKES LOMES LOPES LORES LOSES LOTES LOVES LOWES LOXES.

For first letter S or R there does not appear to be a winning strategy, but the 'hard' cases I've found are smaller and only prove that three guesses are necessary.

Conclusion: The game is always winnable when the first letter is not C, L, R, or S. It is probably not winnable for the other letters (with very high confidence for C and L.)
Tags: puzzles
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments