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<u+v, then f(x,y)<f(u,v).

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: