The American Mathematical Monthly

October 2011 Contents

In this month's issue, you'll learn how error-correcting codes can be used to improve on the "birthday trick," whether Vitali's famous non-Lebesgue measurable set can be measurable in certain extensions of Lebesgue measure, how a shape in the plane can be reduced to a "skeleton" and then reconstructed from that skeleton, and much more.

For subscribers, read recent issues online (Requires MAA Membership)

ARTICLES

The Birthday Trick with Lies

Murad Özaydın and Charlotte Simmons
In this article, we determine the number of yes/no questions required to figure out a birthday (a number between 0 and 31) when up to rincorrect answers to these questions are allowed. In the language of error-correcting codes, we construct optimal (shortest possible length) codes of size 32 and minimal distance d for each positive integer d.

Semiperimeter and Pythagorean Triples

Russell A. Gordon
We consider the semiperimeter (half the perimeter) of right triangles having relatively prime positive integers as side lengths. These values are always integers and we construct integers which are the semiperimeter of one or more such triangles. We prove that for each positive integer k, there exist infinitely many positive integers s such that s is the semiperimeter of exactly k distinct triangles of this type. In addition, we establish an upper bound (as a function of the number of distinct primes in the prime factorization of s) for the number of these triangles that can have a given semiperimeter s.

Measurability Properties of Vitali Sets

A. B. Kharazishvili
It is shown that some Vitali subsets of the real line R can be measurable with respect to certain translation quasi-invariant measures on R extending the standard Lebesgue measure. On the other hand, there exist Vitali sets which are nonmeasurable with respect to every nonzero σ-finite translation quasi-invariant measure on R.

Quotient Sets and Diophantine Equations

Stephan Ramon Garcia, Vincent Selhorst-Jones, Daniel E. Poore, and Noah Simon
Quotient sets

have been considered several times before in the MONTHLY. We consider more general quotient sets

and we apply our results to certain simultaneous Diophantine equations with side constraints.

Reconstruction from Medial Representations

P. J. Giblin and J. P.Warder
In the analysis of planar shapes there are a number of ways of reducing the shape to a one-dimensional “skeleton”: the medial axis, the symmetry set, and the “smoothed local symmetry,” which we call here the midpoint locus. All depend on circles which are twice-tangent to the boundary curve of the shape. In addition there is a “pre-symmetry set” which underlies all these constructions. We describe how a shape can be reconstructed from its medial axis or symmetry set, that is, the centers of the twice-tangent circles, and a knowledge of their radii. Then we ask the question: can the shape be reconstructed similarly from its midpoint locus—this amounts to giving the midpoints of chords of twice-tangent circles instead of their centers—and the radii? The first answer is “yes, given an initial condition,” but further analysis shows that this is so sensitive to that initial condition as to make the reconstruction difficult. We also suggest other avenues of investigation.

The Seventy-First William Lowell Putnam Mathematical Competition

Leonard F. Klosinski, Gerald L. Alexanderson, Loren C. Larson, and Mark Krusemeyer
The results of the Seventy-First William Lowell Putnam Mathematical Competition.

NOTES

On the Parity of a Permutation

R. K. Oliver
This note gives a simplification of Mac Lane’s proof that the map which assigns to each permutation in the symmetric group S_n the value 1 or -1 according as the number of its inversions is even or odd is a homomorphism.

The Hitting Time Theorem Revisited

Wouter Kager
This note presents a very short and simple combinatorial proof of the classical hitting time theorem, or equivalently, the ballot theorem.

The Least Prime Congruent to One Modulo n

R. Thangadurai and A. Vatwani
It is known that there are infinitely many primes congruent to 1 (mod n) for any integer n > 1. In this paper, we use an elementary argument to prove that the least such prime is at most

, where

is the Euler totient function.

A Blichfeldt-type Theorem for H-points

Penghao Cao and Liping Yuan
Let H be the set of vertices of a tiling of the plane by regular hexagons of unit area. A point of H is called an H-point. Let [s] denote the greatest integer less than or equal to s, and let {s} = s - [s]. In this paper we prove a Blichfeldt-type theorem for H-points. It is shown that for any bounded set

of area s, if 0 ≤ {s} < 1/3, then D can be translated so as to cover at least 2[s] + 1 H-points; if 1/3 ≤ {s} < 1, then by a translation D can be made to cover at least 2[s] + 2 H-points. Furthermore, we show that the results obtained are the best possible.

PROBLEMS AND SOLUTIONS

REVIEWS

The Mathematics that Every Secondary School Math Teacher Needs to Know
Alan Sultan and Alice F. Artzt
Reviewed by: Richard Askey

The American Mathematical Monthly Homepage