Author |
Topic: Average condition implies sequence is constant (Read 2319 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Average condition implies sequence is constant
« on: Feb 28th, 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 1st, 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 1st, 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 1st, 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 1st, 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 1st, 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 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:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #5 on: Jun 28th, 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 28th, 2006, 11:54pm » |
Quote Modify
|
on Jun 28th, 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 30th, 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 1st, 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 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:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #9 on: Jul 2nd, 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 4th, 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 4th, 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 4th, 2006, 9:55am » |
Quote 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:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #13 on: Jul 4th, 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 5th, 2006, 8:16pm » |
Quote 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:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #15 on: Jul 5th, 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 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:
Posts: 500
|
|
Re: Average condition implies sequence is constant
« Reply #16 on: Jul 7th, 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 7th, 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 7th, 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 9th, 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 1-8 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 9th, 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 9th, 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 9th, 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 10th, 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 hard-hitters to get it.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #23 on: Jul 10th, 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 "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
Gender:
Posts: 949
|
|
Re: Average condition implies sequence is constant
« Reply #24 on: Jul 25th, 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 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?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print