wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Average condition implies sequence is constant
        
(Message started by: ecoist on Feb 28^th, 2006, 9:21pm)

Title: Average condition implies sequence is constant
Post by ecoist on Feb 28^th, 2006, 9:21pm

A certain sequence of 100 real numbers has the property that, for every subsequence of 8 of these numbers, there exists a subsequence of 9 of these numbers with the same average as the 8. Show that the entire sequence is constant.

(Appeared in sci.math. I seem to be the only one in posession of an elementary proof. Who else belongs to this club?)

Title: Re: Average condition implies sequence is constant
Post by Icarus on Mar 1^st, 2006, 4:04pm

Are you sure there isn't a flaw in your elementary proof? I have come up with a couple of elementary "almost" proofs, that trip up on subtleties.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Mar 1^st, 2006, 5:06pm

Good point. However, I have worked on this for years without success, until now. I have also seen a very clever, but not elementary, proof.

What finally enabled me to prove this with an elementary argument was seeing a proof of the following similar problem.

[hideb]You have 11 weights with the property that, after removing any one of the weights, the remaining 10 weights can be split into two groups of 5 weights each which balance on a scale. Must then all the weights be the same?[/hideb]

Title: Re: Average condition implies sequence is constant
Post by ecoist on Mar 1^st, 2006, 5:15pm

Sorry. My reply probably did not convince you that my proof is correct. It is. It has been checked by experts.

I hope you can solve the problem without looking at the similar problem (although it is a very weak hint).

Title: Re: Average condition implies sequence is constant
Post by Icarus on Mar 1^st, 2006, 5:32pm

I wasn't particularly doubting you, either. I don't have enough information to say one way or another. It just seemed a possibility, particularly given that my first thoughts failed on a some-what subtle point. Since I don't know your math skills, I didn't know if perhaps you had missed that or a similar flaw.

After a suitable time has passed for our own attempts, I look forward to seeing your proof.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jun 28^th, 2006, 9:12pm

Is it time for a hint? This is a really nice problem and a hint might spoil things for those who want no help. Besides, the only hint I can think of could be a near giveaway.

Title: Re: Average condition implies sequence is constant
Post by Barukh on Jun 28^th, 2006, 11:54pm

on 06/28/06 at 21:12:34, ecoist wrote:

Is it time for a hint?

It probably is.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jun 30^th, 2006, 8:37pm

Ok, Barukh, but I'm afraid that this hint may be too big. Assume first that all 100 numbers in the sequence are integers.

Title: Re: Average condition implies sequence is constant
Post by Icarus on Jul 1^st, 2006, 12:21pm

I don't have a complete proof yet, but it looks like you can show that if the sequence has at least 2 values, then you can force a never-ending series of new values from those two using the average rule. Since the sequence is finite, this is impossible.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 2^nd, 2006, 11:25am

Icarus' proof outline made me wonder where finiteness comes in in my proof (not really my proof, a correction of someone's flawed but lovely proof). It turns out that, if the sequence consists of integers, it is constant even when the sequence is infinite. My proof requires finiteness only to extend the proof from integer sequences to real number sequences.

This is what fascinates me about this problem. I know of no other fact about real numbers whose proof depends on results from the theory of integers. Maybe Icarus will show that this problem doesn't depend on the integers either.

Title: Re: Average condition implies sequence is constant
Post by Barukh on Jul 4^th, 2006, 12:36am

I've got a question: Does the situation changes if we replace parameters 8 and 9 to 1 and 2 accordingly?

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 4^th, 2006, 9:45am

My proof crumbles with 1 and 2, Barukh. But it continues to work if 8 and 9 are replaced by, resp., a>1 and b relatively prime to a (recently noticed that it suffices if a>1 and a does not divide b).

Title: Re: Average condition implies sequence is constant
Post by pex on Jul 4^th, 2006, 9:55am

on 07/04/06 at 09:45:51, ecoist wrote:

My proof crumbles with 1 and 2, (...)

