From a college friend
by t0rajir0u, Apr 16, 2007, 3:49 AM
Problem: Show that for any positive integer 
, any infinite subset of 
contains two elements 
such that 
.
Solution 1: We will proceed by contradiction. Suppose there exists
that contains no such pairs of elements. We will consider 
with minimal dimension . Pick any element 
and consider the possible other elements in . No such elements can have each coordinate greater than those of 
, so only contains elements with at least one coordinate less than those of . Each such coordinate 
can only take the values 
.
In other words, let
consist of the elements 
of such that 
. Then
Since is infinite, it follows that for some 
the set 
is also infinite.
Now, ignore the coordinate
in every element of this set, since that coordinate is equal to 
for all elements of this set. But with that coordinate ignored we now have a subset of 
that contains no pairs of desired elements, contradicting the minimality of the dimension of .
Hence no such exists. QED.
Solution 2: We will appeal to the following lemma.
Lemma: An infinite sequence of distinct naturals contains a monotonically increasing infinite subsequence.
This infinitude occurs because an infinite sequence of distinct naturals cannot be bounded. Hence for an infinite sequence of non-distinct naturals, this lemma is false if and only if the sequence is bounded (otherwise we could simply ignore repetitions of numbers and consider only the unbounded sequence of distinct naturals that resulted).
Consider any infinite subset $\mathbc{S}\subset \mathbb{N}^{m}$, and order each element according to the sum of its coordinates. The infinite sequence of a given coordinate of each element is therefore either bounded or contains a monotonically increasing infinite subsequence.
Clearly if every coordinate is bounded then this subset cannot be infinite, so some coordinate is unbounded. Then we can pick an infinite subsequence of $\mathbc{S}$ that is monotonically increasing in that coordinate. From this subsequence, we can pick an infinite subsequence that is also monotonically increasing in each of the other unbounded coordinates.
Repeating this process, we have an infinite subsequence that is either monotonically increasing or bounded in every coordinate. The bounded coordinates must take on at least one of the possible set of values infinitely often, so pick an infinite subsequence such that each bounded coordinate is the same, and we then have an infinite subsequence where each coordinate is non-decreasing. This is stronger than the desired result. QED.
I like problems like these because they are more about reasoning than about memorizing strong results or tricky manipulations (a problem I have with many inequality problems, for example). As Engel says, a good Olympiad problem "should have no prerequisites other than cleverness."
Practice Problem: (From the same friend) Let
be a set of some "words" of maximum length consisting of strings of letters from an alphabet of size 
such that no word in starts with another word in . Let 
be the number of words of length 
in . Show that
, any infinite subset of 
contains two elements 
such that 
.Solution 1: We will proceed by contradiction. Suppose there exists
that contains no such pairs of elements. We will consider 
with minimal dimension . Pick any element 
and consider the possible other elements in . No such elements can have each coordinate greater than those of 
, so only contains elements with at least one coordinate less than those of . Each such coordinate 
can only take the values 
.In other words, let
consist of the elements 
of such that 
. Then
Since
is infinite, it follows that for some 
the set 
is also infinite.Now, ignore the coordinate
in every element of this set, since that coordinate is equal to 
for all elements of this set. But with that coordinate ignored we now have a subset of 
that contains no pairs of desired elements, contradicting the minimality of the dimension of .Hence no such
exists. QED.Solution 2: We will appeal to the following lemma.
Lemma: An infinite sequence of distinct naturals contains a monotonically increasing infinite subsequence.
This infinitude occurs because an infinite sequence of distinct naturals cannot be bounded. Hence for an infinite sequence of non-distinct naturals, this lemma is false if and only if the sequence is bounded (otherwise we could simply ignore repetitions of numbers and consider only the unbounded sequence of distinct naturals that resulted).
Consider any infinite subset $\mathbc{S}\subset \mathbb{N}^{m}$, and order each element according to the sum of its coordinates. The infinite sequence of a given coordinate of each element is therefore either bounded or contains a monotonically increasing infinite subsequence.
Clearly if every coordinate is bounded then this subset cannot be infinite, so some coordinate is unbounded. Then we can pick an infinite subsequence of $\mathbc{S}$ that is monotonically increasing in that coordinate. From this subsequence, we can pick an infinite subsequence that is also monotonically increasing in each of the other unbounded coordinates.
Repeating this process, we have an infinite subsequence that is either monotonically increasing or bounded in every coordinate. The bounded coordinates must take on at least one of the possible set of values infinitely often, so pick an infinite subsequence such that each bounded coordinate is the same, and we then have an infinite subsequence where each coordinate is non-decreasing. This is stronger than the desired result. QED.
I like problems like these because they are more about reasoning than about memorizing strong results or tricky manipulations (a problem I have with many inequality problems, for example). As Engel says, a good Olympiad problem "should have no prerequisites other than cleverness."
Practice Problem: (From the same friend) Let
be a set of some "words" of maximum length consisting of strings of letters from an alphabet of size 
such that no word in starts with another word in . Let 
be the number of words of length 
in . Show that
April 2009
March 2009