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

Deedlit
Senior Riddler
Posts: 476


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

Well, here's a solution that works for rationals: hidden:  Let a_{1} be the minimum value. Let a_{i} be the value such that the order of 2 in a_{i}  a_{1} is minimal  that is, there does not exist j and k such that 2^k (a_{i}  a_{1}) is integral but 2^k (a_{j}  a_{1}) is not. Choose our set to be 7 values equal to a_{1} (as ecoist has said, at least 9 values are equal to a_{1}) 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_{1} + 9/8 (a_{i } a_{1}), and the sum of their values minus a_{1} is 9/8 (a_{i } a_{1}). That has a lower order of 2 than a_{i}  a_{1}, and so for some member a_{j} of the 9element set, a_{j}  a_{1 }has a lower order of 2. This contradicts our choice of a_{i}.  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 1^{st}, 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 1^{st}, 2006, 3:22pm » 
Quote Modify

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^{n}(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 1^{st}, 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 1^{st}, 2006, 3:54pm by Deedlit » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Average condition implies sequence is constant
« Reply #28 on: Aug 1^{st}, 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 nonelementary 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 1^{st}, 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) = (va) / 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 9element 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 1^{st}, 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 14^{th}, 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 25^{th}, 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 26^{th}, 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 F^{n} remain independent in E^{n}, 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 16^{th}, 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 ith 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_{2} be A reduced modulo 2. Then A_{2}=JI(mod 2), where J is the matrix of all 1's and I is the identity matrix. A la Aryabhatta, since A_{2}J=I(mod 2), it follows that rank(A_{2})+rank(J)>rank(I); whence rank(A_{2})>111=10. Since the vector of all 1's annihilates A_{2}, the rank of A_{2} equals 10; whence the rank of A equals 10. Hence all weights must be the same weight.


IP Logged 



