Author 
Topic: Average condition implies sequence is constant (Read 2342 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


Average condition implies sequence is constant
« on: Feb 28^{th}, 2006, 9:21pm » 
Quote Modify

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?)

« Last Edit: Mar 1^{st}, 2006, 6:02am by ecoist » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Average condition implies sequence is constant
« Reply #1 on: Mar 1^{st}, 2006, 4:04pm » 
Quote Modify

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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #2 on: Mar 1^{st}, 2006, 5:06pm » 
Quote Modify

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. hidden:  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? 


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #3 on: Mar 1^{st}, 2006, 5:15pm » 
Quote Modify

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).


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Average condition implies sequence is constant
« Reply #4 on: Mar 1^{st}, 2006, 5:32pm » 
Quote Modify

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 somewhat 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #5 on: Jun 28^{th}, 2006, 9:12pm » 
Quote Modify

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.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Average condition implies sequence is constant
« Reply #6 on: Jun 28^{th}, 2006, 11:54pm » 
Quote Modify

on Jun 28^{th}, 2006, 9:12pm, ecoist wrote: It probably is.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #7 on: Jun 30^{th}, 2006, 8:37pm » 
Quote Modify

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


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Average condition implies sequence is constant
« Reply #8 on: Jul 1^{st}, 2006, 12:21pm » 
Quote Modify

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 neverending series of new values from those two using the average rule. Since the sequence is finite, this is impossible.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #9 on: Jul 2^{nd}, 2006, 11:25am » 
Quote Modify

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.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Average condition implies sequence is constant
« Reply #10 on: Jul 4^{th}, 2006, 12:36am » 
Quote Modify

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


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #11 on: Jul 4^{th}, 2006, 9:45am » 
Quote Modify

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).


IP Logged 



pex
Uberpuzzler
Gender:
Posts: 880


Re: Average condition implies sequence is constant
« Reply #12 on: Jul 4^{th}, 2006, 9:55am » 
Quote Modify

on Jul 4^{th}, 2006, 9:45am, 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.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #13 on: Jul 4^{th}, 2006, 10:28am » 
Quote Modify

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).


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Average condition implies sequence is constant
« Reply #14 on: Jul 5^{th}, 2006, 8:16pm » 
Quote Modify

on Jul 2^{nd}, 2006, 11:25am, 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #15 on: Jul 5^{th}, 2006, 9:32pm » 
Quote Modify

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 numbertheoretic 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.


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Average condition implies sequence is constant
« Reply #16 on: Jul 7^{th}, 2006, 6:18am » 
Quote Modify

By "subsequence" of 8 do you mean 8 _consecutive_ elements of the sequence? Same question for the subsequence of 9 of these numbers...

« Last Edit: Jul 7^{th}, 2006, 6:20am by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #17 on: Jul 7^{th}, 2006, 9:23am » 
Quote Modify

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.


IP Logged 



JP05
Guest


Re: Average condition implies sequence is constant
« Reply #18 on: Jul 9^{th}, 2006, 4:31pm » 
Quote Modify
Remove

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 18 as shown. So A is a subsequence of B by your rules?


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #19 on: Jul 9^{th}, 2006, 6:40pm » 
Quote Modify

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.


IP Logged 



JP05
Guest


Re: Average condition implies sequence is constant
« Reply #20 on: Jul 9^{th}, 2006, 7:20pm » 
Quote Modify
Remove

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.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #21 on: Jul 9^{th}, 2006, 9:28pm » 
Quote Modify

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


IP Logged 



JP05
Guest


Re: Average condition implies sequence is constant
« Reply #22 on: Jul 10^{th}, 2006, 8:24pm » 
Quote Modify
Remove

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 hardhitters to get it.


IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #23 on: Jul 10^{th}, 2006, 9:15pm » 
Quote Modify

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 "hardhitters" 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.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Average condition implies sequence is constant
« Reply #24 on: Jul 25^{th}, 2006, 10:57am » 
Quote Modify

Start of a solution: hidden:  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_{1}, a_{2}, ... a_{9}, 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. 


IP Logged 
Doc, I'm addicted to advice! What should I do?



