E31. A packing polynomial

Funny how one comes across math problems. I was reading my Reed College alumni magazine and came across an article about Maddie Grant, class of '15, whose undergraduate thesis is apparently a substantial generalization of a 1923 result by Fueter and Polya. Feuter and Polya evidently discovered a polynomial function that maps the non-negative integers one-to-one and onto the pairs of non-negative integers. That is, they found a simple formula to express the inverse Cantor's "diagonal" mapping of pairs of non-negative integers to non-negative integers. Their function ‐ a so-called packing polynomial ‐ is given by

f(x,y) = (1/2)[(x + y)² + x + 3y],
where x and y are non-negative integers.

The proof that this function is one-to-one and onto the non-negative integers is actually pretty elementary if you look at it the right way. I will print a hint as a comment in a few days.

A11. Splitting a triangle and a tetrahedron

János Kurdics published this interesting problem in The Math Connection Linkedin group:
Given a triangle, find the shortest line segment that divides the triangle into two regions of equal area. A solution that does not involve calculus is preferred.
The solution that I know is very nice, and gives quite a workout in elementary trigonometry.

János says that he is working on three-dimensional analog (plane that divides a tetrahedron into two regions of equal volume and gives smallest possible cross-sectional area with the tetrahedron) but has only solved it for a regular tetrahedron.

Multiplication table problem

Sometimes mathematics problems that are interesting to the professional mathematician can arise out of the simplest questions. We all learned a multiplication table in school, which lists all 100 products of integers from 1 * 1 to 10 * 10. I've been told that in England, students are required to memorize up to 12 * 12. In the multiplication table for 1 to 10, there are 100 products, but it is only necessary to learn 55, because of the commutative property. In other words, we only need to learn the products a * b, where a ≤ b, and the number of such products is 1 + 2 + ... + 10 = T(10) = (11)(10)/2, where T(n) is the n-th triangular number, (n + 1) * n / 2. Therefore, the number of different products is at most 55. Actually it is less. For example, 6 appears twice in the triangular table, as 1 * 6 and as 2 * 3. The number of different products in a 10 by 10 multiplication table is 42. (Shades of Douglas Adams!)

A mathematician would naturally be interested in knowing how many different products there are in an n by n multiplication table, in other words, the number of different products of the form ab, where a and b are positive integers less than or equal to n. Call this sequence a(n). Then a(n) ≤ T(n), so the lim sup of a(n)/n^2 as n goes to infinity is less than or equal to 1/2. In fact, Erdös gave a very nice proof that the limit is 0, and he and others obtained more accurate asymptotic formulas for a(n).

See the Online Encyclopedia of Integer Sequences, where a(n) is given as sequence A027424. Links provide much information about the sequence. Also, the question of how many different numbers appear in a multiplication table could be given to students at almost any level.

Changes in Mathematics Research Methods

The following math problem appeared in a math forum that I follow:

You have a deck of 56 cards, labeled 1 through 56. All the cards are drawn randomly one at a time. What is the probability that for exactly one card, the face value of the card is one less than the face value of the card before it.

The reason for considering the number 56 was not specified, but that doesn't matter because it is clear that to solve the problem in any kind of satisfying way we have to solve it in a more general case, where 56 is replaced by n. In this case, the probability is P(n)/n!, where P(n) is the number of permutations p of (1, … ,n) for which p(k – 1) – p(k) = 1 for exactly one k. The problem reduces to finding P(n).

The answer is rather neat, and (SPOILER ALERT) I give it below. However what I find most interesting is the way my finding the solution to this problem depended so much on technology. To solve it I did not need to know much mathematics at all. If I had had to solve the problem 30 years ago, it would have taken much more knowledge and/or much more time.

The first thing I did was to generate some numerical evidence. By writing out the acceptable permutations and counting them, I found that P(2) = 1, P(3) = 2, P(4) = 9, and P(5) = 43. I sent the problem to a friend of mine, Ken Cutter, who is a MATLAB guru, and he wrote a short program in MATLAB, using perms(1 … n) to list all permutations and the diff function to compute the differences p(k) – p(k-1). He discovered that I had missed one acceptable permutation of (1 … 5) so that actually P(5) = 44. He also gave me the list of a few more values of P, including P(6) = 265.

