You are here

American Mathematical Monthly - February 1997

January | February | March | April | May | June/July | August/September | October | November | December

Click on the months above to see summaries of articles in the MONTHLY.

An archive for all the 1997 issues is now available


Scheduling Conflict-free Parties for a Dating Service Bryan L. Shader and Chanyoung Lee Shader


The paper studies a scheduling problem that a dating service might confront. The dating service has n divorces couples as their clients. Each person refuses to attend the same party as his or her ex-spouse, but desires to party with each of the other clients of the opposite sex. The dating service wants to arrange a sequence of parties in such a way that no two former couples attend the same party, and yet each client parties exactly once with the other clients of the opposite sex. The dating service asks: Can this be arranged, and if so, what is the fewest number of parties necessary? The problem is reformulated as a graph partitioning problem and as a matrix factorization problem. Elementary linear algebra is used to solve the problem.


An Infinite Set of Heron Triangles with Two Rational Medians
Ralph H. Buchholz and Randall L. Rathbun


This paper presents a construction that generated infinitely many distinct rational sided triangles with two rational medians and rational area. This settles a question raised by Dickson on the existence of such triangles. We show that these triangles correspond to rational points on rank one elliptic curves. Along the way, we uncover connections to Somos sequences and theta functions.


Connected Sprouts
T.K. Lam


The game of Sprouts is a game with pen and paper. First, some points are drawn on the paper. A play or move is drawing an arc joining 2 points or a point to itself, and then adding a new point on the arc subject to the conditions:
  1. the arcs do not cross each other
  2. the degree of each point does not exceed 3
the game ends when no move can be made. The article answers two questions, posed by Mark Copper in Volume 100 (1993) of the Monthly, about the graph that is obtained at the end of the game. Explicit constructions are used to find the smallest number of plays required when the graph is connected and when it is 2-connected.


Regular Expressions for Program Computations
Ronald E. Prather


Techniques are borrowed from the theory of regular expressions and from the decomposition theory of program flowgraphs to present a modified version of the Böhm-Jacopini Theorem: To every program there sorresponds an equilavent structured program, i.e., one involving only the repetition, selection, and sequence constructs. A cubic graph model of programs is adopted for this purpose, and examples of the various constructions are provided.


Relations between Crossing Numbers of Complete and Complete Biparite Graphs
R. Bruce Richter and Carsten Thomassen


Computing the crossing number of a graph is well-known to be difficult. Long-standing conjectures for the crossing numbers of the complete and complete bipartite graphs remain open. In this article, we use quadratic forms to find optimal "cylindrical" drawings of the complete bipartite graph. These are used to construct currently best drawings of the complete graphs in the plane. Further, we show that there is an intimate asymptomatic relationship between the crossing numbers of the complete and complete bipartite graphs.


Carries, Combinatorics, and an Amazing Matirx
John M. Holte


If m numbers in a given base are formed from independent uniformly distributed random digits, then are added, the carries form an m-state Markov Chain. The transition probability matrix, whose formula is derived, is centrosymmetric. Its eigenvalues and eigenvectors, first explored numerically, are proven to be related to several familar sequqnces and arrays, including geometric sequences, binomial coefficients, Eulerian numbers, and Stirling numbers of the first kind.


A new Look at Euler's Theorem for Polyhedra: A Comment
Walter Nef


This note concerns some critical remarks about a paper of Branko Grünbaum and Geoffrey Shephard (Monthly 101 (1994), 109-128). It also presents a particularly short and simple proof of the Theorem of Euler-Schläfli.