..., as it should, since a sequence with 50 x's and 50 y's does the trick.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 4^th, 2006, 10:28am

Good point, pex. Your example shows that the result is also false if a divides b (provided a and b are small enough relative to 100).

Title: Re: Average condition implies sequence is constant
Post by Icarus on Jul 5^th, 2006, 8:16pm

on 07/02/06 at 11:25:17, ecoist wrote:

I know of no other fact about real numbers whose proof depends on results from the theory of integers.

Sorry that I haven't done more. I've had too much to think about lately and haven't been inclined to get too deep into this as a result. But I would like to point out that in some sense all results about real numbers depend on the theory of integers, since you can develop the real numbers and all their properties from the theory of integers.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 5^th, 2006, 9:32pm

Naturally, I am anxious to see what you guys come up with, but I can be patient. This problem is well worth the wait.

Of course you are right, Icarus, but I doubt if anyone thinks that the mean value theorem is a consequence of number theory. Its proof certainly does not make explicit use of any purely number-theoretic results. That said, the only proofs I know of this problem make direct use of number theory. Moreover, even after the problem is solved for integer sequences, the first proof I saw had to invoke some relatively advanced mathematics to extend the result from integer sequences to real number sequences. My contribution eliminates the esoteric math.

I can state that bit of esoteric math if someone wants a second hint.

Title: Re: Average condition implies sequence is constant
Post by Michael_Dagg on Jul 7^th, 2006, 6:18am

By "subsequence" of 8 do you mean 8 _consecutive_
elements of the sequence?

Same question for the subsequence of 9 of these numbers...

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 7^th, 2006, 9:23am

The subsequences of lengths 8 and 9 need not be consecutive. Pretty strong assumption given the seemingly milder assumption of the related problem I mentioned early in this thread. Now I realize that one can assume the condition applies to only consecutive subsequences of length 8, provided wraparound is allowed and the length of the whole sequence is 101 instead of 100.

Title: Re: Average condition implies sequence is constant
Post by JP05 on Jul 9^th, 2006, 4:31pm

Let me ask a question here:

For example, let A = {1, 2, 3, 4, 5, 6, 7, 8} and B = {11, 1, 13, 14, 2, 3, 10, 4, 22, 5, 6, 7, 19, 22, 8, 43,..., --> the reset of the numbers up to 100 of them}.

I know the numbers can be real numbers but I just used integers and I know the set A does not have to have 1-8 as shown.

So A is a subsequence of B by your rules?

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 9^th, 2006, 6:40pm

The important thing, JP05, is that a number can appear more than once among the 100 numbers. I could have used the term multiset instead of sequence but I thought readers would find the latter more readable. So, your example would be more accurate if you allowed A to have repeated numbers and B to contain all the elements of A, including all of its repeats. For example, A={1,1,1,2,2,2,2,3} and B=(17, 3, 2,1,-7,2,1,1,2,4,13,...,2,...}. Note that the ordering of the elements doesn't matter, just their presence including multiplicities.

Title: Re: Average condition implies sequence is constant
Post by JP05 on Jul 9^th, 2006, 7:20pm

Does seem difficult from my view probably because I do not have the artillery to solve it. It kinda makes me think of some exotic triangle number problem.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 9^th, 2006, 9:28pm

It is indeed a difficult problem but, surprisingly (given the first solution I saw), no more than high school mathematics is required.

Title: Re: Average condition implies sequence is constant
Post by JP05 on Jul 10^th, 2006, 8:24pm

Thanks but I wouldn't know where to start with this one. Seems to me that if it is true for 100 real numbers then it should be true for 1000 real numbers.

Expect one of the hard-hitters to get it.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jul 10^th, 2006, 9:15pm

You are not alone, JP05, and you are right. The number 100 is not sacred; any length sequence will do. As I assume Icarus did, I was able to prove that the 9 smallest (or 9 largest) numbers are all equal, but I couldn't extend this to all 100 numbers (hence, if there were only 17 numbers altogether, we are done). Everyone has his own unique way of looking at things. Maybe the similar problem I hid in an earlier post will seem more accessible to you. If you can solve it, this problem may look more manageable, as it did for me.

