Three solutions for 101 numbersby Aleksander PELCZYNSKI (Delta 5/1974)
This year the Mathematical Olympiad is going through its 25th edition and this article was intended to commemorate the anniversary. However, what it eventually resulted in might possibly be adequate rather for the 26th anniversary. One of the important and difficult tasks of the General Committee of the Mathematical Olympiad is to choose the problems for the contest. The problems proposed for the occasion should be new, obviously they cannot be taken form a generally accessible problem book. Moreover, they should be neither too easy nor too hard, ought to have several solutions that can be put into few lines and, finally, no knowledge exceeding that of the level of secondary school should be required to understand and solve the problems; better still, if they require no school knowledge at all to make them accessible to both a primary school pupil and a member of the Polish Academy of Sciences. However, just as you never meet ideal people or things in real life, there seem to be no ideal problems either. I wish to tell you the story of one particular problem, that might almost be called ideal, if it weren't a little bit too hard.
As a freshman in mathematics in 1950 I read a report on the XIII Moscow Mathematical Olympiad in the Russian journal "Mathematics at School". Here is one of the problems offered in the finals:
The numbers from 1 to 101 are written down in an arbitrary order. Prove that you can delete 90 of those 101 numbers in such a way that the remaining 11 form a monotone sequence, i.e. a decreasing sequence or an increasing sequence.
No solution was included, but the report stated that only one participant of the contest gave a correct proof. For me and some of my colleagues this meant a real challenge. Certainly we can solve the problem too! Unfortunately, good will didn't seem to be enough. Notwithstanding hours spent on thinking, discussions and exchange of experiences, the desired wonderful idea did not appear and the problem remained unsolved not only for the few hours time that was given to the participants of the Olympiad, but also for many days and weeks. We only noticed that no number less than 101 would do, since e.g. the sequence of 100 numbers
91, 92, ..., 99, 100, 81, 82, ..., 89, 90, ..., 1, 2, ..., 9, 10
contains no monotone subsequence consisting of more than 10 elements (why? see the solution I (3) below). However, someone observed that the problem moght probably be generalized to arbitrary natural numbers of the form n2+1. We verified this conjecture for 5 = 22+1 and for 10 = 32+1; unfortunately when it came to sequences with 17 elements (17 = 42+1) we got lost in computations. Still puzzled by the question, we started to tell various people about the problem. In particular, I wrote to my colleague X in Poznan, who was one of the winners of the I Mathematical Olympiad, while one of my friends passed the problem to the now lateprofessor Stefan Kulczycki (1893-1960). Both contacts turned out very fruitful. The following letter came from Poznan:
No wonder only one participant solved the problem in Moscow and no one could do it in Warsaw, since I needed six full hours to find the solution.
This proof of the author's modesty was, however, indeed supported by a beautiful, even if slightly complicated proof, quite similar to the one we have simultaneously received from prof. Kulczycki.
Solution I (by X)
We shall prove by induction that for any natural number n you can delete n2- n numbers from an arbitrary sequence of n2+1 different natural numbers in such a way that the remaining n+1 numbers form a monotone sequence. This is obvious for n=1, so let's assume now the induction hypothesis for some k1 and let be an arbitrary sequence of different natural numbers. We must prove that it contains a (k+2)-element monotone subsequence. By induction hypothesis, the sequence contains a monotone subsequence with .
Let be the greatest element in this subsequence. Consider now the sequence with the number deleted, i.e., the sequence withbi=ai for i<s1 and bi=ai+1 for is1. Applying the induction hypothesis once more, we find a monotone sequence and denote its greatest member by . Again the induction hypothesis applied to the sequence without the elements and yields an element , and so on. Since (k+1)2+1 = k2+(2k+2), we can proceed with this procedure 2k+2 times to get 2k+2 different numbers . we shall now divide them into two groups. Let the first one include those, say, A1, A2,...,Aq that were last elements in increasing sequences of length k+1 and the other those, say, B1, B2,..., B2k+2-q,, that were first elements in decreasing sequences of length k+1. We may assume that in each group the enumeration preserves the order of appearance of these numbers in the sequence . Now we can consider several cases.
(4a) There is an index t such that Bt=comes after A1= in the sequence , i.e., . Then if A1>Bt, we have a decreasing (k+2)-element sequence and if A1<Bt, we have an increasing sequence .
(4b) If (4a) does not hold, the members of both groups occur in the sequence in the following order: B1, B2,..., Bk+1, A1, A2,...,Ak+1 and the monotone subsequence required is given either by the increasing sequence B1, B2,..., Bk+1, A1 (when Bk+1<A1) or by the decreasing sequence Bk+1, A1, A2,...,Ak+1 (when Bk+1>A1).
We have thus proved that the induction hypothesis entails that in each case we can choose a monotone (k+2)-element subsequence of the sequence , which completes the solution.
The argument of prof. Kulczycki differed from the previous one in that first the greatest element of the sequence was deleted, and then - as in X's proof - the induction hypothesis was applied 2k+1 times to choose 2k+1 greatest elements out of some monotone (k+1)-element sequences. Next a discussion quite analogous to the one performed by my colleague X was carried out (how?).
Here is where the first part of the story ends. Those who "got lost" while reading solution I needn't despair: you will not need it to understand what follows in the sequel. While discussing the first solution, we concluded that it was too difficult for the organizers of the Moscow Olympiad to take the problem into account - were there not some other and simpler solution. And indeed a simpler solution there was. In some late evening of May 1951, after the usual lecture on propedeutics of philosophy, my fellow-student Stefan Rolewicz announced that during the lecture he devised a new solution. The solution of Stefan Rolewicz, nowadays Head of the Chair of Mathematical Analysis in the Institute of Mathematics of the Polish Academy of Science, was essentially quite similar to that offered by the authors of the problem. This we were able to establish when we found in Warsaw the book Selected problems and theorems of elementary mathematics. Part I: Arithmetic and Algebra (in Russian) by D.O. Shkolskii, G.M. Adelson Welskii, N.N. Tchencov, A.M. Yaglom and I.M. Yaglom (Moscow 1950, pp. 117-118).
Solution II (the authors and S. Rolewicz)
Let be the first (leftmost) of the given sequence of numbers, the first of the remaining numbers that is greater than , the first of the numbers following that is greater than , and so on. Thus we get an increasing sequence . If i1 > 10, then we are done. Otherwise, we delete all the numbers hitherto chosen and in the very same way as before choose a new increasing sequence from the remaining 101-i1 elements. By repeating this procedure we eventually end up with a number of pairwise disjoint increasing sequences. If at least one of them has more than 10 elements, then we are done, too. Therefore it remains to consider the case when each of those sequences has at most 10 elements. Since we started with 101 numbers, the number k of such sequences is not less then 11. In that case we shall define a decreasing sequence with at least 11 elements.
The last element in this sequence is to be , i.e., the last element of the last increasing sequence chosen. Next we choose that element of the sequence before last that occurs to the left of and is the closest such number to . This number, say b, must be greater than , for otherwise in the construction of the sequence before last we would have chosen after b, while in fact b only occurred in the last sequence. Similarly, we find an element in the third sequence before last that occurs to the left of b and is the number closest to b, and so on. Thus we construct a sequence of numbers that grow from right to left, i.e., a decreasing sequence. The number of elements of this sequence is equal to the number k of increasing sequences previously chosen, hence it is not less than 11. This ends the proof.
Again, do not despair if you have not grasped the II solution: you still have another chance. More or less twenty years later my colleague Andrzej Mąkowski told me of a "very simple" proof of the problem on 101 numbers, coming from the eminent Hungarian mathematician Paul Erdos. Here it comes.
Solution III (P. Erdos)
To each memberak of the sequence a1, a2,...,a101 of different natural numbers assign two natural numbers r(k) and m(k), where r(k) is the length (=number of elements) of the longest increasing sequence which has ak as its last element (i.e., k=nr(k)) and m(k) is the length of the longest decreasing sequence which has ak as its first element. We will prove that for some k (between 1 and 101) at least one of the numbers r(k) or m(k) is greater or equal to 11. Suppose this is not so, i.e., let for each k=1, 2,…,101 be 1r(k)10 and 1m(k) 10. Since there are exactly 100 pairs of natural numbers less than10 each, there must be some indices s and t such that 1st101 and r(s)=r(t) and m(s)=m(t). But now as<at clearly implies r(s)<r(t), while as>at yields m(t)>m(s). (Why?) This contradiction completes the proof.
An analysis of solution III leads to the following generalization of the theorem on 101 numbers:
THEOREM: Let a1, a2,…, an be a sequence of different natural numbers. Then nmr, where m is the length of the longest decreasing subsequence of this sequence and r is the length of its longest increasing subsequence.
I don't know whether this fact can be proved along the lines of either of the two first solutions.
The next theorem due to one of the most brilliant Polish mathematicians Waclaw Sierpinski (1882-1969) can be viewed as an infinite analogue of the fact that each (n2+1)-element sequence contains an (n+1)-element monotone sequence.
THEOREM: Each infinite sequence of numbers contains an infinite monotone subsequence.
I invite the reader to give a thought to the proof of Sierpinski's theorem.
Summing up our considerations, let me say that it is not easy to evaluate a priori the difficulty of a problem. To use the example of the problem on 101 numbers, I suppose that if that problem were presented to our General Committee of the Mathematical Olympiad together with solution I alone, it would certainly be rejected; if we knew solution II, we might accept it, classifying the problem as a diffcult one. However, if someone offered us solution III, we might see the problem as one of average difficulty.