I now knew I was looking for a sequence 1 , 2, 9, 44, 265, … , so I went to the Online Encyclopedia of Integer Sequences (OEIS, https://oeis.org/) and entered 1 , 2, 9, 44, 265 into the search field, and out came two known sequences. Only the first of these two sequences seemed to relate to permutations, and sure enough, one the descriptions of this sequence identified it as what I was looking for.

The answer turns out to be that P(n) number of derangements of P(n), that is, the number of permutations with no fixed points. The formula for P(n) is given on OEIS as P(n) = n!*Sum((-1)^k/k!, k=0..n). On the Wikipedia page for derangements, it is noted that a common notation for P(n) is !n, so the desired probability is !n/n! = Sum((-1)^k/k!, k=0..n) which, as Wikipedia notes, converges rapidly to 1/e. In fact, it is the first n terms of the Taylor expansion for exp(x) about 0, evaluated at x = -1.  For the original problem with n = 56, the answer for all practical purposes is 1/e.

Looking back, the most crucial tool in my finding the solution was The Online Encyclopedia of Integer Sequences, started by Neil J. A. Sloane, and a wonderful resource for anyone involved in mathematical work. MATLAB was also very helpful. Without it, I might have still gotten the answer if I had gone over my work and discovered my mistake which made me get P(5) off by one. If I had entered the correct first 4 terms, Online Encyclopedia of Integer Sequences would have returned 17 sequences, but it would still have been pretty easy to find the correct sequence from amongst these 17. But MATLAB (and Ken Cutter) saved a lot of time. Lastly, Wikipedia was a help in explaining the result.

When I was in school, none of these resources were available. If I knew more about combinatorial mathematics, I might have known the answer immediately, or at least recognized it once I generated the numerical examples. Otherwise, I would have had to look at my lists of acceptable permutations more carefully and perhaps derived a recursion relation or induction step that would enable me to find the solution. I would be interested in hearing from anyone would like to send me a solution to this problem from scratch, imagining that they do not know the answer already.

This experiences brings home to me how much the methods of mathematics research have changed since I was in school. I wonder what changes we should be making in K-12 math education that take into account these changes.

From a Spreadsheet Problem to the Umbral Calculus: A Mathematical Odyssey

I'm planning to write a paper where I describe how a colleague's challenge to come up with an Excel formula to compute a weighted average of grades led me to make a couple of mathematical conjectures, and how I was able to prove the conjectures and solve the problem. Along the way, I got a lot of help from many people and I discovered a lot of combinatorial mathematics that I had not known, including the Binomial Inversion Formula and the Umbral calculus. In describing this odyssey I will explore the social nature of mathematics and the different ways that people from different disciplines approach mathematical problems. Also, I hope to show that experiences of this sort can be replicated in the classroom through a problem-based method of learning.

A New Business Card

I recently designed a new business card, using an interesting geometrical structure as a design element. The design is based on a circular Dirichlet tessellation, also known as a Voronoi diagram with multiplicative weights. The design seemed appropriate because I have done research on these structures in the past, in a paper I wrote with Ethan Bolker in the eighties.

In the multplicative Voronoi diagram, we start with a finite number of sources (points) in the plane, each assigned a positive weight w. The diagram consists of the circles or circular arcs that divide the plane into regions, where the region corresponding to point P consists of all points X such that
|P-X|/w(P) is less than or equal to |Q-X|/w(Q) for every other source Q.

You can think of the sources as being restaurant locations and the weights as being a desirability rating, so if w(P) is r times w(Q), a customer is willing to travel r times as far to go to P as to go to Q. For the case of two sources, the boundary is the circle of Apollonius of ratio r. The case where all weights are equal reduces to the classical Voronoi diagram, where the circular arcs degenerate into straight lines.

If you would like to play around with these diagrams, you can use the applet written by Gabi Knuppertz at http://www.pi6.fernuni-hagen.de/GeomLab/VoroMult/. I was not able to find the needed plugin for Firefox, but got it to work fine in Internet Explorer.