By Josh Feldman
On what I thought was a typical subway ride 18 months ago, my friend Chef asked me for a hand on a game he was stuck in. Never in a million years did I expect that this simple call for help would change my life.
Chef couldn’t solve that day’s New York Times Connections puzzle. In Connections, players are given 16 seemingly random words. In reality, each puzzle contains four groups of four words that are related. The connection might be that the words are synonyms, that the four words are all names of famous rappers, that they are all NHL nicknames, and so on. In each game, the player makes a guess of four words they think are connected. After each guess, the game tells you if your guess is correct or not. As each word appears in only one connection, all 16 words are used exactly once. You keep playing the game until you have found all four sets of connected words, or if you make four mistakes, whichever comes first.
I honestly can’t remember if I helped Chef solve that original Connections puzzle or not, but wow, did I get hooked on the game! I went to the archive and played all the previous puzzles, and without tooting my own horn, I thought I was a pretty darn good Connections player. So, when I heard there was an unofficial Connections National Championships, I had to enter and test myself against the best Connections solvers in the country.
At the Championships, it wasn’t enough to solve the Connections puzzle; speed mattered. The fastest person to solve the Connections puzzle was declared national champion. As usual, I massively overestimated my problem-solving skills, disgraced my family name, and came nowhere close to winning or even placing in the competition. I left the competition feeling humbled and embarrassed.
While leaving the contest venue, an angry mob started to form. It didn’t take long to figure out what was irking everyone: fellow competitors accused the winner of cheating. The mob seemed confused about how the winner had somehow solved the puzzle in under 10 seconds! How was this possible without something nefarious going on?
With a brouhaha brewing, I decided to stay for the award ceremony to see what would happen. When the winner accepted the first-place prize, she admitted to the angry crowd she won the competition by sheer luck: She had guessed the right answers. The winner explained that because the game let players know if they were one away from a right answer (hence the incorrect answer had three words that connected but the fourth did not), she used this fact to devise a guessing strategy that ultimately gave her the win.
I have no idea how, but a random person standing nearby recognized me and said, “Wait, aren’t you that puzzle guy? Is it really possible to guess your way to success? What is the probability that someone can guess their way to victory? Still bummed from my poor performance, I was not in the right mindset to help answer the question. But I bet my puzzle-solving friends could help out!
- Assuming a standard Connections puzzle of 16 randomly placed words, what is the probability, by sheer luck, that someone correctly matches all four groups of four words without making any mistakes?
- At the start of the Connections puzzle with 16 words remaining, if one made a random guess, what is the probability that the first four-word guess would be correct? What is the probability the first four-word guess would consist of three connected words along with one unrelated word? How does this probability change after one correctly finds the first connection, so that there are now 12 words left?
- Assuming the game does not give any hints about being one away from the right answer (though it will indicate if you matched four words correctly), what is the probability of someone randomly winning the game before making their fourth wrong guess?
- Assume the game tells you after your first guess that you were one away from the right answer. What is your probability of randomly correcting your error on your next guess? Assume that you know your first incorrect guess was not the one away set. Using this information, what is the probability that your next guess of four will be correct?
- How does the answer to part 4 change if there are only 12 words remaining in the puzzle? What about if there are now only eight words remaining in the puzzle?
Solutions may be emailed to puzzles@actuary.org.
In order to make the solver list, your solutions must be received by Dec. 1, 2025.
Party People Solutions
The well-known problem: “Prove that at a party of six people, there are either three mutual acquaintances or there are three mutual strangers” can be translated into Graph Theory, by representing each of the six people at the party as vertices of a graph, G. And for each pair of people (vertices), one gets a unique line between them which is an edge of G. We use the pair of vertices to denote their edge. This graph is the complete graph of order 6, denoted K6. If two people are acquainted, we color their edge blue but if they are strangers, we color their edge red.
The original problem now reads: Prove that if the edges of K6 are variously colored blue and red, then there is a blue triangle or a red triangle. I gave the proof in the prior issue of this column. You were asked to show that the “6” in K6 was the minimum.
Problem 1
Demonstrate that it is possible to color the edges of K5 (the complete graph on five vertices) blue and red such that no monochromatic triangle is formed. (A “monochromatic” triangle is one with edges of only one color.)
Solution: Take the graph of K5 shown in the prior column and color the perimeter edges: {{1,2}, {2,3}, {3,4}, {4,5}, {5,1}} one color, say blue, and the interior edges:{{1,3}, {3,5}, {5,2}, {2,4}, {4,1}} the other color, red. Observe that all edges of the graph are colored and there are no monochromatic triangles.
You were then challenged to go beyond the original problem.
Problem 2
Prove that if the edges of K6 are variously colored blue and red, then there are at least two monochromatic triangles. (The triangles could be the same or different colors.)
Each solution I received was different; so much for the perception that math problems have a single answer. However, all solvers assumed the existence of one monochromatic triangle to start with and proved the existence of a second monochromatic triangle by contradiction. The following is based on the solution by Clive Keatinge.
Solution: Assume triangle ABC is red and the remaining vertices are X, Y, and Z. There are three edges in each triangle ABC and XYZ. Since there are 15 total edges in K6, that leaves nine edges each of which runs across the gap from one triangle to the other: three edges from each of A, B, and C to each of X, Y, and Z. These same nine edges can also be viewed as three edges from each of X, Y, and Z to each of A, B, and C.
If two of the three edges going from X to triangle ABC are red, we get a second red triangle so at least two of the edges from X to ABC must be blue. The same holds for Y and Z. Thus, there are at least four blue edges from the pair of vertices X and Y to ABC. Thus, one of ABC’s vertices must get two blue edges, one from X and one from Y, which implies that edge XY must be red. Similarly, edges YZ and XZ must also be red. And so, XYZ is a second monochromatic triangle.
Solvers: Bob Conger, Clive Keatinge, Rui Guo, David Promislow, Jason Shaw, and Al Spooner