# Proving the possibility of rectangles within another

I was given this problem to prove yet Im having a hard time understanding what this problem actually is saying.

Here is what I am understanding:

In the plane we are given an infinite set of rectangles.

and every rectangle $(n_k,m_k)$ has the form where it must go through $(0,0)$ and the three other coordinates given above.

Now, how would I be able to prove that there exist two rectangles in the set such that one contains the other. The way I am visualizing is the rectangle (green) would only touch the origin but not the lengths of the bigger rectangle (red).

If possible can anyone give an example or an idea, it would help a lot.

• Note that you must consider that a rectangle contain another one even if it touch the sides. Indeed, if we consider that in this case the rectangles are not contained in one another, the set of rectangles $\{ (1,n) | n\in \Bbb N^* \}$ would be an infinite set where there are no two rectangles that contains one another. Commented Oct 28, 2015 at 1:26

The idea is to notice that if there is no rectangles contained in one another, for each $m\in \Bbb N$, there is only one rectangle with height $m$. Indeed, if there was two, with with $n_1$ and $n_2$ such that $n_1 < n_2$, the rectangle $(m,n_1)$ is contained in the rectangle $(m,n_2)$. By the same reasoning, each rectangle has a different width too.

Now, take the rectangle with the smallest height $m$, it has width $N$. But every other rectangle must have a width smaller that $N$, or else it would contain $(m,N)$. And as the rectangles have all a different width, there is at most $N$ rectangle.

Let $R(n,m)$ be the rectangle whose upper right corner is at $\langle n,m\rangle$. If the set of rectangles were finite, it might, for instance, consist of the rectangles $R(1,6),R(2,5),R(3,4),R(4,3),R(5,2)$, and $R(6,1)$. If you sketch these, you’ll see that none of them is contained in any of the others. In fact, if you want $n$ rectangles, none of which contains any of the others, you can use

$$R(1,n),R(2,n-1),R(3,n-2),\ldots,R(n-1,2),R(n,1)\;,$$

the rectangles of the form $R(k,n+1-k)$ for $k=1,\ldots,n$. This shows that you’ll definitely need infinitely many rectangles in order to be sure that one of them is contained in another; your problem is to show that infinitely many is enough.

It’s easier to show the contrapositive:

Let $\mathscr{R}$ be a family of rectangles of the form $R(n,m)$ such that no member of $\mathscr{R}$ contains any other member of $\mathscr{R}$; then $\mathscr{R}$ is finite.

HINT: Let $\mathscr{R}$ be as stated, and suppose that $\langle n,m\rangle\in\mathscr{R}$. Show that if $R(k,\ell)$ is any other member of $\mathscr{R}$, then either $k<n$ and $\ell>m$, or $k>n$ and $\ell<m$. (In other words, $\langle k,\ell\rangle$ is either above and to the left of $\langle n,m\rangle$, or below and to the right of $\langle n,m\rangle$.