wu :: forums
« wu :: forums - Average condition implies sequence is constant »

Welcome, Guest. Please Login or Register.
Nov 4th, 2024, 7:04pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: william wu, Eigenray, Grimbal, towr, Icarus, SMQ)
   Average condition implies sequence is constant
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Average condition implies sequence is constant  (Read 2337 times)
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Average condition implies sequence is constant  
« on: Feb 28th, 2006, 9:21pm »
Quote Quote Modify 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 1st, 2006, 6:02am by ecoist » IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Average condition implies sequence is constant  
« Reply #1 on: Mar 1st, 2006, 4:04pm »
Quote Quote Modify 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #2 on: Mar 1st, 2006, 5:06pm »
Quote Quote Modify 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #3 on: Mar 1st, 2006, 5:15pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Average condition implies sequence is constant  
« Reply #4 on: Mar 1st, 2006, 5:32pm »
Quote Quote Modify 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 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.
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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #5 on: Jun 28th, 2006, 9:12pm »
Quote Quote Modify 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: male
Posts: 2276
Re: Average condition implies sequence is constant  
« Reply #6 on: Jun 28th, 2006, 11:54pm »
Quote Quote Modify Modify

on Jun 28th, 2006, 9:12pm, ecoist wrote:
Is it time for a hint?

It probably is.
IP Logged
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #7 on: Jun 30th, 2006, 8:37pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Average condition implies sequence is constant  
« Reply #8 on: Jul 1st, 2006, 12:21pm »
Quote Quote Modify 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 never-ending 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #9 on: Jul 2nd, 2006, 11:25am »
Quote Quote Modify 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: male
Posts: 2276
Re: Average condition implies sequence is constant  
« Reply #10 on: Jul 4th, 2006, 12:36am »
Quote Quote Modify 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #11 on: Jul 4th, 2006, 9:45am »
Quote Quote Modify 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: male
Posts: 880
Re: Average condition implies sequence is constant  
« Reply #12 on: Jul 4th, 2006, 9:55am »
Quote Quote Modify Modify

on Jul 4th, 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #13 on: Jul 4th, 2006, 10:28am »
Quote Quote Modify 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: male
Posts: 4863
Re: Average condition implies sequence is constant  
« Reply #14 on: Jul 5th, 2006, 8:16pm »
Quote Quote Modify Modify

on Jul 2nd, 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #15 on: Jul 5th, 2006, 9:32pm »
Quote Quote Modify 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 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.
IP Logged
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Average condition implies sequence is constant  
« Reply #16 on: Jul 7th, 2006, 6:18am »
Quote Quote Modify 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 7th, 2006, 6:20am by Michael Dagg » IP Logged

Regards,
Michael Dagg
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #17 on: Jul 7th, 2006, 9:23am »
Quote Quote Modify 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

Email

Re: Average condition implies sequence is constant  
« Reply #18 on: Jul 9th, 2006, 4:31pm »
Quote Quote Modify Modify Remove 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 1-8 as shown.
 
So A is a subsequence of B by your rules?
IP Logged
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #19 on: Jul 9th, 2006, 6:40pm »
Quote Quote Modify 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

Email

Re: Average condition implies sequence is constant  
« Reply #20 on: Jul 9th, 2006, 7:20pm »
Quote Quote Modify Modify Remove 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: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #21 on: Jul 9th, 2006, 9:28pm »
Quote Quote Modify 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

Email

Re: Average condition implies sequence is constant  
« Reply #22 on: Jul 10th, 2006, 8:24pm »
Quote Quote Modify Modify Remove 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 hard-hitters to get it.
IP Logged
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Re: Average condition implies sequence is constant  
« Reply #23 on: Jul 10th, 2006, 9:15pm »
Quote Quote Modify 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 "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.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Average condition implies sequence is constant  
« Reply #24 on: Jul 25th, 2006, 10:57am »
Quote Quote Modify 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 a1, a2, ... a9, that has the average A. Find the smallest of those 9, call it ai, and take it away from the set. Now you have a set of 8 numbers, with an average value of 9A/8 - ai/8. Since A is the largest average we can have, we know that:
 
A >= 9A/8 - ai/8
0 >= A/8 - ai/8
ai >= A
 
Because ai is the smallest in the set, we know that it cannot be larger than the average:
 
ai <= A
 
Hence ai = 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?
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board