# Christopher Carl Heckman'sAmerican Mathematical Monthly Problem Solutions

My homepage

Solutions to AMM Problems

People
Things
Electronic Journals and Preprints

## My Solutions to American Mathematical Monthly Problems

### All solutions are in Acrobat (PDF) form.

1. Proposed by Harry Tamvakis, University of Pennsylvania, Philadelphia, PA. (October 1998) Let a1, a2, ... an be a sequence of nonzero real numbers, exactly p of which are positive. Characterize the pairs (n, p) such that exactly half of the possible products aiajak with i < j < k are positive.   (Reconstructed) Solution   (October 2000, "Splitting Triple Products by Sign")

2. Proposed by Józef Przytycki, The George Washington University, Washington, DC. (January 2001) A lattice simple closed curve in the plane is a simple closed curve all of whose points have an integer coordinate. The area A(C) enclosed by such a curve C is always a positive integer. A shrinking move on a lattice simple closed curve C is one that replaces C with another such curve D whose interior is inside C and with A(D)=A(C)-1. Is is always possible to transform a lattice simple closed curve to a 1-by-1 square via shrinking moves?   Solution   (January 2002, "Shrinking Lattice Curves")

3. Proposed by Andrei Jorza, "Moise Nicoara" High School, Arad, Romania. (February 2001) Find all bounded convex polyhedra such that no three faces have the same number of edges.   Solution (with Generalization)   Mathematica Notebook with Pictures   (February 2006; "No Three Faces with the Same Number of Edges")

4. Proposed by Gordon Rice, Davis, CA. (November 2001) It is clear from the law of cosines that every angle that occurs in a triangle with integer sides has a rational cosine. Is the converse true? Does every angle between 0 and π with a rational cosine occur in some triangle with integer sides?   Solution (with Generalization)   (Aug-Sept 2003, "Angles with Rational Cosines")

5. Proposed by Jean-Marie De Koninck, Université Laval, Québec, Canada. (October 2002)
1. Let φ denote the Euler φ function, and let γ(n) be the product of the primes that divide into n, with γ(1)=1. Prove that there are exactly six positive integers such that φ(n)=(γ(n))2.
2. * Let σ(n) denote the sum of divisors of n. Prove or disprove that the only solutions to σ(n)=(γ(n))2 are n=1 and n=1782.

Solution (with Generalization)   (June/July 2004, "When the Totient is the Product of the Squared Prime Divisors")

6. Proposed by Li Zhou, Polk Community College, Winter Haven, FL. (December 2005) Find a closed formula for the number of ways to tile a 4 by n rectangle with 1 by 2 dominoes.   Solution   (June/July 2007, "Tiling 4-Rowed Rectangles with Dominoes")

7. Proposed by Mohammad Hossein Mehrabi, Iran University of Science and Technology, Tehran, Iran. (January 2006) Let A and B be real n × n matrices. Show that if AB−BA is invertible and A2+B2=√3(AB−BA), then n is a multiple of 6.   Solution   (January 2008, "A Condition on the Cummutator")

8. Proposed by Li Zhou, Polk Community College, Winter Haven, FL. (March 2006) The stage-n Menger Sponge Mn is generated recursively, starting with the unit cube M0. To drill a cube is to partition it into twenty-seven congruent subcubes and remove the closed central cube along with the six remaining subcubes sharing a face with that cube, resulting in a solid that is the union of twenty congruent cubes. Given Mn-1, construct Mn by drilling each of the 20n-1 subcubes of edge-length 31-n in Mn-1. M4 is shown:

The chromatic number of a surface is the minimum number of colors that suffice to color any map drawn on that surface (so that the chromatic number of M0 is 4 by the celebrated "Four Color Theorem.") Find the chromatic number of the surface of Mn.   Solution (with Conjecture)   (November 2007, "Coloring Graphs on Sponges")

Update, March 2009: Li Zhou has informed me that my conjecture (about the source of the problem) is false.

9. Proposed by Alexander Dubinov and Irina Dubinova, Russian Federal Nuclear Center, Sarov, Russia. Consider the following system of n equations in n positive unknowns x1, ... xn and n positive given numbers a1, ... an:
Find a formula in closed form for x1, ... xn in terms of a1, ... an.   Solution   (December 2007, "Can "Closed Form" Involve Lambert?")

10. Proposed by David Beckwith, Sag Harbor, NY. (March 2006) Show that for an arbitrary positive integer n
Two Solutions   (April 2008, "A Vanishing Alternating Sum")

11. Proposed by Gary Gordon, Lafayette College, Easton, PA. (April 2006) Consider the following algorithm, which takes as input a positive integer n and proceeds by rounds, listing in each round certain positive integers between 1 and n inclusive, ultimately producing as output a positive integer f(n), the last number to be listed. In the 0th round, list 1. In the first round, list, in increasing order, all primes less than n. In the second round, list in increasing order all numbers that have not yet been listed and are of the form 2p, where p is prime. Continue in this fashion, listing numbers of the form 3p, 4p, and so on until all numbers between 1 and n have been listed. Thus f(10)=8 because the list eventually reaches the state {1,2,3,5,7,4,6,10,9,8}, while f(20)=16 and f(30)=27.
(a) Find f(2006).
(b) Describe the range of f.
(c) Find

Solution and Poly-time Algorithm   (April 2008, "The Number Between 1 and n That is Least Prime")

12. Proposed by Roberto Tauraso, Università di Roma "Tor Vergata", Rome, Italy. (August-September 2006) Find a closed formula for
where Fn denotes the nth Fibonacci number (that is, F0=0, F1=1, and Fj=Fj-1+Fj-2 when j ≥ 2) and S[k,n] is the set of all (k+1)-tuples of nonnegative integers that sum to n-k.   Solution, Generalization, and Variations (November 2008, "Fibonacci Numbers and Tiling a Board with Cuts")

