Solution: ‘The Bulldogs That Bulldogs Fight’

Our April Insights puzzle explored the magical concept of recursion, a self-referencing process that can create unending complexity from simple beginnings. Recursion, which commonly appears in mathematics, computer science and linguistics, seems especially head-spinning and brain-straining when identical elements are involved, as in our first problem.

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 University 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 color bulldogs do the brown bulldogs fight?
3. Which bulldogs fight the brown bulldogs?
4. What color bulldogs do the white bulldogs fight?

This puzzle can make your brain feel like the bruised and battered bulldogs so wonderfully rendered in Dan Page’s illustration. The best way to deal with recursion while minimizing brain strain is as follows:

1. Start as simply as possible.
2. Build on the recursion one element at a time, looking for a pattern.
3. Once you find the pattern, let the pattern do the work.

Let’s apply these techniques to the fighting bulldogs. The simplest possible sentence you can start with by removing the center-embedding is: Bulldogs fight.

Who do they fight? This is not specified — fight is an intransitive verb here, a verb without an object. So the meaning conveyed here is that these bulldogs fight generally or among themselves.

Following our color code, these were the red bulldogs, so the red bulldogs fight generally.

Now let’s add the center-embedding of the second set of bulldogs: Bulldogs [bulldogs fight] fight. The simplest sentence, adding in the colors, becomes: The (red) bulldogs [that the (brown) bulldogs fight] fight.

The verb fight is transitive here and does have an object. The brown bulldogs fight the red bulldogs specifically. The red bulldogs, as far as we know, don’t change their character. They continue to fight generally.

Okay, let’s add the third set: Bulldogs [bulldogs {bulldogs fight} fight] fight. With the colors, we have this sentence: The (red) bulldogs [that the (brown) bulldogs {that the (white) bulldogs fight} fight] fight.

The verb fight is again transitive here, and its object is the brown bulldogs. The white bulldogs fight the brown bulldogs specifically. Again, the description of the first two sets of bulldogs is not changed in any way.

The answers to the questions are:

1. The red bulldogs fight generally.
2. The brown bulldogs fight the red bulldogs.
3. The white bulldogs fight the brown bulldogs.
4. The white bulldogs fight the brown bulldogs.

(You may object that since the brown bulldogs fight the red bulldogs, the red bulldogs must fight them too. But this inference is not necessarily true: The red bulldogs might just keep fighting generally or among themselves, without paying any attention to the brown bulldogs, for all we know.)

As you can see, we arrive at this pattern: Group one fights generally, group two fights group one, group three fights group two, and so on. Thus, we can construct a recursive center-embedded sentence consisting of any number of bulldog groups and very easily determine who fights whom. A hypothetical group four would fight group three, group five would fight group four, and so on. Finding the pattern enables you to correctly answer the questions by offloading the work to the pattern or algorithm, without having to tax your brain’s short-term memory.

This is similar to how mathematicians deal with higher dimensions. No one can visualize the fourth dimension and beyond in the way we can visualize the first three. Not even Einstein could visualize higher dimensions. You have to find patterns or algorithms that generalize to the higher dimensions. Then you can accurately answer questions about them.

Several readers got the right answers, including boymeetswool, plouf, Nqabutho and Danielle Schaper. I enjoyed boymeetswool’s diagram and explanation of the sentence tree — it is perfectly correct. Danielle Schaper also produced some very nice diagrams based on the idea that subsets of bulldogs of each color are being referred to. This is one way to interpret the sentence, but it involves an additional assumption that is not specified explicitly. The most parsimonious approach is to assume that all the bulldogs of a given color do the same thing.

Puzzle 2: The Lying Legislators

Our second problem is briefly summarized below. For the full description, see the original puzzle column.

