From - Mon Aug 17 18:35:06 1998 Path: ar4dec01!ar4news.dlh.de!newsfeed2.de.ibm.net!newsfeed.uk.ibm.net!ibm.net!dispose.news.demon.net!demon!woodstock.news.demon.net!demon!howland.erols.net!dca1-hub1.news.digex.net!digex!news.fas.harvard.edu!ramanujan!elkies From: Noam D. Elkies Newsgroups: sci.math,rec.puzzles Subject: *Spoilers* Re: Russian mathematical puzzles Date: 17 Aug 1998 15:13:49 GMT Organization: Harvard Math Department Message-ID: <6r9hbd$obd$1@news.fas.harvard.edu> References: NNTP-Posting-Host: ramanujan.math.harvard.edu Originator: elkies@ramanujan Lines: 35 Xref: ar4dec01 sci.math:79493 rec.puzzles:21652 In article , Anatoly Vorobey wrote: >On Mon, 17 Aug 1998 08:25:24 +0100, >John Scholes wrote: >>I have acquired a large number of Russian mathematical puzzles (without >>solutions) aimed at children aged 14-16. >>Sample 1: Given an mxn array of reals. You may change the sign of all >>numbers in a row or in a column. Prove that by repeated changes you can >>obtain an array whose row and column sums are all non-negative. >>Sample 2: ABC is an equilateral triangle. The point P satisfies AP=2, >>BP=3. Find the maximum possible value of CP. >Took me a few minutes to solve the first one, but I couldn't see >a way to solve the second one except by long, tedious and >trivial equations, which is not interesting. Spoilers for both sample problems follow: (1) There are only finitely many changes possible [at most 2^(m+n), since row and column changes are independent; indeed changing all the rows is equivalent to changing all the columns, so at most 2^(m+n-1)]. Choose one that maximizes the sum of the entries. Then flipping any row or column reduces that overall sum by twice the row or column sum, so such a sub-sum cannot be negative. (2) By Ptolemy's inequality (aha!) CP is at most AP+BP with equality iff P is on the AB arc of the circumscribed circle of ABC, i.e. iff angle APB measures 120 degrees and P,C are on opposite sides of the line AB. So in our case the maximum is 2+3=5. --Noam D. Elkies (Dept. of Mathematics, Harvard University) [change UK to USA abbreviation to recover correct e-mail address]