The Bulldogs That Bulldogs Fight

Recursion is one of the most fascinating, magical concepts in computer science and mathematics. A programmer’s subroutine can call itself, which can call itself again and again in an infinite loop. A math function can be defined in terms of itself. Informally, recursion involves having an entity or action that refers to, acts on or is based on a copy or type of itself. Like a set of Russian dolls, or self-reflecting mirrors, this process can theoretically go on forever.

For example, the factorial of a number n can be defined as n times the factorial of the previous number: n! = n (n − 1)! As in the centuries-old fable of an Earth-supporting tortoise that spawned the popular expression “turtles all the way down,” this process must have a base to stand on. For the factorial function, we can define 0! as 1 to create an infinite series of factorials starting literally from nothing. And this kind of process is not confined to just the abstract world of numbers. A tantalizing quantum finding seems to suggest that the universe itself is built from recursive elements.

Language, too, has a recursive structure in which a syntactic category such as a sentence can contain other sentence clauses that in turn can contain clauses themselves, and so on. This recursive structure allows us to generate sentences of potentially infinite length. We are introduced to this early in life in nursery rhymes such as “This is the dog that worried the cat that killed the rat that ate the malt…” and in childhood games like “She thinks that I think that she thinks that I’ll do that. So I’ll do this instead.” As you can see, it’s hard to wrap your head around such recursive sentences when they contain identical elements. And that brings us to our first puzzle, which involves a linguistic whodunit.

Puzzle 1: The Fighting Bulldogs

One type of recursive sentence uses a grammatical structure called “center-embedding.” An example is the sentence, “The dog the man the maid married owned died.” You can make this somewhat easier to understand by inserting the linking words: “The dog that the man whom the maid married owned died.” Most people can understand who did what here, but it’s already getting tough. Now consider the Yale football cheer “Bulldogs bulldogs bulldogs fight fight fight.” The Rutgers cognitive philosopher Jerry Fodor once pointed out that this is a grammatically correct triple center-embedded sentence. Your challenge is to try to understand how this cheer works as a real sentence. To make it more specific, imagine that the first set of bulldogs is red, the second brown and the third white. Try to answer the following questions:

1.   Whom do the red bulldogs fight?
2.   What kind of bulldogs do the brown bulldogs fight?
3.   Which bulldogs fight the brown bulldogs?
4.   What kind of bulldogs do the white bulldogs fight?

Now imagine a sentence with four groups of fighting bulldogs … Just kidding! Instead, let’s go on to the next puzzle, which is equally head-spinning.

Puzzle 2: The Lying Legislators

This is a modified version of a famous logic puzzle that has existed for decades in different forms:

Long, long, ago in a galaxy far, far, away, there was a planet called Lyon that had a legislative assembly of 100 Lyers, who met every day. They were conscientious and never absent except in very rare circumstances. Unfortunately, similar to political bodies on Earth, a significant proportion of these legislators, about half, were prone to lying pathologically. Unlike humans, though, the Lyers had a keen sixth sense that allowed them to detect pathological liars (also known as “pathos” for short). This ability was based on intangible factors that caused Lyers to actually perceive pathos as having long noses, a dead giveaway. (If you think that such perception cannot occur, check out the McGurk effect, in which what you see makes you hear things differently.) Of course, the pathos who had this affliction didn’t really have long noses, so they were unaware of their own pathology. Also unlike humans, the Lyers had impeccable mathematical logic: Given any situation, no matter how complex, all of them could analyze it perfectly and make the correct inferences. They also had a rigid legislative code. Any legislator who logically inferred or came to know that he or she was a patho would be psychologically compelled to resign by the end of that very day, and invariably did so. On account of this harsh consequence, it became an unbreakable taboo on Lyon to ever talk about anybody’s perceived long nose in any way. Talk about unspoken rules (or rather, don’t talk).

One day, a leader from a planet named Truon visited the Lyon assembly. The residents of Truon shared some of the perceptive abilities of the Lyers, but they had no inhibitions about breaking taboos. The Truon leader looked around the assembly and said, “I perceive that at least one of you has a long nose. That would never be acceptable on Truon.”

Several days passed. The assembly continued to meet every day as before, and all the members saw one another every day. In the classical version of this puzzle, which took place in a parallel universe with beings that were exactly like those described above, about half the legislators suddenly tendered their resignation en masse on one particular day. There were no resignations before that day and none after. Let’s pause to answer the first question:

1.   What could possibly have caused such a strange pattern of resignations in this parallel universe?

In our Quanta universe, things happened a little differently. As you might expect, there were several complications. Here, the uninterrupted and uneventful daily meetings of all the legislators could not take place because of unforeseen happenings. For instance, on the 35th day after the Truon leader’s visit, a legislator who previously had not had a long nose, suddenly developed one and became a patho, possibly because of long-standing political pressure. This kind of change was known to be a relatively rare event on Lyon, but it did happen now and then, and the change was known to be irreversible — once a patho, always a patho. A few days later, on the 43rd day, three of the legislators from Lyon were lost at sea. Only one of them was known to have been a patho. On the evening of the 45th day, one of the legislators, also a patho, slipped into a coma and couldn’t attend the assembly for several days. The next evening after assembly hours (on the 46th day), the legislators were informed by email that one of the lost legislators had been found. He turned out to be the patho and came back to the assembly the next morning (on the 47th day), completely briefed about what had happened in his absence. He was a little shaken, but his logical faculties were intact.

Disruptive as these events were, they paled in comparison to what happened a couple of days later. The 49th day after the Truon leader’s visit started quietly enough, with the one legislator still in a coma. However, by the end of the day, the news cycle was dominated by the unprecedented mass resignation of a large number of legislators, similar to the one described above for the parallel universe. Now answer the following questions:

2.   Given all the events described, how many pathos were in the assembly originally and how many resigned on the 49th day?
3.   Was the originally truthful legislator who became a patho on the 35th day among those who resigned?
4.   The legislator who had slipped into a coma recovered and returned to the assembly on the 50th day. He was briefed about everything that had happened. Did he resign?
5.   What would have happened if the legislator who had been lost at sea had been found a day later?
6.   Why was the Truon leader’s visit necessary for the mass resignations to occur? After all, all of the legislators always knew that at least one of them had a long nose.

Enjoy the brain vertigo and happy puzzling!

Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt or one of the two new Quanta books, Alice and Bob Meet the Wall of Fire or The Prime Number Conspiracy (winner’s choice). And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION.” (It will not appear online, so solutions to the puzzle above should be submitted separately.)

Note that we may hold comments for the first day or two to allow for independent contributions by readers.

Update: The solution has been published here.