On a faraway planet with perfectly logical beings, there was a legislative assembly consisting of 100 members who met every day. Some among them were pathological liars, or “pathos.” A patho was perceived as having a long nose by everybody else, including other pathos. However, a patho was completely unaware that he or she had a long nose and couldn’t hear about it from anyone because of a taboo that prevented others from pointing out or saying anything about anybody else’s long nose. Any patho who logically inferred that he or she was a patho was compelled to resign before the end of the business day. One day an alien leader not bound by the taboo addressed the assembly and said, “I perceive that at least one of you has a long nose.” Many days later, about half of the legislators resigned en masse.

Question 1 (parallel universe situation): What could have caused this strange pattern of resignations?

Let us apply the recursion-solving rules stated above and start small. Suppose that there was only one person in the assembly who had a long nose. Then the alien leader’s statement would allow that one person to infer that he or she was the one with the long nose and cause him or her to resign. Let’s say this happens on day one (more on this choice below).

If there were two people with long noses (let’s say a male, A, and a female, B), each of them would see one person with a long nose. Legislator A infers that B would see nobody with a long nose if he, A, doesn’t have one, or she would see one person if he, A, does. In the first case, B would be compelled to resign on day one. But that wouldn’t happen because she does see A’s long nose, and by an identical reasoning process, she waits to see if he resigns on day one, which would mean that she, B, did not have a long nose. Thus, neither A nor B resign on day one. On day two, both A and B realize that they have long noses and resign.

If there were three people with long noses, each would see two pathos, and they would have to wait two days to see if both resign on day two, which would mean they themselves were not pathos. When that doesn’t happen, then they would all be forced to resign on day three.

The pattern is already becoming clear. If n people in the assembly are pathos, then:

• The mass resignations will happen on day n.
• Everyone’s resignation day is one more than the number of pathos they see. Pathos see n-1 pathos, so their resignation day is n, while all nonpathos see n pathos, so their resignation day (if others don’t resign first) is n+1.

All of the pathos are hoping that the mass resignations happen on day n–1, but when that doesn’t happen, they realize they are pathos themselves and resign next day. Nonpathos see n people with long noses, and they are hoping that the resignations happen on day n, which indeed happens, confirming that they are not pathos.

So if about half of the legislators in the parallel universe resigned, then about half of them must have been pathos to begin with.

We know that the pathos’ days as legislators are numbered, but do we number them starting from zero or one? This point came up in the long discussion between plouf and Sunil Nandella.

We decided above that we should call the day the lone patho resigns “day one.” If we are thinking in terms of days after the alien leader’s visit, then the alien leader must have addressed the assembly after the day’s work was done (say, at an after-dinner speech), so a lone patho would have to resign the next day. On the other hand, if the alien leader addressed the assembly in a morning gathering, then a lone patho would be compelled to resign the same day, which would be day zero.  This would change the number of days by 1. This is the basis of the very common off-by-one-error (OBOE or OB1) that can cause bugs in computer software. Whether you want to use the index 1 or 0 for the first element of an array of numbers or first step of a recursion is an arbitrary choice that has to be made initially and applied consistently. Some computer languages force you to use one or the other (usually 0), whereas others allow you to choose, using a declaration such as “Option Base 0” or “Option Base 1”). The first option is commonly used by software engineers; the second is the one that all of us use naturally when counting, and that’s what we used here.

The above parallel universe scenario can take place only if all the legislators meet all the others every day and no one is ever absent. The Quanta universe scenario (questions 2 through 6) considers what happens in a messier situation where people may be absent temporarily (lost at sea and later found), absent indefinitely (slip into a coma) or where a nonpatho can change into a patho. Specifically, the puzzle stated that:

a.) On the 35th day, a nonpatho changes into a patho irreversibly.
b.) On the 43rd day, three legislators, including one patho, were lost at sea. On the 46th evening, one of the pathos was found and rejoined the assembly the next day.
c.) On the 45th day, a legislator who was a patho slipped into a coma.
d.) On the 49th day, there was a mass resignation of a large number of legislators.

Before we answer the remaining questions, let us consider how the absence of a patho from the assembly (as happens in items b and c) should be handled: Should the remaining pathos take the absence into account and resign one day earlier, or should they stick to the original plan? Let’s examine a simple situation.

