Let $n$ be a positive integer. A $corner$ is a finite set $S$ of ordered $n$-tuples of positive integers such that if $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ are positive integers with $a_k \geq b_k$ for $k = 1, 2, \ldots, n$ and $(a_1, a_2, \ldots, a_n) \in S$, then $(b_1, b_2, \ldots, b_n) \in S$. Prove that among any infinite collection of corners, there exist two corners, one of which is a subset of the other one.
Problem
Source: USA TST 2000
Tags: induction, pigeonhole principle, analytic geometry, number theory unsolved, number theory
12.05.2006 14:21
it is in my book . if noone ..., i will post solution?
29.12.2006 20:52
A point $(a_{1}, a_{2}, \ldots a_{n})$ is said to pwn a point $(b_{1}, b_{2}, \ldots b_{n})$ if $a_{i}\ge b_{i}$ for all $i$. Suppose that there is an infinite set $S$ of corners such that no corner is the subset of another. We call such a set evil; any infinite subset of an evil set is clearly evil. We will construct an infinite sequence $T_{k}$ of points such that $T_{i}$ pwns $T_{j}$ only if $i \le j$. To aid our construction, we will also define a sequence $S_{k}$ of evil sets and a sequence $C_{k}\in S_{k}$ of corners. We will define $S_{k}$ inductively, with $S_{1}= S$. Suppose that we have already defined $S_{k}$ as well as $T_{i}$ for $1 \le i \le k-1$. Further suppose that for each $i \le k-1$, there is no element in a corner in $S_{k}$ which pwns $T_{i}$. This is vacuously true in the base case when $k = 1$. We choose $C_{k}$ to be an arbitrary element of $S_{k}$. Let $T_{k}$ be an element of $C_{k}$ which is not contained in infinitely many other corners in $S_{k}$. Such a $T_{k}$ exists since $S_{k}$ is evil. By the induction hypothesis, $T_{k}$ does not pwn $T_{i}$ for any $i \le k-1$. We now define $S_{k+1}$ to be the set of all corners $C \in S_{k}$ such that $T_{k}\not\in C$. We know that $S_{k+1}$ is evil since it is infinite and $S_{k+1}\subset S_{k}$. Obviously, no element in a corner $C \in S_{k+1}$ pwns $T_{k}$, or else $T_{k}$ would be an element of $C$. Also, since $S_{k+1}$ is a subset of $S_{k}$, no element in a corner in $S_{k+1}$ pwns $T_{i}$ for $i \le k-1$. This completes our inductive definitions, so that we have in fact constructed a sequence $T_{k}$ such that $T_{i}$ pwns $T_{j}$ only if $i \le j$. But now we will show that the existence of this sequence is contradictory. Indeed, we construct an infinite subsequence $X_{k}$ of $T_{k}$ such that for no $i \ne j$ does $X_{i}$ pwn $X_{j}$. This can be done, since if we have picked the first $a$ points in $X_{k}$, where $X_{a}= T_{b}$, then note that the points $X_{1}, X_{2}, \ldots X_{a}$ collectively pwn only a finite number of points, so that there must be some $c > b$ such that $X_{i}$ does not pwn $T_{c}$ for any $i \le a$. Then choose $X_{a+1}$ to be $T_{c}$, and continue ad infinitum in a similar manner. However, it is not possible to have an infinite set of lattice points no two of which pwn each other. This can be proven by induction on number of dimensions. It's trivial in dimension 1. Suppose it holds for $n-1$ dimensions. Assume that there is an infinite set $X$ of points no two of which pwn each other in $n$ dimensions. Let $(a_{1}, a_{2}, \ldots a_{n})$ be a point in $X$. Then every other element $(x_{1}, x_{2}, \ldots x_{n})$ in $X$ must satisfy $x_{i}\le a_{i}$ for at least one $i$. Then by pigeonhole, there is some $i$ such that infinitely many elements of $X$ have $i$th coordinate at most $a_{i}$. Then by pigeonhole, there is some $a \le a_{i}$ such that infinitely many elements of $X$ have $i$th coordinate equal to $a$. However, this is not possible, since it implies that there exists an infinite set of points in $n-1$ dimensions, no two of which pwn each other, which there doesn't. Thus we have reached a contradiction, and no evil set exists.
30.12.2006 18:29
We can extend the result: in any infinite set of corners, there exist infinitely many corners, each of which is a subset of infinitely many other corners. We can similarly induct on the number of dimensions: if each corner is denoted by a foremost point (ie the point which pwns all other poitnts in the corner, by probability's jargon), then we either have that, in each of the n places (the components, the dimensions), we hit infinitely many values as we vary over the foremost points, in which case we can create an elimination scheme to make, for any point in the list, an infinite list of successively pwning points, or we have some place where there are infinitely many points which have the same value in that dimension, and then the problem reduces to one of $n-1$ dimensions. This is just an outline of the solution, but, reading it over, I realize it makes little sense if you haven't thought about it...so i can post the whole thing if needed.