##
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 *Q*^{2} on a level curve of *P* is at a singular point or the minimum is zero, and similarly for *P*^{2} 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