Assume that there are three pathos in the group. After day one, one of them goes missing, so that as above, only a male A and female B remain. Should they resign on day two now, because there are only two of them actually present (modified plan), or should they follow the original plan and resign on day three?

On day two, legislator A will reason as follows: “Either I have a long nose, or I do not. If I do not, then the only long-nosed person B would have seen is C, and she can assume that the alien leader was referring to C as the one with the long nose. So there is nothing to compel her to resign today. If I do have a long nose, then B will reason in the same way about me that I am reasoning about her. So I cannot be certain that I don’t have a long nose, and neither can she.” Hence neither A nor B can be fully certain that they are pathos, and so neither can logically resign on day two. The modified plan does not work.

On the other hand, everything works if they adhere to the original plan and wait until day three, imagining that C is watching everything from some virtual place and would have followed the plan too if he were present (even if he is actually dead, for all they know). All three pathos had originally seen two people with long noses, and nobody resigned on day two. So they must resign on day three.

What about the addition of a newly created patho, as happens in item a above? In this case, from the point of view of the person who has become a patho, nothing has changed because she never knew whether she was a patho anyway: She still sees the original number of n pathos. The pathos now also see n pathos, and the nonpathos see n+1. This calls for everyone except the affected person to modify their resignation plan to one day later than it originally was. The pathos’ resignation day is now n+1, and the nonpathos’ is n+2. You can see that this situation is indistinguishable from having n+1 pathos from the beginning, provided that all the legislators except the changed one know about the change, which is true in this instance.

So the principle for absences is: Stick to the original plan, and the resignation day remains the same. For additions such as the universally observable change (except to the affected person) of a nonpatho into a patho, add 1 to the resignation day.

With this in mind, let’s answer the remaining questions:

2. Given all the events described, how many pathos were in the assembly originally and how many resigned on the 49th day?

There were 48 pathos originally, and 48 resigned on the 49th day (with the base day understood as day one). The 48 pathos would have all resigned on day 48, but the addition of the new patho in plain sight to everyone except the affected legislator forced them to change the resignation day to day 49. The comatose person was the missing 49th patho. (If the base day was understood as day zero, add 1 to all the answers.)

3. Was the originally truthful legislator who became a patho on the 35th day among those who resigned?

Yes. He had always seen 48 other pathos, so his resignation day was always 49.

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?

Yes. When he returned, he asked for the names of the people who had resigned. He saw the name of the legislator who had changed to a patho on the 35th day. He went down the list, desperately scouring it for a name that he knew to have been that of a nonpatho as of the 44th day. He didn’t find any. He resigned.

5. What would have happened if the legislator who had been lost at sea had been found a day later?

Nothing. All the resignations would still have happened on the 49th day. Absences do not affect the set plan.

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.

This question holds the key to this puzzle. This is what is known as a “common knowledge” problem. Common knowledge, in logic, is defined as the knowledge of some truth, p, in a group, such that everybody in the group knows p,  they all know they know p, they all know that they all know that they know p, and so on ad infinitum. It is this common, infinitely recursive, web of knowledge that the alien leader’s words impart to the legislators. This web of recursive knowledge remains intact in the parallel universe because the legislators are present every day and are able to carry the recursive reasoning forward one step at a time. Thus, all the pathos are able to reach the same conclusion on the same day. When absences and additions are present, the original plan may need to be modified, and this can be done logically but only among the original legislators who were present at the declaration and therefore knew that everyone knew what they knew. The alien leader’s declaration also gives a common base to count the days starting on the day the declaration was made and the web of common knowledge was constructed. As the days pass, this web is recursively unraveled from the outside in, until resignation day arrives and everyone can logically infer their true nature.

The Quanta prize for this puzzle goes to plouf, who answered both puzzles correctly. Plouf’s answers for the second puzzle counted the base day as zero, so they are 1 off from the ones given here, but they are correct for the assumed base day.

I hope you enjoyed this brain twister. If you need some time to untwist, you have a few weeks before we return next month with more Insights.