## 187 – Extra credit problems

These questions are due Friday, April 9 at the beginning of lecture.

1. Let $f:{\mathbb N}\times{\mathbb N}\to{\mathbb N}$ be the function given by $\displaystyle f(x,y)=\frac{(x+y)(x+y+1)}2+y.$ Show that $f$ is a bijection.
2. Define $g:{\mathbb N}\to{\mathbb N}$ by setting $g(0)=0,$ $g(1)=1$ and, if $n>1,$ then, letting $p$ be the smallest prime such that $p|n,$ then $g(n)=2^p\times 3^{g(n/p)}.$ [Here, $n/p=n\mathrel{\rm div} p$.] Compute $g(n)$ for $n\le 15,$ and show that $g$ is one-to-one.
Advertisements

### One Response to 187 – Extra credit problems

1. Here are some suggestions. This does not mean you have to follow them, but they may be useful.

One way of showing that $g$ is one-to-one is to prove the following by induction on $n$: For any $a,b\in{\mathbb N},$ if $a+b\le n$ and $g(a)=g(b),$ then $a=b.$

In problem 1, you need to show $f$ is 1-1 and onto. To show onto: Prove by induction on $n$ that the equation $f(x,y)=n$ has a solution $(x,y).$ So, you have to find a solution to $f(x,y)=0$ and, from a solution to $f(x,y)=n,$ you need to construct a solution $(x',y')$ to $f(x',y')=n+1.$

I strongly suggest that you try a few values first, to get a good idea of what is going on. Once you have an idea, the following will make more sense:
Given $f(x,y)=n,$ to find $(x',y')$ with $f(x',y')=n+1,$ it is best to look at two cases, whether $x>0,$ or whether $x=0.$

To show 1-1: Suppose $f(x,y)=f(u,v).$ You need to show $x=u$ and $y=v.$ Begin by showing that $x+y=u+v.$ One way of doing this is to show that if $x+y then $f(x,y)

From this, and the definition of $f,$ it should now be easy for you to show that if $f(x,y)=f(u,v)$ then $y=v.$ And then, of course, it follows that $x=u.$