You are currently browsing the category archive for the ‘Elementary Math Problem Solving’ category.
High-school students and undergraduates are (almost) always taught the following definition of an equivalence relation.
A binary relation on a set is an equivalence iff it satisfies
- the reflexive property: for all in , ,
- the symmetric property: for all in , if , then , and
- the transitive property: for all in , if and , then .
However, there is another formulation of an equivalence relation that one usually doesn’t hear about, as far as I know. And, it is the following one.
A binary relation on a set is an equivalence iff it satisfies
- the reflexive property: for all in , , and
- the euclidean property: for all in , if and , then .
Exercise: Show that a binary relation on a set is reflexive, symmetric and transitive iff it is reflexive and euclidean.
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.
Happy holidays, folks! And happy birthday to Topological Musings, which Vishal started just a little over a year ago — we’ve both had a really good time with it.
And in particular with the Problem of the Week series. Which, as we all know, doesn’t come out every week — but then again, to pinch a line from John Baez’s This Week’s Finds, we never said it would: only that each time a new problem comes out, it’s always the problem for that week! Anyway, we’ve been very gratified by the response and by the ingenious solutions we routinely receive — please keep ‘em coming.
This problem comes courtesy of regular problem-solver Arin Chaudhuri and — I’ll freely admit — this one defeated me. I didn’t feel a bit bad though when Arin revealed his very elegant solution, and I’d like to see what our readers come up with. Here it is:
What is the maximum number of colors you could use to color the vertices of an 8-dimensional cube, so that starting from any vertex, each color occurs as the color of some neighbor of that vertex? (Call two vertices neighbors if they are the two endpoints of an edge of the cube.)
Arin, Vishal, and I would be interested and pleased if someone solved this problem for all dimensions .
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Friday, January 2, 2009, 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.
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.)
The solutions to POW-11 are in! Or make that solution, unless you also count your hosts’: only one reader responded. Perhaps everyone has been distracted by the upcoming US presidential election?!
Composite solution by Philipp Lampe, University of Bonn, and Todd and Vishal: We claim there are exactly two functions which satisfy the identity : the identity function and the function which is identically zero.
Clearly forces , whence . Therefore or , and the claim above follows if we show that for all . The first few cases are built up as follows:
where in a few places we have invoked the simple lemma that [since ]. The remainder of the argument proceeds by strong induction. For odd , we have
Since preserves sums of two squares, we derive
Therefore, using the inductive hypothesis that for , we have
From equation (1) we also have
Comparing equations (2) and (3), we infer . In particular, for , and we have the case from before. This will be used to start the induction for even , starting from .
For even , where , we have
and by arguing as we did above, we derive the two equations
where the second follows from the first by inductive hypothesis. Multiplying (4) through by and comparing with the last equation, we conclude , and this completes the proof.
The underlying idea is to exploit the fact that many numbers can be expressed as a sum of two squares in more than one way, so that one can generate enough relations of the form to nail down all the [in terms of ]. A powerful way of generating equations of the form is to consider prime factorizations in the ring of Gaussian integers . For example, in the Gaussian integers we have the prime factorizations
so that there are two ways of writing their product 65 in the form :
Here we have, respectively, , , whence . Extrapolating from this, if we set
then we have , whence we derive
This gives a large supply of available relations to work with, and from there it is not too bad to get an inductive argument up and flying, once some base cases have been cleared out of the way with some numerical experimentation.
[Although it's a little unusual to need such an outlay of base cases (up to at least ) before one can start the induction; it creates a psychological hurdle, I feel. It reminds me of POW-6, where no complete solutions were received: one has to fiddle with a number of base cases before the general argument can be pushed through.]
Incidentally, while researching this problem, I found the wonderful website MathPages, created by an all but anonymous author named Kevin Brown. I really recommend checking out this website, and I hope that it is somehow kept alive: it would be a shame for such a treasure trove to be buried and forgotten in some deep hollow of cyberspace.
Time for another problem of the week! This one doesn’t necessarily require any number-theoretic knowledge, although a little bit might help point you in the right direction. As usual, let be the set of natural numbers, i.e., the set of nonnegative integers.
Describe all functions such that for all .
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Sunday, November 2, 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.
The solutions are in! As is so often the case, solvers came up with a number of different approaches; the one which follows broadly represents the type of solution that came up most often. I’ll mention some others in the remarks below, some of it connected with the lore of Richard Feynman.
Solution by Nilay Vaish: The answer to POW-10 is . Put
and integrate by parts: we have
The first term vanishes by a simple application of L’hôpital’s rule. We now have
where the second equation follows from , and the general elementary fact that Adding the last two displayed equations, we obtain
after a simple substitution. The last integral splits up as two integrals:
but these two integrals are equal, using the identity together with the general integration fact cited above. Hence the two sides of (3) equal
recalling equation (1) above. Substituting this for the last integral in equation (2), we arrive at
whence we derive the value of the desired integral .
1. A number of solvers exploited variations on the theme of the solution above, which could be summarized as involving symmetry considerations together with a double angle formula. For example, Philipp Lampe and Paul Shearer in their solutions made essential use of the identity
in conjunction with the complementarity , and the general integration fact cited above.
2. Arin Chaudhuri (and Vishal in private email) pointed out to me that the evaluation of the integral
is actually fairly well-known: it appears for example in Complex Analysis by Ahlfors (3rd edition, p. 160) to illustrate contour integration of a complex analytic function via the calculus of residues, and no doubt occurs in any number of other places.
3. Indeed, Simon Tyler in his solution referred to this as an integral of Clausen type, and gave a clever method for evaluating it: we have
which works out to
The last integral can be expanded as a series
where the summands for odd vanish; the other terms can be collected and then resummed to yield
and by substituting this for the integral in (*), the original integral is easily evaluated.
4. Arin C. later described still another method which he says he got from an exercise in a book by Apostol — it’s close in spirit to the one I myself had in mind, called “differentiation under the integral sign”, famously referred to in Surely You’re Joking, Mr. Feynman!. As Feynman recounts, he never really learned fancy methods like complex contour integration, but he did pick up this method of differentiating under the integral sign from an old calculus book. In typical Feynman style, he writes,
“It turns out that’s not taught very much in the universities; they don’t emphasize it. But I caught on how to use that method, and I used that one damn tool again and again. So because I was self-taught using that book [Wilson's Advanced Calculus], I had peculiar methods of doing integrals. The result was, when guys at MIT or Princeton had trouble doing a certain integral, it was because they couldn’t do it with the standard methods they had learned in school. If it was contour integration, they would have found it; if it was a simple series expansion, they would have found it. Then I come along and try differentiating under the integral sign, and often it worked. So I got a great reputation for doing integrals, only because my box of tools was different from everybody else’s, and they had tried all their tools on it before giving the problem to me.”
So, what is this method? Wikipedia has a pretty good article on it; the idea is to view a given definite integral as an instance of a smoothly parametrized family of integrals, where the extra parameter is inserted at some judicious spot, in such a way that has an easy-to-integrate derivative. Then one figures out , and evaluates it at the which yields the original definite integral.
The best way to understand it is through an example. Pretend you’re Feynman, and someone hands you
[I suppose there may be a contour integration method to handle that one, but never mind -- you're Feynman now, and not supposed to know how to do that!] After fiddling around a little, you find that by inserting a parameter in the exponent,
this has a very simple derivative:
i.e., by differentiating under the integral sign, you manage to kill off that annoying factor in the denominator:
We therefore have
and notice that from the original definition of , we have . Thus , and the problem integral evaluates to . Bam!
It takes a little experience to judge where or how to stick in the extra parameter to make this method work, but the Wikipedia article has some good practice problems, including the integral of POW-10. For this problem they recommend considering
and I’ll let you the reader take it from there.
The point is not that this method is much more elegant than others, but that a little practice with it should be enough to convince one that it’s incredibly powerful, and often succeeds where other methods fail. (Not always, of course, and Feynman had to concede defeat when in response to a challenge, his pal Paul Olum concocted some hellacious integral which he said could only be done via contour integration.)
Doron Zeilberger is also fond of this method (as witnessed by this paper). Something about it makes me wonder whether it’s secretly connected with the idea of “creative telescoping” and the powerful methods (e.g., see here) developed by Gosper, Wilf, Zeilberger, and others to establish identities of hypergeometric type. But I haven’t had time to consider this carefully.
Also solved by Arin Chaudhuri, Philipp Lampe (University of Bonn), Paul Shearer (University of Michigan), and Simon Tyler. Thanks to all who wrote in!
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Friday, October 10, 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.