From - Mon Apr 27 19:07:17 1998 From: Robin Chapman Newsgroups: sci.math Subject: Re: asking putnam problem 1993A4 Date: Mon, 27 Apr 1998 02:42:49 -0600 Organization: University of Exeter > > I would like to ask about putnam problem 1993A4. > > x_1,...,x_{19} are positive integers such that x_i<=93, y_1,...,y_{93} are > positive integers such that y_j<=19.Prove there is a sum of some x_i equal > to a sum of some y_j > > I want to know whether the x_i and y_j can be repeated. For example > x_1+x_1+x_2=y_1+y_1+y_2+y_2+y_3 (x_1, y_1 and y_2 are repeated). > No. [SPOILER ALERT] Of course 19 and 93 are not important here. Suppose that x_1,...,x_n are positive integers of size at most m and y_1,...,y_m are positive integers of size at most n. We shall show that some sum of the x_j s equals some sum of the y_k s. Let s_j = x_1 + x_2 + ... + s_j (0 <= j <= n) and t_k = y_1 + y_2 + ... + y_k (0 <= k <= n). If s_n = t_m we're done, so suppose without loss of generality that t_m < s_n = S say. Note that S <= mn. Consider the numbers s_j - t_k for 0 < j <= n and 0 <= k <= m (NB the inequalities). There are n(m + 1) > S of these. If any equal zero then t_k = s_j > 0 and we are done so we may suppose not. By the pigeonhole principle there are two which are congruent modulo S say s_j - t_k = s_u - t_v (mod S) or s_j - s_u = t_k - t_v (mod S). Both sides are strictly less than S in absolute value, and we may suppose k > v (equality menas both sides vanish and so k = v and j = u). Either (1) s_j - s_u = t_k - t_v, i.e., x_{u+1}+ ... + x_j = y_{v+1} + ... + y_j, or (2) s_j - s_u + S = t_k - t_v in which case x_1 + ... + x_u + x_{j+1} + ... + x_n = y_{v+1} + ... + y_j. Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading you can find the solution in the October 1994 issue of the Amer. Math. Monthly.