From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: A hard problem ..... Date: 21 Feb 2001 02:14:12 GMT Newsgroups: sci.math Summary: Rational linear algebra solves combinatorial averaging problem In article , Ken Pledger wrote: >Consider a sequence of 8 real numbers, and suppose that for each >subsequence of 2 members there exists some subsequence of three members >having the same average. Why are all 8 numbers equal? Suppose not. Order by size. Apply a linear transformation so min=0, max=1. Apply hypothesis to two largest to discover three largest are equal; likewise three smallest are equal. So the numbers are 0,0,0,x,y,1,1,1 Now make a tree of all possible averages of two and all possible averages of three. Show that the averages of 0,x,1 and 0,y,1 are the only 3-way averages which can lie between those of 0,0,1 and 0,1,1; thus one of them must be the 2-way average of 0,1. That is, either x=1/2 or y=1/2. By symmetry, assume the latter. Then what's left of the tree of 2-way averages is 1/2 / \ 0 < x/2 < 1/4 (1+x)/2 < 3/4 < 1 \ / x/2 + 1/4 Try each of the candidate 3-way averages to match the "1/4", say, and solve for x in each case; I find that in no case does any 3-way average equal 3/4. This is a quick and unenlightening examination of cases; I think it solves the reduced problem without addressing the original one. dave ============================================================================== From: Gerry Myerson Subject: Re: A hard problem ..... Date: Wed, 21 Feb 2001 15:55:17 +1000 Newsgroups: sci.math Summary: [missing] In article <96u2jp$jem$1@wanadoo.fr>, "julien.santini" wrote: > There are 100 REAL numbers.If for any 8 numbers (selected from this > set) with average t we can find 9 numbers (in this set) such that the > average of these 9 numbers is t, prove that these 100 numbers are > equal. > > (of course if the numbers are rational the problem isn't too difficult) Suppose you've got 100 reals with the averaging property. Write down all the equations implied by the averaging property; that's a long-but-finite list of linear equations with rational coefficients. The solutions form a vector space determined by rational conditions, so, if there's a real solution, there's a rational solution. The averaging property is invariant under multiplying through by a constant, so, if there's a rational solution, then there's an integral solution obtained by multiplying through by a common denominator. We may use the least common denominator, so the 100 integers have no common factor exceeding one. Thus, you can't have only even integers. Since 8 & 9 are relatively prime the averages must all be integers. You can't have both even and odd integers, lest some sum of 8 be odd, so you must have only odd integers. Then they must all be congruent mod 8, lest some sum of 8 not be divisible by 8. Suppose each is congruent to t mod 8. Then from 9(a_1 + ... + a_8) = 8(b_1 + ... + b_9) we get 9(a_1 + ... + a_8) congruent 72t mod 64, or a_1 + ... + a_8 congruent 8t mod 64. But this forces all the integers to be congruent mod 64. Iterate this argument to force them all to be congruent to an arbitrarily high power of 8. Then they must be equal. Gerry Myerson (gerry@mpce.mq.edu.au) ============================================================================== From: taga@news.uni-rostock.de (Dr. Michael Ulm) Subject: Re: A hard problem ..... Date: 22 Feb 2001 09:39:48 +0100 Newsgroups: sci.math On Tue, 20 Feb 2001 16:25:35 +0100, julien.santini wrote: >There are 100 REAL numbers.If for any 8 numbers (selected from this set) >with average t we can find 9 numbers (in this set) such that the average of >these 9 numbers is t, prove that these 100 numbers are equal. > >(of course if the numbers are rational the problem isn't too difficult) Let the sequence be a_1 <= a_2 <= ... <= a_100. Since the problem is invariant under affine transformations, we may assume that the smallest number a_1 = 0. It is easy to show, that this number must occur at least nine times, so a_1 = a_2 = ... = a_9 = 0. Now let n+1 be the dimension of the span of all numbers a_i over the field of rationals Q. This means, there exist n irrational numbers z_1, ... z_n which are linearly independent over Q, such that for every index k in [1,100] there exist rational numbers b_kl with l in [0,n] such that a_k = b_k0 + z_1 b_k1 + z_2 b_k2 + ... + z_n b_kn. We now assume, that a_100 > 0. Since all b_kl are rational, we may scale the sequence a_k so, that all b_kl are integers such that the greatest common divisor of all b_kl is 1. So, there must be some index kl such that b_kl is an odd number. Take the average of the numbers a_1, a_2,... a_7 and a_k, which is a_k/8. The coefficient of z_l in this average is b_kl/8. From the averaging property we know that there must be some integer n such that b_kl/8 = n/9, which implies 9 b_kl = 8 n. This is a contradiction, since 9 b_kl is odd and 8 n is even. HTH, Michael. -- &&&&&&&&&&&&&&&&#@#&&&&&&&&&&&&&&&& Dr. Michael Ulm FB Mathematik, Universitaet Rostock taga@hades.math.uni-rostock.de ============================================================================== From: Gerhard Woeginger Subject: Re: A hard problem ..... Date: 22 Feb 2001 10:28:39 GMT Newsgroups: sci.math julien.santini wrote: > There are 100 REAL numbers.If for any 8 numbers (selected from this set) > with average t we can find 9 numbers (in this set) such that the average of > these 9 numbers is t, prove that these 100 numbers are equal. > (of course if the numbers are rational the problem isn't too difficult) > > /rocco There are 1000 real numbers. For any 12 numbers with average t we can find 18 numbers that also have average t. Prove that these 1000 numbers all are equal. -Gerhard ============================================================================== From: Ayatollah Potassium Subject: Re: A hard problem ..... (averaging vectors) Date: Thu, 08 Mar 2001 16:41:53 -0500 Newsgroups: sci.math Ken Pledger wrote: > > > There are 100 REAL numbers.If for any 8 numbers (selected from this > > > set) with average t we can find 9 numbers (in this set) such that the > > > average of these 9 numbers is t, prove that these 100 numbers are > > > equal. Call the numbers (or vectors) a_i. The point is that (a) 8/9 has a numerator > 1, that is, 8 is not divisible by 9 (b) For the vector of differences w_i = a_i - a_0, averaging property implies w = 8/9Mw where M is some integer matrix. This forces w=0, either by infinite iteration (w--> 8Mw/9 is an 8-adic contraction), or by reduction mod 8: det(9-8M) = det (9) mod 8 is nonzero. (c) if a_i live in an abelian group rather than a vector space there are still no nontrivial solutions, because 8 and 9 are relatively prime. (If the numbers were 12 and 18 the a_i's could be modified by some 6-torsion elements to produce a new solution). So, the conclusion is that (100,8,9) can be replaced by (N,p,q) with p>2, provided p is not divisible by q (for a_i chosen from a vector space) or (p,q)=1 (for a_i chosen from an abelian group). > But has anyone yet penetrated the real nature of the problem (what > 18th-century mathematicians might have called "the true metaphysics" of > it)? Is the fact that 8 and 9 are relatively prime really crucial? I would identify the 'true metaphysics' as the following lemma. It avoids any nonconstructive argument about descent to the case of rational numbers. Let L be a square matrix with rational coefficients all divisible by some given number (in this case, 8/9). Then the equation v=Lv has only the trivial solution.