This puzzle can’t be solved by a computer program. No algorithm will get you the answer. But if you’re really into algorithms, there’s a good chance that you’ve seen the solution recently, although you may not recognize this puzzle as corresponding to that solution. And if you haven’t, there are enough clues here that you should be able to figure it out. Oh, and while the puzzle can’t be solved by a computer, you’ll probably need Wikipedia to help you work out the details.
A certain club has just over four dozen members. It’s not what you’d call a social club. Most of the members are friends with only a few others.
For example, Richard, Lincoln, Christine, Jack M., and Nikki are particularly lonely, as each has only two friends. And Paul is almost as lonely as the utterly friendless Sean and Neil, since he has just one friend, John L.
Friendship, I should mention, is a reciprocal relation. If I’m your friend, you’re my friend. Substitute any other reciprocal relation if it makes the problem clearer to you. I won’t mind. We're friends, after all.
Nobody else in the club has as many friends as Jay or Bill, who have eight each. Perhaps we should not be surprised that these two relatively gregarious members are friends with each other. And with Steve, who has seven friends.
You could say that Bob has six friends and Martin has five, but only if you count Vincent, and Vincent isn’t a member. Forget I mentioned Vincent. Vincent is right out.
It’s a cliquish club, this one. Some members are off in their own chilly little corner. If it weren’t for Andrew, all six of Peter, Paul, Lincoln , John L., Deval, and Dan would only have each other for friends. He’s their only link to all the rest. Well, all except Sean and Neil.
There are also what you might call strings of friends. Jerry and Jack M. are remotely connected, because Jerry is friends with Young Brian, who is friends with Gary, who is friends with John H., who is friends with Sam, who is friends with Jay, who is friends with Pat, who is friends with Mitch, who is friends with John K., who is friends with Tom, who is friends with Chris, who is friends with Jack M.—still with me?
A similar string connects Jan with Richard, running from Jan to Susana to Mary to James Richard to Mike to Bobby to Haley to Robert to Nathan and ultimately to Nathan’s friend Richard.
Friendships in the club are fairly permanent, but thin. No four people are all friends with one another, but there are many mutually-friendly threesomes, like Beverly, Nikki, and Nathan.
Some of these friendship triangles do overlap. The three-friend triangle of Butch, Old Brian, and Matt, for example, overlaps with the Old Brian-Matt-Dennis triangle, which shares Old Brian and Matt and which also overlaps with the Dennis-Jack D.-Mark triangle, which overlaps with the Mark-Scott-Terry triangle, which in turn overlaps with the Terry-Dave-Dennis triangle, which overlaps with…
Well, this is getting a little complicated, with these friendship triangles that one can be a member of many of, if you follow me. I mean, Earl is a member of five such triangles and Doctor John is a member of three, although Rick is a member of only one. But I think you have enough information now.
So if I tell you that Christine has exactly two friends, can you name them?
Here’s a bonus question: Where can you find a map of the club’s friendship structure? I’ll give you a hint: it’s in Figure 17 on page 15 of a book.