Author |
Topic: Average condition implies sequence is constant (Read 2320 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Re: Average condition implies sequence is constant
« Reply #25 on: Aug 1st, 2006, 2:43pm » |
 Quote  Modify
|
Well, here's a solution that works for rationals:
| hidden: |
Let a1 be the minimum value. Let ai be the value such that the order of 2 in ai - a1 is minimal - that is, there does not exist j and k such that 2^k (ai - a1) is integral but 2^k (aj - a1) is not. Choose our set to be 7 values equal to a1 (as ecoist has said, at least 9 values are equal to a1) and one value equal to ai. Then there must be a set of 9 values with the same average, meaning their sum is 9 a1 + 9/8 (ai - a1), and the sum of their values minus a1 is 9/8 (ai - a1). That has a lower order of 2 than ai - a1, and so for some member aj of the 9-element set, aj - a1 has a lower order of 2. This contradicts our choice of ai.
|
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.
|
| « Last Edit: Aug 1st, 2006, 2:47pm by Deedlit » |
 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 #26 on: Aug 1st, 2006, 3:22pm » |
Quote Modify
|
Nice, though your definition of minimal order of 2 does not work: 2k(1/3) is never integral, but, 1/2 has a lower order. I suggest defining the order directly:
If x = 2n(p/q), where p & q are both odd, and n may be any integer, then the "order of 2 in x" is n.
|
|
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
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Average condition implies sequence is constant
« Reply #27 on: Aug 1st, 2006, 3:47pm » |
Quote Modify
|
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:
| hidden: |
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.
|
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.
|
| « Last Edit: Aug 1st, 2006, 3:54pm by Deedlit » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #28 on: Aug 1st, 2006, 6:46pm » |
Quote Modify
|
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.)
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Average condition implies sequence is constant
« Reply #29 on: Aug 1st, 2006, 8:43pm » |
Quote Modify
|
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.
| hidden: |
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.
|
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #30 on: Aug 1st, 2006, 9:18pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #31 on: Aug 14th, 2006, 5:08pm » |
Quote Modify
|
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.
| hidden: | | 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. |
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Average condition implies sequence is constant
« Reply #32 on: Aug 25th, 2006, 10:38pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #33 on: Aug 26th, 2006, 10:01am » |
Quote Modify
|
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 Fn remain independent in En, where E is any extension field of F.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Average condition implies sequence is constant
« Reply #34 on: Jan 16th, 2007, 9:54pm » |
Quote Modify
|
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 A2 be A reduced modulo 2. Then A2=J-I(mod 2), where J is the matrix of all 1's and I is the identity matrix. A la Aryabhatta, since A2-J=-I(mod 2), it follows that rank(A2)+rank(-J)>rank(-I); whence rank(A2)>11-1=10. Since the vector of all 1's annihilates A2, the rank of A2 equals 10; whence the rank of A equals 10. Hence all weights must be the same weight.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print