It never ocurred to me to assume first that the 100 numbers were integers. If it had ocurred to me, maybe I could have made some progress. But, since the "hard-hitters" have yet to put this baby to bed, I probably would have still failed to make any headway. Polya wrote that sometimes a more general problem is easier to solve. It turns out that this problem remains true if the 100 numbers are complex numbers.

Title: Re: Average condition implies sequence is constant
Post by James Fingas on Jul 25^th, 2006, 10:57am

Start of a solution:
[hideb]Form all the different average values that can be formed by choosing 8 numbers from the set. Take the largest and call it A.

Now find the selection of 9 numbers a₁, a₂, ... a₉, that has the average A. Find the smallest of those 9, call it a_i, and take it away from the set. Now you have a set of 8 numbers, with an average value of 9A/8 - a_i/8. Since A is the largest average we can have, we know that:

A >= 9A/8 - a_i/8
0 >= A/8 - a_i/8
a_i >= A

Because a_i is the smallest in the set, we know that it cannot be larger than the average:

a_i <= A

Hence a_i = A, which is a way of saying that the set of 100 must have at least 9 copies of A in it.[/hideb]

Title: Re: Average condition implies sequence is constant
Post by Deedlit on Aug 1^st, 2006, 2:43pm

Well, here's a solution that works for rationals:

[hideb]
Let a₁ be the minimum value. Let a_i be the value such that the order of 2 in a_i - a₁ is minimal - that is, there does not exist j and k such that 2^k (a_i - a₁) is integral but 2^k (a_j - a₁) is not. Choose our set to be 7 values equal to a₁ (as ecoist has said, at least 9 values are equal to a₁) and one value equal to a_i. Then there must be a set of 9 values with the same average, meaning their sum is 9 a₁ + 9/8 (a_i- a₁), and the sum of their values minus a₁ is 9/8 (a_i- a₁). That has a lower order of 2 than a_i - a₁, and so for some member a_j of the 9-element set, a_j - a₁has a lower order of 2. This contradicts our choice of a_i.

[/hideb]

Unfortunately, this strategy is not much use for the reals. The same is true for the other problem mentioned - there's a simple solution involving divisibility that doesn't translate to the reals, even though it's still true.

Title: Re: Average condition implies sequence is constant
Post by Icarus on Aug 1^st, 2006, 3:22pm

Nice, though your definition of minimal order of 2 does not work: 2^k(1/3) is never integral, but, 1/2 has a lower order. I suggest defining the order directly:

If x = 2ⁿ(p/q), where p & q are both odd, and n may be any integer, then the "order of 2 in x" is n.

Title: Re: Average condition implies sequence is constant
Post by Deedlit on Aug 1^st, 2006, 3:47pm

Yes, thank you, Icarus. Also, I should clarify that the order of 2 in 0 is infinity.

I just thought of a solution for an arbitrary set of integers:

[hideb]
Given a set S of integers, not all identical. If all members of S are equal to i mod 8, then we apply the function f(x) = (x - i) / 8 to the set S. Note that a linear mapping does not affect the problem condition, since all averages are simply affected by the same linear mapping. We keep applying the process until not all members of S are equal mod 8; this must eventually happen, since the minimum distance between elements of S is divided by 8 each time.

Let x and y be elements of S that are unequal modulo 8. Let T be any other seven elements; then the sums T U {x} and T U {y} differ modulo 8 as well, so at least one is not divisible by 8. There can be no 9 element set with the same average, as the sum would have to be nonintegral.

[/hideb]

Of course, the same statement doesn't hold for the rationals or larger, as the rationals trivially satisfy the required condition.

I guess this isn't the elementary proof that ecoist is talking about, as it doesn't look like this proof can be extended to the reals either.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Aug 1^st, 2006, 6:46pm