13. Proposed by Manuel Kauers, Research Institute for Symbolic Computation, Johannes Kepler University. (December 2006) Let Fn denote the nth Fibonacci number, and let i denote √(-1). Prove that
Solution and Variation   (December 2008, "A Telescoping Fibonacci Sum")

14. Proposed by Ashay Burungale, Satara, Maharashtra, India. (December 2006) In a certain town of population 2n+1, one knows those to whom one is known. For any set A of n citizens, there is some person amongst the other n + 1 who knows everyone in A. Show that some citizen of the town knows all the others.   Solution   (November 2008, "Getting to Know You, Directly and Indirectly"; my solution published)

Solution   (November 2009, "Baking a Pi with Factorials")

16. Proposed by David Beckwith, Sag Harbor, NY. (February 2008) Show that when n is a positive integer,
Solutions   (December 2009, "The Number of Balanced Senates from n States")

17. Proposed by Roger Cuculière, France. (February 2008) Find all nondecreasing functions f from R to R such that f(x+f(y)) = f(f(x)) + f(y) for all real x and y.   Solution and Variation   (October 2009, "A Functional Equation")

18. Proposed by Bhavana Deshpande, Poona College of Arts, Science & Commerce Camp, Pune, India, and M. N. Deshpande, Institute of Science, Nagpur, India. (March 2008) Given a positive integer n and an integer k with 0 ≤ k ≤ n, form a permutation a = (a1, ..., an) of (1, ..., n) by choosing the first k positions at random and filling the remaining n - k positions in ascending order. Let En,k be the expected number of left-to-right maxima. (For example, E3,1 = 2, E3,2 = 11/6, and E4,2 = 13/6.) Show that En+1,k - En,k = 1/(k+1). (A left-to-right maximum occurs at k when aj < ak for all j < k.)   Solution and Variation   (January 2010, "A Partially Random Permutation"; my variation published)

19. Proposed by David Callan, University of Wisconsin, Madison, WI. (May 2008) A bit string arc diagram is an undirected graph in which the vertices are the positions in a single string of bits and the edges are called arcs due to the visual representation in which they are drawn joining positions in the string. To be a good diagram, arcs must occur only between unequal bits, and each bit may be the left endpoint of at most one arc. Thus, the first diagram is good but, for two reasons, the second is not.
There are six good diagrams on two bits, four with no arc and two with a single arc. How many good diagrams are there on n bits?   Solution and Generalization   SOLUTION WAS NOT SUBMITTED ON TIME.   (February 2010, "Counting Good Bit String Arc Diagrams")

20. Proposed by Christopher Hillar, Texas A&M University, College Station, TX, and Lionel Levine, Massachusetts Institute of Technology, Cambridge, MA. (Aug/Sep 2008) Given a monic polynomial p of degree n with complex coefficients, let Ap be the (n + 1) × (n + 1) matrix with p (–i + j) in position (ij), and let Dp be the determinant of Ap. Show that Dp depends only on n, and find its value in terms of n.   Solution   (October 2010, "A Determinant Generated by a Polynomial")

21. Proposed by K. S. Bhanu, Institute of Science, Nagpur, India, and M. N. Deshpande, Nagpur, India. (???) A fair coin is tossed n times, with n ≥ 2. Let R be the resulting number of runs of the same face, and X the number of isolated heads. Show that the covariance of the random variables R and X is n / 8.   Solution   (December 2010, "Runs Versus Isolated Heads in Coin Tossing")

22. Proposed by A. A. Dzhumadil'daeva, Almaty, Republics Physics and Mathematics School, Almaty, Kazakhstan. (January 2009) Let n!! denote the product of all positive integers not greater than n and congruent to n mod 2, and let 0!!=(-1)!!=1. For positive integer n, find
in closed form.  Two solutions (December 2010, "A Double Factorial Sum")

23. Proposed by Emeric Deutsch, Polytechnic University, Brooklyn, NY. (March 2009) Find the number of bit strings of length n in which the number of 00 substrings is equal to the number of 11 substrings. For example, when n = 4 we have 4 such bit strings: 0011, 0101, 1010, and 1100.   Solution and Generalization   (April 2011, "Equally Many Repetitions of Each Type"; my version published)

24. Proposed by M. L. Glasser, Clarkson University, Potsdam, NY. (April 2009) Find
 Γ(1/14) Γ(9/14) Γ(11/14) Γ(3/14) Γ(5/14) Γ(13/14)
where Γ denotes the usual gamma function, given by Γ(z) = ∫0 t z-1 e–t dt.   Solution and Variations   (November 2010, "Gamma Products")

25. Proposed by Estelle L. Basor, American Institute of Mathematics, Palo Alto, CA, Steven N. Evans, University of California, Berkeley, CA, and Kent E. Morrison, California Polytechnic State University, San Luis Obispo, CA. (June-July 2010) Find a closed-form expression for
Solution

26. Proposed by Andrew McFarland, Płock, Poland () Given four concentric circles, find a necessary and sufficient condition that there be a rectangle with one corner on each circle.   SOLUTION TO APPEAR AUGUST 1, 2011.

Now the legal stuff: These links are provided as a courtesy. Arizona State University does not, and does not mean to, endorse the linkage to these materials.

The contents of this page reflect solely the opinions of the author who originated it; the opinion of Arizona State is that I should stop goofing off and get to work. This page has (obviously) not been reviewed by, nor is it (again, obviously) a publication of Arizona State University. The person who is responsible for this page is: checkman@math.asu.edu. Praise his name. Better yet, send him money. Lots of money. And offer him a tenure-track job.