3.2 THE EXTREME PRINCIPLE 81is only one, (5, 93), and sure enough, their sum is an element of the sequence. So our
sequence is good. Now compute the average, and indeed, we have
5+93+98+99 100+ 1
4
22
.
But why? Let's try to construct another good sequence, with m = 6, n = 100. Start
with 11,78. Since 11 + 78 = 89 ::; 100, there must be a term in the sequence that equals
89. Now we have 11 ,78,89. Notice that 89 + 11 = 100 ::; 100, so 100 also must be in
our sequence. Now we have 11,78, 89, 100, and if we include any more small terms,
we need to be careful. For example, if we included 5, that would force the sequence
to contain 11 + 5 = 16 and 78 + 5 = 83 and 89 + 5 = 94, which is impossible, since
we have only six terms. On the other hand, we could append two large terms without
difficulty. One possible sequence is 11,78,89, 100, 99, 90. And once more, we have
11+78+89+100+99+90 101
------:------> -.6 - 2
Again, we need to figure out just why this is happening. Multiplying by 6, we get
101
11 + 78 + 89 + 100+ 99 + 90 2 6· 2 = 3. 101,
which strongly suggests that we try to pair the six terms to form three sums, each
greater than 101. And indeed, that is easy to do:
11 + 78 + 89 + 100+99 +90 = (11 + 100) + (78 + 89) + (99 + 90).
Can we do this in general? We can hope so. Notice that by hoping this, we are actually
attempting to prove something slightly stronger. After all, it could be that the terms
don't always pair nicely, as they did in this case, but nevertheless, the sum of all the
terms is always big enough. However, there is no harm in trying to prove a stronger
statement. Sometimes stronger statements are easier to prove.
Let's try to work out an argument that handles all sequences with m = 6 and n =
100. First monotonize! This is an important simplification. Assume without loss of
generality that our sequence is good and that
al < a 2 < a 3 < a 4 < as < a 6 ·
We have strict inequalities above because each term in a good sequence is distinct, that
being one of the features of a good sequence.
We want to see if we can pair the terms so that the sum of each pair is greater than
or equal to n + 1. Let's pause for a moment and think about strategy. The hypothesis
is that the sequence is good (and monotonized), and the conclusion that we desire is
a set of three inequalities. It is hard to prove three different inequalities directly (and
if n were bigger, then there would be even more). A more promising approach is
contradiction. For then, we need only assume that one of the inequalities fails, and if
that gets a contradiction, we are done. And not only that, if we assume that two things
sum to less than n + 1, that means the sum is ::; n, which is involved in the definition
of a good sequence-very promising, indeed! So, appealing to the symmetry of the
monotonized sequence, we will assume that at least one of the sums