Deedlit, believe it or not, your two solutions can each be completed to a full, still elementary, solution (which completion is the only part of the solution for which I had no help). The argument for the reals changes, but it begins with what you have proved (hint?). Even the non-elementary solution I saw begins where you left off. (Also, your second solution for integers contains what's needed to extend it to the rationals.)

Title: Re: Average condition implies sequence is constant
Post by Deedlit on Aug 1^st, 2006, 8:43pm

It's funny, it took me all of three minutes after reading your post to realize what I needed to do. Before, I didn't think the above approach was right for the reals and just didn't pursue it.

[hideb]
Given a finite set S of reals, let V be the vector space over Q generated by S. Choose a basis for V such that all elements of S have integral coordinates. By the previous argument, we can perform linear transformations of the form f(v) = (v-a) / 8 until S is not identical mod 8 on every coordinate. As before, we find two sets T U {x} and T U {y} such that the sum at least one is not divisible by 8 on some coordinate; then it cannot have the same average as any 9-element set.

The finiteness is required so that we can make every element have integral coordinates, but the proof works fine for any subset of Z^S for any set S.
[/hideb]

Title: Re: Average condition implies sequence is constant
Post by ecoist on Aug 1^st, 2006, 9:18pm

Ok, Deedlit, it appears that you have a complete solution which requires knowledge not usually available to high school students. You are the first solver. Can you now supply a proof accessible to high school students? You then will be the most esteemed member of the club of solvers with an elementary solution because I failed to accomplish what you did without help.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Aug 14^th, 2006, 5:08pm

Ok, here's a change to the last step of Deedlit's solution that is accessible to high school students. The change begins after it is proved that the result holds for rationals.

[hideb]The fact that the result holds for rationals implies that the 100 numbers satisfy a rational linear homogeneous system of (100 choose 8) equations in 100 unknowns of rank 99! But then the only real solutions of the system are also all 100 of the real numbers are equal.[/hideb]

Title: Re: Average condition implies sequence is constant
Post by Deedlit on Aug 25^th, 2006, 10:38pm

Hmmm... I would have to say this really doesn't look more accessible. I'd say we are trying to explain more or less the same idea - how accessible it is to high school students depends on how well we can take standard concepts in linear algebra, and present them to a high school student by avoiding the terminology by explaining everything in detail. (i.e. avoid "rational linear homogenous equation" or he'll run away screaming.) It's probably a tomato - toomato thing.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Aug 26^th, 2006, 10:01am

Maybe you are right, but I don't think so. Since a rational solution consists of all multiples of a single vector, the echelon form of the matrix of the system has such a form that all solutions, including real solutions, can be easily read off. No need to even hint at the fact that linearly independent vectors in Fⁿ remain independent in Eⁿ, where E is any extension field of F.

Title: Re: Average condition implies sequence is constant
Post by ecoist on Jan 16^th, 2007, 9:54pm

Then, again, Deedlit, I may have to stand corrected. Here's a proof of:

You have 11 weights with the property that, after removing any one of the weights, the remaining 10 weights can be split into two groups of 5 weights each which balance on a scale. Must then all the weights be the same?

The proof is based on Aryabhatta's proof for "Devil Matrix".

Let A be the 11x11 matrix indexed by the 11 weights. In the i'th row of A, for i=1,...,11, set the entry in the i-th column to 0, put 1's for the 5 weights on the left pan of the scale, and put (-1)'s for the 5 weights on the right pan of the scale, which two groups of weights balance on the scale. Then the vector v, whose entries are the 11 weights, satisfies Av=0. Let A₂ be A reduced modulo 2. Then A₂=J-I(mod 2), where J is the matrix of all 1's and I is the identity matrix. A la Aryabhatta, since A₂-J=-I(mod 2), it follows that rank(A₂)+rank(-J)>rank(-I); whence rank(A₂)>11-1=10. Since the vector of all 1's annihilates A₂, the rank of A₂ equals 10; whence the rank of A equals 10. Hence all weights must be the same weight.