[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1942.0. "Math Magazine 1466" by RUSURE::EDP (Always mount a scratch monkey.) Thu Feb 23 1995 15:49

    Proposed by David M. Bloom, Brooklyn College of CUNY, Brooklyn, New
    York.
    
    Let m and n be positive integers.  If x[1], ..., x[m] are positive
    integers whose average is less than n+1 and if y[1], ..., y[n] are
    positive integers whose average is less than m+1, prove that some sum
    of one or more x's equals some sum of one or more y's.  (This is a
    strengthening of Putnam problem A-4, 1993; see this Magazine, April
    1994, 156-157.)
T.RTitleUserPersonal
Name
DateLines
1942.1pigeonhole principle strikes againFLOYD::YODERMFYFri Feb 24 1995 17:5117
The conditions on the means are equivalent to

  sum(xi) <= nm+m-1, sum(yj) <= nm+n-1.  WLOG assume m <= n.

Since no two sums of xi are equal, if no sum of xi equals any sum of yj, we have
(2^n - 1) + (2^m - 1) different sums in the range 1 .. mn+n-1.  This implies

  2^n + 2^m - 2 <= mn+n-1  [call this condition Fred]

but 2^m >= 2, m <= n, so this implies

  2^n <= n^2 + n - 1

  2^n < n(n+1).

This is only true for n = 2 (proof left to reader), so m = 1 or 2.  But then
we can use the stronger condition Fred to get a contradiction.
1942.2Hey whatHERON::BUCHANANEt tout sera bien etMon Feb 27 1995 11:195
>Since no two sums of xi are equal

	How do you get this?

Andrew
1942.3Re: .2FLOYD::YODERMFYMon Feb 27 1995 13:342
The statement is an error.  I'm not sure where it came from now, as I discarded
my notes after entering the "solution."  Consider the problem reopened.