In the NYT Connections game, is there a guaranteed strategy to get the last two groups without knowing the theme?

Question

Recap of the rules

You're given a grid of 16 words that have to be split into 4 sets of 4, each with a defining theme. For example, in today's puzzle, four of the words are 'iguana', 'monitor', 'gecko', and 'chameleon', with the theme being 'lizards'.

On the first guess, you pick 4 of the 16 words. If these words form a set, they are removed from the pool and the game continues with 12 words. After a second correct guess, the pool is 8 words, and so on. If they don't form a set, the game counts this as a mistake. You can make 3 mistakes and continue playing, but a 4th mistake ends the game.

One more note about mistakes. If your guess contains 3 words from one set and 1 word from another, the game will still count it as a mistake, but will also give you the hint 'One away...'.

---

Puzzle

The question is this. Imagine you've made two correct guesses, and the board now contains 8 words that need to be divided into 2 sets, but you have no idea what the connections are. From the additional hint, and the fact that there's only two sets left, you can tell if your guesses are correct, one off, or two from each set. Is there a strategy which guarantees you win?

If not, how many guesses would be necessary? An absolute upper bound would be ${8 \choose 4}=70$ but that doesn't take into account the extra hints.

(To be upfront, I don't know the answer. Hoping the smarter people here can help.)

Answer 1

You can guarantee a correct pick within

6

guesses, so in at most

5

wrong guesses. From there it remains to enter the complementary 4 words to finish.

Let's call the eight words A, B, C, D, E, F, G, H. Start by grouping together A, B, and C, and testing 3 of the remaining 5 options for the last slot.

ABCD
ABCE
ABCF

If we're told "one away" all of these, the only possibility is that A, B, and C are in one set and D, E, and F are in the other. We can now guess ABCG and ABCH and guarantee getting a set in 5 guesses.

Otherwise, A, B, and C are split two-and-one. Let's call their majority theme X and the minority theme Y. We know which of D, E, and F are on X or on Y by whether we're told one-away or two-away for each.

• If D, E, and F are all Y's, we guess them all together with each of A, B, and C to win in 6 guesses.

• If they are two X's and a Y, guessing the two X's with every pair from A, B, C gets a set in 6 guesses.

• If there's one X and two Y's among D, E, and F, this is the interesting case. Let's say that D and E are the Y's. We want to find the remaining two Y's, one from among ABC, and one from GH. To this end, we guess:

   ADEG
   BDEG
  

  • If we get the same number for both sets, then A and B had the same theme, which means they're both X's and C is a Y. If we got both one-away, then G was the last Y, and otherwise it's H. So, we call in either CDEG or CDEH to win on our sixth and last guess.
  • Otherwise, one of the guesses did better, and means whichever of A and B it used was Y. If we haven't already won, switching its G to H will win on the sixth guess.

---

This solution is optimal in the worst case -- you can't guarantee a correct set in 5 or fewer guesses. This comes from a counting argument. You need to distinguish between $\binom{8}{4}/2 = 35$ possible splits, where we're dividing by two because submitting either set of words wins.

But there's only 31 possible sequences of answers we can get after four guesses, by which time we'd need to know the correct set or have already guessed it. This is because answer is either one-away or two-away, or is correct (0 away) but ends the sequences of guesses. And, there are only 31 such sequences of length 4 or less:

0
10
20
110
120
210
220
1110
1120
1210
1220
2110
2120
2210
2220
1111
1112
1121
1122
1211
1212
1221
1222
2111
2112
2121
2122
2211
2212
2221
2222

So, there's simply not enough information to distinguish between all 35 possibilities.