You are currently browsing the category archive for the ‘Problem Corner’ category.
I thought I would share with our chess-loving readers the following interesting (and somewhat well-known) mathematical chess paradox , apparently proving that , and the accompanying explanation offered by Prof. Christian Hesse, University of Stuttgart (Germany). It shows a curious connection between the well-known Cassini’s identity (related to Fibonacci numbers) and the chessboard ( being a Fibonacci number!). The connection can be exploited further to come up with similar paradoxes wherein any -square can always be “rerranged” to form a -rectangle such that the difference between their areas is either or . Of course, for the curious reader there are plenty of such dissection problems listed in Prof David Eppstein’s Dissection page.
The following “polynomial-logarithmic” algebraic identity that one encounters on many occasions turns out to have a rather useful set of applications!
POLYNOMIAL-LOGARITHMIC IDENTITY: If is a polynomial of degree with roots , then .
PROOF: This one is left as a simple exercise. (Hint: Logarithms!)
A nice application of the above identity is found in one of the exercises from the chapter titled Analysis (p120) in Proofs from the Book by Aigner, Ziegler and Hofmann.
EXERCISE: Let be a non-constant polynomial with only real zeros. Show that for all .
SOLUTION: If is a zero of , then the right hand side of the above inequality equals zero, and we are done. So, suppose is not a root of . Then, differentiating the above identity w.r.t. , we obtain , and we are done.
It turns out that the above identity can also used to prove the well-known Gauss-Lucas theorem.
GAUSS-LUCAS: If is a non-constant polynomial, then the zeros of lie in the convex hull of the roots of .
PROOF: See this.
HISTORY: The well-known Russian author V.V. Prasolov in his book Polynomials offers a brief and interesting historical background of the theorem, in which he points out that Gauss’ original proof (in 1836) of a variant of the theorem was motivated by physical concepts, and it was only in 1874 that F. Lucas, a French Engineer, formulated and proved the above theorem. (Note that the Gauss-Lucas theorem can also be thought of as some sort of a generalization (at least, in spirit!) of Rolle’s theorem.)
Even though I knew the aforesaid identity before, it was once again brought to my attention through a nice (and elementary) article, titled On an Algebraic Identity by Roberto Bosch Cabrera, available at Mathematical Reflections. In particular, Cabrera offers a simple solution, based on an application of the given identity, to the following problem (posed in the 2006 4th issue of Mathematical Reflections), the solution to which had either escaped regular problem solvers or required knowledge of some tedious (albeit elementary) technique.
PROBLEM: Evaluate the sum . (proposed by Dorin Andrica and Mihai Piticari.)
SOLUTION: (Read Cabrera’s article.)
There is yet another problem which has a nice solution based again on our beloved identity!
PROBLEM: (Putnam A3/2005) Let be a polynomial of degree , all of whose zeros have absolute value 1 in the complex plane. Put . Show that all zeros of have absolute value 1.
SOLUTION: (Again, read Cabrera’s article.)
“In mathematics you don’t understand things. You just get used to them.”
– John von Neumann
I had been wanting to write on this topic – no, I am not referring to the above quote by von Neumann – for quite some time but I wasn’t too sure if doing so would contribute anything “useful” to the ongoing discussion on the pedagogical roles of concrete and abstract examples in mathematics, a discussion that’s been going on on various blogs for some time now. In part coaxed by Todd, let me share some of my own observations for whatever they are worth.
First, some background. A few months ago, Scientific American published an article titled In Abstract: Avoid Concrete Example When Teaching Math (by Nikhil Swaminathan). Some excerpts from that article can be read below:
New research published in Science suggests that attempts by math teachers to make the subject easier to grasp by providing such practical examples may actually have made it tougher to learn.
For their study, Kaminski and her colleagues taught 80 undergraduate students—split into four 20-person groups—a new mathematical system (based on several simple arithmetic concepts) in different ways.
One group was taught using generic symbols such as circles and diamonds. The other groups were taught using practical scenarios such as combining liquids in measuring cups.
The researchers then tested their grasp of the concept by seeing how well they could apply it to an unrelated situation, in this case a children’s game. The results: students who learned using symbols on average scored 80 percent; the others scored between 40 and 50 percent, according to Kaminski.
One may read the entire article online to learn a bit more about the study done. Let me add that I do agree with the overall conclusion of the study cited: in mathematics concrete examples (in contradistinction to abstract ones) more often than not obfuscate the underlying concepts behind those examples, thus hindering “real” or complete understanding of those concepts. However, I also feel that such a claim must be somewhat qualified because there is more to it than meets the eye.
Sometimes the line between abstract examples and concrete ones can be quite blurry. What is more, some concrete examples may even be more abstract than other concrete ones. In this post, I will assume (and hope others do too) that the distinction between an abstract example and a concrete one (that I have chosen for this post) is sharp enough for our discussion. Of course, my aim is not to highlight such a distinction but to emphasize the importance of both abstract and concrete examples in mathematical education, for I firmly believe that a “concrete” understanding of concepts isn’t necessarily subsumed under an “abstract” one, even though a concrete example may just be a special case of a more general and abstract one. What is more, and this may sound surprising, abstract examples may sometimes not reveal certain useful principles which, on the other hand, may be clearly revealed by concrete ones!
Let me illustrate what I wrote above by discussing a somewhat well-known problem and its two related solutions, one of which employs an abstract approach and the other a concrete one, if you will. Some time ago, Isabel at God Plays Dice pointed to an online article titled An Intuitive Explanation of Bayesian Reasoning by Eliezer Yudkowsky, and I borrow the problem I am about to discuss in this post from that article.
PROBLEM: 1% of women at age forty who participate in routine screening have breast cancer. 80% of women with breast cancer will get positive mammographies. 9.6% of women without breast cancer will also get positive mammographies. A woman in this age group had a positive mammography in a routine screening. What is the probability that she actually has breast cancer?
How may one proceed to solve this problem? Well, first, let us look at an “abstract” solution.
“ABSTRACT” SOLUTION: Here we employ the machinery of set-theoretic probability theory to arrive at our answer. We first note that what we really want to compute is the probability of a woman having breast cancer given that she has tested positive. That is, we want to compute the conditional probability P(A/B), where event A corresponds to that of a woman having breast cancer and event B corresponds to that of a woman testing positive for breast cancer. Now, from Bayes’ theorem, we have
Also, we note that and . Plugging these values into the above formula immediately yields P(A/B) = 7.76%. And, we are done.
A couple of observations.
1. It is not hard to observe that the derivation of Bayes’ formula follows from the definition of conditional probability, viz. P(A/B) = P(AB)/P(B), where P(B) > 0, and the usual set-theoretic rules involving the union and intersection of sets (events). And, this derivation can be carried out through sheer manipulation of symbols under those rules. By that I mean, if a student knows enough set theory as well as the “laws” of set-theoretic probability theory, then the derivation of Bayes’ theorem makes absolutely no (or, almost no) use of the “intuitive” faculty of a student.
2. The abstract method presented above also subsumes the concrete method, as we shall see shortly. What is more, Bayes’ formula can be generalized even further. This means that once we have this particularly useful “abstract” tool at our disposal, we can solve any number of similar problems by repeatedly using this tool in concrete (and even abstract) cases. In addition, Bayes’ theorem can also be thought of as a “black box” to which we apply certain inputs in order to get our output. This should not surprise us, for in mathematics the use of theorems as black boxes is a common one.
Now, the above two observations may lead one to believe that indeed there is almost no need to find a “concrete” solution to the above problem. After all, the abstract case takes care of the concrete cases completely.
However, let us see if we can come up with a concrete (that is, a far less abstract) solution and examine it more closely to see if we can extract some useful ideas/techniques from the same.
“CONCRETE” SOLUTION: Suppose we choose a random sample of 100,000 women of age forty. (We choose that figure for reasons that will be clear soon.) Then, we have two groups of women.
1st group: 1,000 (1%) women who have breast cancer.
2nd group: 99,000 (99%) women who don’t have breast cancer.
Now, in the 1st group, 800 (80% of 1,000) women will test positive, and, in the 2nd group, 9,504 (9.6% of 99,000) women will test positive. So, it is clear that if a woman tests positive, then the probability that she belongs to the 1st group (that is, she really has cancer) is 800/(800+9504) = 7.76 %. And, we are done.
Let me quickly point out a very important advantage the above solution has over the abstract one we saw earlier.
Indeed, we finally “see” what’s really going on. That is, from an intuitive standpoint, we observe in the above solution that there is a “tree structure” involved in our reasoning. The sample of 1,00,000 women bifurcates into two distinct samples, one of which has 1,000 women who have breast cancer and the other that has 99,000 women who don’t. Next, we observe that each of these two samples in turn bifurcates into two samples, one of which comprises women who test positive and the other that comprises women who don’t. This clearly reveals to the student the “tree structure” in the above reasoning. This makes the concrete solution much more appealing and “satisfying” to the average student. In fact, the generalization we talked about earlier in regard to Bayes’ theorem can even be carried out in this particular method: we will only need to increase the depth and/or breadth of our “tree” by extending more nodes from existing ones!
Moreover, one may recall that the use of such “trees” in reasoning is quite common in mathematics. For instance, the two most basic rules of Combinatorial Principles, viz. the Rule of Sum and the Rule of Product are proved using such “trees”. So, this is one instance in which a concrete solution reveals much more clearly a quite fundamental principle/technique (use of “trees” in reasoning) in mathematics that isn’t clearly revealed at all in the abstract solution we examined earlier.
In other words, much thought needs to be put in deciding if abstract examples should necessarily be “favored” over concrete ones in mathematics education. From a pedagogical standpoint, sometimes concrete examples are simply much better than abstract ones!
Let be a simple closed curve in the plane, and let be any point strictly in the region interior to . Show there are two points on whose midpoint is .
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 9, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.
This week’s problem is offered more in the spirit of a light and pleasant diversion — I don’t think you’ll need any deep insight to solve it. (A little persistence may come in handy though!)
Define a triomino to be a figure congruent to the union of three of the four unit squares in a square. For which pairs of positive integers is an rectangle tileable by triominoes?
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 3, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response. Enjoy!
We got some very good response to our last week’s problem from several of our “regular” problem-solvers as well as several others who are “new”. There were solutions that were more “algebraic” than others, some that had a more “trigonometric” flavor to them and some that had a combination of both. All the solutions we received this time were correct and they all deserve to be published, but for the sake of brevity I will post just one.
Solution to POW-5: (due to Animesh Datta, Univ of New Mexico)
Note that the given integral may be written as
Now, we use the substitution , which transforms the integral into
Finally, we use one last (trigonometric) substitution , which transforms the integral into , which evaluates to , which equals . And this is our final answer!
Watch out for the next POW that will be posted by Todd!
Source: I had mentioned earlier that Carl Lira had brought this integral to our attention, and he in turn had found it in the MIT Integration Bee archives. This one was from the year 1994.
Trivia: Four out of the six people who sent correct solutions are either Indians or of Indian origin! Coincidence? :)
Time for our next problem in the POW series! Earlier, Todd and I deliberated for a bit on whether we should pose a “hard” Ramanujan identity (involving an integral and Gamma function) as the next POW, but decided against doing it. Perhaps, we may do so some time in the future.
Okay, the following integral was brought to our attention by Carl Lira, and for the time being I won’t reveal the actual source of the problem.
It is “hard” or “easy” depending on how you look at it!
Please send your solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, June 26, 11:59pm (UTC); do not submit solutions in Comments. Everyone with a correct solution gets entered in our Hall of Fame! We look forward to your response.
The solutions are in! I thought last week’s problem might have been a little more challenging than problems of previous weeks — the identity is just gorgeous, but not at all obvious (I don’t think!) without some correspondingly gorgeous combinatorial insight. Luckily, some of our readers came up with the goods, and their solutions provide a forum for discussing a beautiful circle of ideas, involving the inter-related combinatorics of trees and endofunctions.
I can’t decide which of the solutions we received I like best. They all bear a certain familial resemblance, but each has its own distinct personality. I’ll give two representative examples, and append some comments at the end. Both proofs are conceptual “bijective” proofs, in which the two sides of the identity represent two different ways of counting essentially the same combinatorial objects. And both rely on a famous theorem of Cayley, on the number of tree structures or spanning trees on distinct labeled nodes (maybe this would be sufficient hint, if you still want to think about it some more by yourself!). Here, I’ll add a little spoiler space:
1. (Solution by David Eppstein) As is well known (see, e.g., http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence), the number of different spanning trees on a set of n labeled nodes is . Equivalently, the number of ways of choosing a spanning tree together with a specification of a single vertex is , and the number of ways of choosing a spanning tree together with a specification of two vertices and (possibly equal to each other) is . So that’s the right hand side of the identity.
Now suppose you are given a tree , and two nodes and . If and are different, let be the first edge on the path in from to ; cutting at that edge produces two disjoint subtrees, one containing one marked node and the other containing two (possibly equal) marked nodes, namely and the first node on the path after . Conversely, from this information (two trees, one containing a marked node and the other containing two marks on nodes and ) we can put together simply by connecting the two trees by an edge . If is the number of nodes in the tree containing , the number of ways we can choose two disjoint marked subtrees in this way is
almost the same as the left hand side of the identity, but missing the final term in the sum.
The final term comes from the case when the marked nodes and of tree T coincide. The number of ways this can happen is the same as the number of ways we can pick a single marked node of a tree, that is, , which is the same as the final term in the left hand sum.
Thus, the left side counts (partitions of n vertices into two disjoint subtrees, one subtree having one marked node and one subtree having two possibly-equal marks) + (-vertex trees with one marked node); the right side counts (-vertex trees with two possibly-equal marks), and we have demonstrated a combinatorial equivalence between these two sets.
2. (Solution by Sune Jakobsen) Consider all -tuples , where each term is from the set Since each of the terms can take values, there are such tuples.
Given a -tuple, , construct a graph as follows. Begin with a vertex labeled . Then, for each vertex labeled in the graph, if , add a new vertex labeled , and connect and by an edge. This graph must be a tree since each only takes one value and doesn’t exist.
Using this graph, I will count the number of -tuples in another way. Let be the number of vertices in such a tree graph. The vertices may be chosen in ways, since the vertex labeled is already one of them. Given the vertices, the tree can be formed in ways, by Cayley’s theorem (see http://www.research.att.com/~njas/sequences/A000272). Given the tree graph, the values of the ‘s, for each vertex labeled in the graph, can be chosen in one and only one way (namely, is the label of the first vertex after along the unique path from vertex to vertex ). The remaining components of the tuple are not among the vertex labels in the graph, so each takes on one of possible values, giving possibilities for the remaining components. Therefore the number of -tuples must be:
1. I found this curious identity in HAKMEM, item 118. For those who don’t know, HAKMEM is a kind of archive of cool mathematical observations made by some of the original MIT computer “hackers” from the 60′s and 70′s, including Bill Gosper and Rick Schroeppel. This particular item is credited to Schroeppel, but the accompanying text is a bit cryptic in my view:
Differentiate to get . One observes the curious identity
Maybe it was just their style to record a lot of their observations in such terse, compact form, but it annoys me that these guys hide their light under a bushel in this way. No motivation whatsoever, even though (I’d be willing to bet) these guys knew about the connection to trees — they’re computer scientists, after all!
Personally, I find it easier to get from to by other means than through their intermediate identity. I feel sure that just about anyone who has played around with enumerative combinatorics, and with the combinatorics of trees in particular, could figure this one out.
For, as David pointed out in his solution, is the number of spanning trees on the set  equipped with a distinguished vertex; I’ll call that vertex the root, and such structures rooted trees. (Incidentally, a spanning tree is by definition an acyclic subgraph of the complete graph on the set , such that any two elements of the set are connected or spanned by a path in the subgraph. The theorem of Cayley mentioned above is that there are such spanning trees.) Thus,
Somehow I find this explanation much easier to understand than the machinations hinted at in HAKMEM 118.
2. David’s proof was actually the one I myself had in mind. I can’t say what inspired David, but I myself was inspired by an earlier reading of a beautiful (and in many respects revolutionary-for-its-time) article, on a systematic functorial approach to enumerative combinatorics:
- André Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1-82.
In particular, I am very fond of the proof Joyal gives for Cayley’s theorem (which he credits to Gilbert Labelle), and this proof is in a line of thought which also leads to David’s solution. I’d like to present that proof now.
Labelle’s proof of Cayley’s theorem:
The expression probably makes most people think of the number of functions :   from an -element set to itself. The art of combinatorics lies in drawing appropriate pictures, so draw a picture (a graph) of such a function by drawing a directed edge from to whenever (cf. Sune’s solution). Starting from any vertex and iterating enough times, you always eventually land in a cycle where points get revisited periodically, infinitely often. Let’s call those points periodic points; the function acts as a permutation on periodic points. Now, for each periodic point , consider the union of directed paths which end at without hitting any other periodic points. This union forms a subgraph which is a tree, rooted at (again, cf. Sune’s solution). The entire set  is thereby partitioned into (equivalence) classes (the underlying vertex sets of the trees ), and the structure of a function   thus determines the following data:
- An equivalence relation on ;
- A rooted tree structure on each equivalence class;
- A permutation structure on the set of equivalence classes (each tagged by the periodic point at the root).
Conversely, these three data determine a function, and the correspondence is bijective.
- Remark: It’s not necessary to the proof, but let me add that by basic principles of generatingfunctionology, if is the egf for permutations [namely, ], and if is the egf for rooted trees, then is the egf for structures given by such triplets of data. Thus, by the bijective correspondence, we have
On the other hand, consider a tree structure on points, and suppose we also specify an ordered pair of such points , possibly equal. There is a unique path from to in , which I’ll call the spine (of the “bipointed tree”); call the points along that path, including and , vertebrae. Now, for each point , there is a unique shortest path from to the spine, terminating at a vertebra . The union of all such paths which terminate at a vertebra again forms a subtree rooted at . Again, the set of points is partitioned by the (underlying vertex sets of) , and the structure of a bipointed tree on an -element set  is thus encoded [in bijective fashion] by
- An equivalence relation on ;
- A rooted tree structure on each equivalence class;
- A spine structure (that is, a linear ordering) on the roots which tag the equivalence classes.
However, the number of linear orderings on an -element set, , is the same as the number of permutations on that set. We conclude that the number of bipointed tree structures on an -element set is the same as the number of endofunctions, . And, voilà! the number of tree structures on the -element set must therefore be .
Note: regular solver Philipp Lampe, who submitted a solution similar to David’s, pointed out that there are no fewer than four proofs of Cayley’s theorem given in Aigner and Ziegler’s Proofs from The Book, which I referred to in an earlier post. At this point, I really wish I had that book! I’d be delighted if someone were to post one of those nice proofs in comments…
3. I’m not quite sure, but Sune’s solution just might be my current favorite, just because it makes obvious contact with the circle of ideas which embrace endofunctions, trees, and rooted trees (I think of the tuples there as endofunctions, or actually, partial endofunctions on -element sets). In any event, my sincere thanks go to David, Philipp, and Sune for their insightful responses.
Encouraged and emboldened (embiggened?) by the ingenuity displayed by some of our readers, I’d like to see what sort of response we get to this Problem of the Week:
Establish the following identity: for all natural numbers .
(Here we make the convention .) I find this problem tantalizing because it looks as if there should be some sort of conceptual proof — can you find one?
Please send your solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, June 11, 11:59pm (UTC); do not submit solutions in Comments. Everyone with a correct solution gets entered in our Hall of Fame! We look forward to your response.