Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Exercise [16.08]
Author Message

Joined: 26 Mar 2010, 04:39
Posts: 109
Exercise [16.08]
We consider the function . We must show that this function provides a 1-1 mapping between the natural numbers and the pairs of natural numbers.

To do this we must show:
1. (i.e. the range of lies in )
2. For any natural number we can find a unique pair of natural numbers such that

The first part is obvious if we just consider the different choices of modulo 2 to see that is always an even number and thus .

For the second part, we notice that can be expressed recursively according to:

This shows us how to construct any natural number and thus for any natural number we can find a pair of natural numbers such that as required. It remains to show uniqueness. Actually this is obvious from the construction, but I'll prove it explicitly:

Suppose where . Suppose first that and without loss of generality suppose . Then

which is a contradiction. Hence we must have .

Suppose then, without loss of generality, that , or in other words . Then we have (noting that is monotone in the first variable):

In other words , which is again a contradiction.

Hence we have that if and only if and , which establishes uniqueness.

15 May 2010, 07:43
Supporter

Joined: 07 Jun 2008, 08:21
Posts: 235
Re: Exercise [16.08]
Robin
Presumably you've seen the other solution to this exercise via the sorted solutions link here.

26 May 2010, 08:55

Joined: 12 Jul 2010, 07:44
Posts: 154
Re: Exercise [16.08]
Trying to work out why the formula provided maps NxN onto N, as the solutions above do, is actually the harder way to approach this problem.

A much easier and more intuitive way is to start by designing a 1-1 map from N onto NxN as follows:

0 1 3 6 ...
2 4 7 ...
5 8
9
.
.

i.e. number along each diagonal layer in turn.

Now, this numbering pattern implies a formula from (x,y) to n (the number at that point). To construct this formula, note that (x+y) gives the "layer number" (assuming in the diagram above that y increases in the downwards direction).

The first (topmost) number in each layer l is equal to the total number of numbers (points) in all the previous layers - that is, in the triangle (0,0) --> (l-1, 0) --> (0, l-1). Numbering then increases as you move vertically downward in a layer.

The number of points in this triangle is l(l+1)/2. Since (x+y) is the "layer number", substitute l=x+y, to get the starting number for a layer, and then add y for the downward increase along (within) the layer:

n = (x+y)(x+y+1)/2 + y

= ((x+y)^2 + 3y + x)/2

...which is exactly the formula given, just with (b,a) replacing (x,y)!

03 Apr 2011, 08:36
 Page 1 of 1 [ 3 posts ]