Artefactual coattail (Part 2)

Hmm, I realized explaining all of these is a bit more lengthy than I thought, and I have no intention of doing it all in one sitting. So I'll do it 2 at a time - #3 and #4 will either come later today or tomorrow.

EDIT: Darn, writing at a computer seems to make you verbose. I'm fairly sure I probably could have solved this a bit quicker. Regardless, there are nice ideas that I'll end up using again in #3 and #4.

Generalization 1:

Because of the symmetry, we can take , and is the max element.

Claim: An (n,k) system can have no excess iff we can form a n-gon with sides , or equivalently: .

Proof:

First, note that the algebraic inequality in the problem statement is simply the Generalized Triangle Inequality (bottom of http://mathworld.wolfram.com/TriangleInequality.html) for the set of vectors in the n-gon in the geometric statement. We'll work with the algebraic inequality - it happens to be considerably more relevant.

First, let's show that the inequality is necessary for there to be no excess - we'll then show that it's a sufficient condition. By the construction of the rule set for the (n,k) system whenever we decrease by , we also decrease of the 's by . So, for every decrease in , we have a decrease in . If there is no excess then, eventually will have to be 0. But we cannot have . Since it must decrease by at least , we have the given inequality must hold.


Showing that this is sufficient is considerably trickier. First we shall make a key observation about rules - that it doesn't matter in what order they are applied. Indeed, we could assume they are all applied at the same time - however, in our solution we will still be doing things sequentially. The fact that it doesn't matter if rules are applied at the same time leads to avery crucial observation - you can add rules to form new rules. If is a rule and is a rule, then is a rule. Keep this in mind. Now the method we will use to get 0 excess looks like this:

1. Take the set of the largest 's.
2. Apply the rule which decreases all of 's in that set until the set of 's is no longer the largest set of 's. Then, go back to 1.

Now, if you try this, you'll realize it's somewhat inconvenient when there doesn't exist a set of 'largest' 's - for example, try to find the 3 largest numbers in 2, 2, 2, 5, 5. Now we'll use the very cool trick of adding rules. First let's illustrate with the 2, 2, 2, 5, 5 example. The 2's are annoying, in that we can't really choose one of them to belong in our set. So we'll 'delocalize' them - each of the 2's will be '1/3' of an element in the set. So our rule would be (1/3, 1/3, 1/3, 1, 1). Is this a valid rule? Yes! If we add the rules (1, 0, 0, 1, 1), (0, 1, 0, 1, 1), and (0, 0, 1, 1, 1), we get (1, 1, 1, 3, 3) = 3*(1/3, 1/3, 1/3, 1, 1). It's not too surprising that this should work in general. If there are smallest's when we can only have , consider each of the smallests '' in the set (and adjust the rule accordingly). How can we ensure that we can have a rule which looks like with a's and b's? Basically it consists of adding all the rules with 1's in place of the a's and a 'consecutive' string of b 1's in the b's. Illustrating for and , :

We want to obtain rule (4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7) (there could be 0's and the elements do not have to be in order, but that doesn't change anything). We add the following rules:

(1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1)
(0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1)
(0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1)
(0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1)

One more problem with this rule-creating needs to be settled: what happens if there are or more largests? Then our job is actually very easy. Decrease each of those largests by the same amount (one cool thing about the system thing is that an system has all all the rules of an system for - the reader should be able to show this) until all the largests have the same value as the second-largest. And continue - until all the elements have the same value, and then until they are all 0.

Now, back to the problem. Let us assume we never have a case where there are or more largests (if we do, we're done, from above). We make the key observation that applying our (sometimes created) rule keeps constant. Because of this, it will always be non-negative (given the initial inequality) As long as less than of the elements are zero (more than are positive), we can apply some rule (we can only not apply rules to zero quanitities). So eventually there will be or less positive elements. But if we have or less positive elements, all less than or equal to , then if is non-negative, all those positive have to equal - so we have elements equalling the ; that is, largests. So we have a contradiction, and we are (finally) done.


Generalization 2:

Looking at the above method of proof, it should be fairly obvious that the excess is equivalent to . We can obtain it in basically the same way we obtain 0 excess in Generalization 1.