Functions study problems

Problem 1

Let's define a function f as follows:

\(f: [\frac{1}{4},3] \rightarrow [0,1] \)
\(\displaystyle f(x) = \frac{4x-1}{2x+5}\)

Using the definitions of one-to-one and onto, prove that f is a bijection.

Check your answer against the annotated solutions.

Stuck? Look here for hints . Your algebra might be jamming because you're trying to use a poor choice of outline.

Problem 2

Use the Pigeonhole Principle to prove the following claim.

Claim: There exist two distinct natural numbers m and n with \(m,n\leq 2048\) such that \(13^m-13^n\) is divisible by 2013.

The truth of this claim does not depend on the exact values 13, 2013, and 2048. So, your solution should give an argument that is easy to adapt to other values for these constants rather than, say, using a computer program to find specific values for m and n.

Stuck? See the hints.

Done? Now see the solution.

Problem 3

Suppose that \(h:\mathbb{Z}\rightarrow \mathbb{Z}\) is known to be one-to-one. Let's define a function \(f:\mathbb{Z}^2\rightarrow \mathbb{Z}^2\) by $$f(x,y) = (h(x) + h(y), h(x) - h(y))$$ Prove that f is one-to-one.

First, check the outline for your proof.

Then check the full solution.

Problem 4

Suppose that \(h:\mathbb{Z}\rightarrow \mathbb{Z}\) is known to be onto. Let's define a function \(f:\mathbb{Z}^2\rightarrow \mathbb{Z}\) by \(f(x,y) = h(x)+h(y)\).

Prove that f is onto.

Hints

Solution

Problem 5

Recall that the identity function on a set A is the function \(id_A\) such that \(id_A(x) = x\) for any \(x \in A\).

Definition: A function \(r : X \rightarrow A\) is a retraction if there exists another function \(s : A \rightarrow X\) such that \(r\circ s = id_A\).

Prove that if \(r : X \rightarrow A\) is a retraction, then r is onto.

Hints

Solution

Problem 6

Twenty three people go to lunch at Tang Dynasty and sit down evenly spaced at a large circular table with a lazy Susan (central rotating circular tray) on it, each of them orders a different dish from the menu and they all refuse to share. The dishes of food are brought out and placed on the lazy Susan, one in front of every person, but they are entirely mismatched, so each person has another person's dish. Prove that there is a way to rotate the lazy Susan so that at least two people have the correct dish that they ordered in front of them.

Hints

Solution

Problem 7

Suppose that set A has 5 elements and set B has 2 elements. How many different onto functions can be constructed from A to B? Show your work clearly, so we can see how you came up with your answer.

Hints

Solution

Problem 8

Prof. Windgrave is growing mold samples in his basement. He would like to grow 380 different samples, which need to be more than \(\sqrt{2}\) inches apart. He has a 19 inch by 19 inch sheet of agar. The samples do not need to be placed in any specific pattern: they just have to be far enough apart. Use the pigeonhole principle to prove that his sheet of agar isn't large enough.

Hints

Solution