Theory is practical in practice
Whenever groups of pigeons gather, they instinctively establish a pecking order. For any pair of pigeons, one pigeon always pecks the other, driving it away from food or potential mates. The same pair of pigeons will always choose the same pecking order, even after years of separation, no matter what other pigeons are around. Surprisingly, the overall pecking order in a set of pigeons can contain cycles – for example, pigeon A pecks pigeon B, which pecks pigeon C, which pecks pigeon A. If A pecks B, we say that A is dominant and B is submissive.
(a) Prove that any set of pigeons can be listed in some order so that every pigeon pecks the following pigeon.
(b) Prove that any set of n pigeons can be listed in some order so that the number of pairs of pigeons where the dominant pigeon appears before the submissive pigeon is at least [some expression]
The concreteness of this problem was designed to help the students understand not only cases where graphs can be applied, but to make the problem easier to understand. I certainly thought that it would have this effect when I read it, and it seems much less intimidating than “Prove that every orientation of a complete graph has a Hamiltonian path,” which is what the question is “really” asking. My office hours indicated that it did not succeed in these goals. This was the question I got asked about much more than any other question, and most students seemed really confused by what the pigeons had to do with the problem, or even what the problem was asking. It’s interesting to me the amount of confusion which this caused. The students are still struggling with the basic concepts of graphs, so they had a lot of trouble thinking of the “right” way to abstract the problem, and then on top of that prove things about it.
I’m not sure what the best solution is for all this. Throughout much of the course, I’ve heard about how the material seems irrelevant to computer programming, and that the material is too abstract. Should we ignore complaints about the material, and give the students a heavy dose of abstraction, give the applications after students have done the homework (which might lead to frustration when students don’t know what theorems are “for”), or perhaps keep using problems like this. I don’t know, but it’s certainly interesting to think about.
(This is not to harp on the author of the question, who is a very good teacher. I think these issues are difficult, and there is no right answer. I just found the students’ response interesting and noteworthy.)