February Issue

PROBLEMS ELGIN H. JOHNSTON, Editor Iowa State University

˘ Assistant Editors: RAZVAN GELCA, Texas Tech University; ROBERT GREGORAC, Iowa State University; GERALD HEUER, Concordia College; VANIA MASCIONI, Ball State University; BYRON WALDEN, Santa Clara University; PAUL ZEITZ, The University of San Francisco

PROPOSALS To be considered for publication, solutions should be received by July 1, 2009. 1811. Proposed by Emeric Deutsch, Polytechnic University, Brooklyn, NY. Given a connected graph G with vertices v1 , v2 , . . . , vn , let di, j denote the distance from vi to v j . (That is, di, j is the minimal number of edges that must be traversed in traveling from vi to v j .) The Wiener index W (G) of G is defined by  W (G) = di, j . 1≤i< j ≤n

a. Find the Wiener index for the grid-like graph

on 2n vertices. b. Find the Wiener index for the comb-like graph

on 2n vertices. 1812. Proposed by Bob Tomper, University of North Dakota, Grand Forks, ND. Let m and n be relatively prime positive integers. Prove that     n n   km km n(n 2 − 1)(m − 1) . k2 k =n − n n 12 k=1 k=1 We invite readers to submit problems believed to be new and appealing to students and teachers of advanced undergraduate mathematics. Proposals must, in general, be accompanied by solutions and by any bibliographical information that will assist the editors and referees. A problem submitted as a Quickie should have an unexpected, succinct solution. Solutions should be written in a style appropriate for this M AGAZINE . Solutions and new proposals should be mailed to Elgin Johnston, Problems Editor, Department of Mathematics, Iowa State University, Ames IA 50011, or mailed electronically (ideally as a LATEX file) to [email protected]. All communications, written or electronic, should include on each page the reader’s name, full address, and an e-mail address and/or FAX number.

63

64

MATHEMATICS MAGAZINE

1813. Proposed by Elton Bojaxhiu, Albania, and Enkel Hysnelaj, Australia. Let a, b, and c be positive real numbers. Prove that 1 1 1 3 + + ≥√ . √ 3 a(1 + b) b(1 + c) c(1 + a) abc(1 + 3 abc) 1814. Proposed by Michael Goldenberg and Mark Kaplan, The Ingenuity Project, Baltimore Polytechnic Institute, Baltimore, MD. Let A1 A2 A3 be a triangle with circumcenter O, and let B1 be the midpoint of A2 A3 , B2 be the midpoint of A3 A1 , and B3 be the midpoint of A1 A2 . For −∞ < t ≤ ∞ and −−−→ −−→ k = 1, 2, 3, let Bk,t be the point defined by O Bk,t = t O Bk (where by Bk,∞ we mean −−→ the point at infinity in the direction of O Bk ). Prove that for any t ∈ (−∞, ∞], the lines Ak Bk,t , k = 1, 2, 3, are concurrent, and that the locus of all such points of concurrency is the Euler line of triangle A1 A2 A3 . 1815. Proposed by Stephen J. Herschkorn, Rutgers University, New Brunswick, NJ. It is well known that if R is a subring of the ring Z of integers, then there is a unique positive integer m such that R = mZ. Determine a similar unique characterization for any subring of the ring Q of rational numbers. What is the cardinality of the class of all subrings of Q? (We do not assume that a ring has a multiplicative identity.)

Quickies Answers to the Quickies are on page 69. Q987. Proposed by Scott Duke Kominers, student, Harvard University, Cambridge, MA. Let A and B be n × n commuting, idempotent matrices such that A − B is invertible. Prove that A + B is the n × n identity matrix. Q988. Proposed by Ovidiu Furdui, Campia-Turzii, Cluj, Romania. Let k and p be positive integers. Prove that 1k + 2k + · · · + n k = (1 + 2 + · · · + n) p is true for all positive integers n if and only if k = p = 1 or k = 3 and p = 2.

Solutions Odd sums

February 2008

1786. Proposed by Marian Tetiva, Bˆırlad, Romania. Let n ≥ 2 be a positive integer and let On = {1, 3, . . . , 2n − 1} be the set of odd positive integers less than or equal to 2n − 1. a. Prove that if m is a positive integer with 3 ≤ m ≤ n 2 and m  = n 2 − 2, then m can be written as a sum of distinct elements from On . b. Prove that n 2 − 2 cannot be written as a sum of distinct elements of On .