Problem 10
List all \(1-1\) and onto functions from (1,2,3) to itself.
Problem 10
Prove that for any collection of \(n\) people, two persons have the exact same number of acquaintances in the group provided that each person has at least one acquaintance.
Problem 10
Find the first six terms of the sequences defined for \(n \geq 0\) as: (a) \(H(n)=n^{2}(n+1)^{2} / 4\) (b) \(G(n)=2^{n}-1\) (c) \(F(n)=(-1)^{n} 2^{n}-3^{n}\)
Problem 11
There are five suburbs in the city of Melbourn. How many all-stars must be picked from each suburb to guarantee that at least five players come from the same suburb?
Problem 11
A chain-letter scheme is a famous (and usually illegal) get-rich-quick scheme. A person \(X\) receives a letter with, say, five names on it. \(X\) sends 10 to the person whose name is at the top of the list. \(X\) then deletes that name from the top of the list, adds his or her own name to the bottom of the list, and sends the letter to five "friends," all within one day. In around two weeks, \(X\) is supposed to receive 31,250. Suppose every person who receives the letter follows the instructions (including sending 10 to the person listed first!). Show that if there are only finitely many people, the scheme cannot work (in some sense of "cannot work" that you should make precise). Show that if there are countably infinitely many people, the scheme can work.
Problem 12
Find a recursively defined function that gives the terms of the following sequences: (a) \(2,5,8,11,14, \ldots\) (b) \(3,6,12,24,48, \ldots\)
Problem 12
Determine which of the following functions are onto: (a) \(F_{1}: \mathbb{R} \rightarrow \mathbb{R}\) where \(F_{1}(x)=x^{2}-1\). (b) \(F_{2}: \mathbb{R} \rightarrow \mathbb{Z}\) where \(F_{2}(x)=\lceil x\rceil(\lceil x]\) is the "ceiling" of \(x\) ). (c) \(F_{3}: \mathbb{Z} \rightarrow \mathbb{Z}\) where \(F_{3}(x)=x^{3}\). (d) \(F_{4}: \mathbb{R} \rightarrow \mathbb{R}\) where \(F_{4}(x)=x^{3}\). (e) For the linear ordering \(<\) on \(\mathbb{R}\), list all the increasing functions among parts (a) through (d). (f) For the ordering \(<\) on \(R\), list all the strictly increasing functions among parts (a) through (d).
Problem 12
Show for the natural numbers \(\mathbb{N}\) that $$|P(N)|>|\mathbb{N}|$$
Problem 12
A bowl contains raspberry and orange lollipops, with 15 of each. How many must be drawn one at a time to ensure that you have at least three orange lollipops?
Problem 13
Challenge: Show that \(|\mathbb{R}|=|\mathcal{P}(\mathbb{N})| .\) (Hint: Use the
Cantor-Schröder-Bernstein Theorem. To show that \(|\mathbb{R}|
\leq|\mathcal{P}(\mathbb{N})|\), you might use function \(D: \mathbb{R}
\rightarrow \mathcal{P}(\mathbb{Q})\) where for \(r \in \mathbb{R}, D(r)=\\{q
\in Q: q
