# American Mathematical Monthly -NOVEMBER 2009

## November 2009

Maximum Overhang
By: Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick
msp@dcs.warwick.ac.uk, peres@microsoft.com, mthorup@research.att.com, peter.winkler@dartmouth.edu, zwick@cs.tau.ac.il
A 150-year-old problem asks how many identical rectangular blocks of length 1, balanced at the edge of a table, are needed to achieve some given overhang D beyond the table edge. A well-known construction based on the harmonic series requires a number of blocks which grows exponentially with D. Many people had assumed that this was optimal until a construction by Paterson and Zwick in this MONTHLY (January 2009) showed that a quantity just cubic in D was sufficient. The current paper settles this classic problem within a constant factor, proving cubic growth to be not only sufficient, but also necessary.

(The results in this paper were featured in Science 323 (Feb. 13, 2009) 875.)

Carries, Shuffling, and an Amazing Matrix
By: Persi Diaconis and Jason Fulman
fulman@usc.edu
The number of "carries'' when n random integers are added forms a Markov chain, studied by John Holte in 1997 in an article in this Monthly. We show that this Markov chain has the same transition matrix as the descent process when a deck of n cards is repeatedly riffle shuffled. This gives new results for the statistics of carries and shuffling.

Rational Functions
By: Luis Verde-Star
verde@star.izt.uam.mx
We use a linear algebraic approach to study rational functions. We find a basis for the space of proper rational functions and prove the general partial fractions decomposition formula, the Hermite polynomial interpolation formula, and some properties of rational functions related to residues.

Using duality we identify rational functions with linear functionals on the space of polynomials and show that the space of proper rational functions has an interesting algebraic structure, obtained by duality from the structure of the polynomials.

The vector space of proper rational functions is isomorphic to the space of exponential polynomials and also to the space of linearly recurrent sequence. Such isomorphisms are used to explain the origin of several convolution products and transform methods for the solution of linear functional equations.

Notes

Lagrange Multipliers and the Fundamental Theorem of Algebra
By: Theo de Jong
dejong@mathematik.uni-mainz.de
This paper gives a proof of the fundamental theorem of algebra. The main idea is as follows. Let F(x+iy) = P(x,y) + iQ(x,y), where F(z) is a polynomial with complex coefficients and P and Q are real polynomials. We show that either the minimum of Q2 on a level curve of P is at a singular point or the minimum is zero, and similarly for P2 on a level curve of Q. We prove this fact by applying the theorem of Lagrange multipliers.

On Sara's Dove Bar Habit
By: D. M. Einstein, C. C. Heckman, and T. S. Norfolk
deinst@gmail.com, checkma@math.asu.edu, norfolk@uakron.edu
We consider a specific function from the set of finite binary sequences to the set of finite ternary sequences, expressed as a whimsical sampling problem. Using a bivariate generating function and some simple asymptotics, we derive the expected value of the ratio of 2s and 1s in the resulting sequence. The surprising result is that this value for large sequences is not the same as that for a sequence of infinite length.

An Identity Involving the Least Common Multiple of Binomial Coefficients and its Application
By: Bakir Farhi
bakir.farhi@gmail.com
In this note, we obtain an explicit formula for the least common multiple of the binomial coefficients with a given upper index k in terms of the least common multiple of the integers from 1 to k + 1. As an application, we give an easy proof of a nontrivial lower bound for the least common multiple of a finite initial segment of the positive integers.

Stirling's Series Revisited
By: Valerio De Angelis
vdeangel@xula.edu
The classical Stirling series for log n! is an asymptotic expansion that involves the Bernoulli numbers and only odd powers of 1/n. It follows easily that the asymptotic series for 1/n! is obtained from that of n! by changing the signs of the coefficients of the odd powers of 1/n. In this note, we present a short and elementary derivation of the asymptotic series for n! that produces a new expression for the coefficients and directly proves the simple relationship between the series for n! and that for 1/n! without relying on the classical expression of the series for log n! in terms of the Bernoulli numbers.

Reviews

Mathematical Masterpiece: Further Chronicles by the Explorers
By: Arthur Knoebel, Reinhard Laubenbacher, Jerry Lodder, and David Pengelley
Reviewed by: Victor J. Katz
vkatz@udc.edu