[ 3 posts ] 
 Exercise [16.08] 
Author Message

Joined: 26 Mar 2010, 04:39
Posts: 109
Post Exercise [16.08]
We consider the function f(a,b)=((a+b)^2+3a+b)/2. We must show that this function provides a 1-1 mapping between the natural numbers and the pairs (a,b) of natural numbers.

To do this we must show:
1. f:\mathbb{N}\times\mathbb{N}\to\mathbb{N} (i.e. the range of f lies in \mathbb{N})
2. For any natural number n we can find a unique pair of natural numbers (a_n,b_n) such that f(a_n,b_n)=n

The first part is obvious if we just consider the different choices of (a,b) modulo 2 to see that (a+b)^2+3a+b is always an even number and thus f(a,b)\in\mathbb{N}.

For the second part, we notice that f can be expressed recursively according to:
f(a,b) + 1 = \begin{cases}f(a+1,b-1)& b>0\\ f(0,a+1) & b=0\end{cases}

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

Suppose f(a,b)=f(c,d) where (a,b)\neq (c,d). Suppose first that a+b=c+d and without loss of generality suppose a>c. Then
f(a,b) = f(c,d) + (a-c) > f(c,d)
which is a contradiction. Hence we must have a+b\neq c+d.

Suppose then, without loss of generality, that a+b>c+d, or in other words a+b-1\geq c+d. Then we have (noting that f is monotone in the first variable):
f(a,b) \geq f(0,a+b) > f(a+b-1,0) \geq f(c+d,0)\geq f(c,d)
In other words f(a,b) >f(c,d), which is again a contradiction.

Hence we have that f(a,b)=f(c,d) if and only if a=c and b=d, which establishes uniqueness.

15 May 2010, 07:43

Joined: 07 Jun 2008, 08:21
Posts: 235
Post Re: Exercise [16.08]
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
Post 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

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
   [ 3 posts ]