| 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 |
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.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1942.1 | pigeonhole principle strikes again | FLOYD::YODER | MFY | Fri Feb 24 1995 14:51 | 17 |
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.2 | Hey what | HERON::BUCHANAN | Et tout sera bien et | Mon Feb 27 1995 08:19 | 5 |
>Since no two sums of xi are equal How do you get this? Andrew | |||||
| 1942.3 | Re: .2 | FLOYD::YODER | MFY | Mon Feb 27 1995 10:34 | 2 |
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. | |||||