Final Exam Practice Problems

Instructions

Complete as many of the following problems as you can. Note that the final exam is comprehensive, but will focus more on the stuff we covered after midterms. You can turn in your solutions to the problems below for 0.5% points toward your final exam. These problems are graded entirely on completeness. So, if you manage to get 40 problems done (i.e. you have completed solutions, even if mildly wrong), you earn 20 percentage points toward your final exam score (i.e., if you earn a 60% on the final, but completed the review sheet, your final score will be 80%).

I promise that the problems you see on the final will be 1/2 to 1/3 the difficulty of the ones you see below. If you can handle the hard stuff, the moderately difficult stuff that you’d normally struggle with becomes really easy. The point of you working these harder problems is so that you have to understand the basics well enough to solve these.

Sets

1. Simplify the notation for the intersection of intervals \((4,10)\cap (5,11]\) (Helps to draw this stuff on a number line)
2. Simplify the notation for the union of intervals \([4,6]\cup (6,10]\).
3. Let \(U=\mathbb{R}\) be a “universal set” for the sake of this problem. Find the complement of the interval \((0,3)\)
4. How many elements are in the interval \((0,10)\)? (Be careful!!!!!)

Modular Arithmetic, Divisibility, and the Quotient Remainder Theorem

1. Calculate \(567 \pmod {13}\)
2. Calculate \(-1284 \pmod 6\)
3. Let \(n\) be an (unknown) natural number. Calculate \((n+3) \pmod n\). (Hint: Use the quotient remainder theorem, or try solving the problems for several different choices for \(n\) in order to come up with a solution to the original problem with the generic \(n\)).
4. Let \(n\) be an unknown natural number. Calculate \((n^2+n+2) \pmod n\).

Functions and Relations

1. Let \(A=\{0,4,1\}\) and \(B=\{1,2,3,4,5\}\). Is is possible to define a bijective function from \(A\) onto \(B\)? If so, define one. If not, explain why not.
2. Let \(2\mathbb{Z}\) be the set of all even numbers. Define a function \(f\) from the natural numbers to \(2\mathbb{Z}\) that is one-to-one, but not onto. (Hint: infinitely long potato diagrams so that one contains all natural numbers and the other contains all even numbers can help).
3. For each of the following, find a function \(f\) from the reals to the reals (i.e. a function that can be graphed on the usual coordinate system) such that:
   1. \(f\) is one-to-one but not onto
   2. \(f\) is one-to-one and onto
   3. \(f\) is NOT one-to-one and IS onto

4. Given the relation \(R=\{(1,5),(1,4),(4,1),(5,1),(5,4), (1,1), (4,4),(5,5)\}\), determine whether or not \(R\) is reflexive, symmetric and/or transitive.

5. Find relation that is transitive but NOT symmetric.

Truth Tables and Symbolic Logic

1. Let \(p,q,r\) be statements. Prove or disprove the logical equivalence of the statement \((p\vee \neg q)\wedge r \equiv (p\wedge r)\vee (\neg q \wedge r)\).

Proofs and Counterexamples

1. Prove or disprove the statement: “If \(n,m\) are odd, then \(n^2+m^2\) is even.”
2. Prove or disprove: “If \(n\) is odd, then \(8\vert n^2-1\). “
3. Prove or disprove the statement: “Everybody’s got a water buffalo.”
4. Prove or disprove the statement: “There are integers \(n,m\) such that \(10n+6m=2\)”
5. Prove or disprove that the sum of five consecutive natural numbers is divisible by 5.

Sequences, Sums, and Products

1. Find a closed formula for the following sequence \(\{128,-64,32,-16,8,-4,2,-1,\frac{1}{2},-\frac{1}{4},…\}\).
2. Prove or disprove that \(\sum_{i=1}^n i^3=\frac{n^2(n+1)^2}{4}\).
3. Prove or disprove that \(\Pi_{i=1}^n 3^i=3^{\sum_{k=1}^n k}\) (yes, the sum is in the exponent)
4. Compute the value of \(\sum_{k=0}^{200} \frac{1}{3^k}\) (Note: you might need to rewrite the inside expression to make your life easier)

Recurrence Relations and Recursion

1. Let \(A=\{a_n\}_{i=0}^\infty\) be a recursively defined sequence such that \(a_0=2\) and \(a_n=a_{n-1}+5\). Find a closed formula for \(A\).

2. Use an induction argument to prove that your closed formula in the problem above is correct.

3. Let \(B=\{b_k\}_{k=0}^\infty\) be a recursively defined sequence such that \(b_0=3\) and \(b_k=b_{k-1}\cdot 2\). Compute the value of \(\sum_{k=0}^7b_k\) and \(\Pi_{k=2}^6 b_k\).

4. “Inflation” describes the phenomena of your money losing value/spending power every day because of increases in the costs of goods, and increases in worldwide dollar supply (more dollars means each is worth less). As of this writing, the current estimated rate of inflation is \(3%\), meaning each year your dollar is only worth \(97%\) of what it was last year. So, supposing you start with $\(100\) today, and do not invest it at all, how much money will you have after \(1\) year, if your money is only worth \(0.97\) times what it was last year? How about after two years? Three years? Come up with a recursively defined formula that will tell you how much you have after \(n\) years.

Counting Systems

1. Convert \(7236_{10}\) to binary.
2. Convert the number \(512764_8\) from “Octal” (base 8) to decimal, where each place-value, reading right to left, represents incrementally higher powers of \(8\).
3. The “Hexadecimal” number system is base \(16\), where place values are can be filled with any character in the set \(\{0,1,2,3,4,…,7,8,9,A,B,C,D,E,F\}\), where \(A_{16}=11_{10}\), \(B_{16}=12_{10}\), etc. Convert \(151213_{10}\) to hexadecimal.
4. Multiply the binary numbers \(10101101_2\) and \(10101_2\).

Combinatorics

1. How many distinct rearrangements of the letters in the “syzygy” are there (so that there are no duplicate words)?
2. Suppose you have a bag containing 5 red marbles, 7 blue marbles, 6 green marbles, and 8 purple marbles. How many ways can you select 10 marbles where you have exactly 3 red marbles, exactly 4 blue marbles, and no more than 3 green marbles (i.e. less than or equal to 3 green marbles).
3. You visit a pizza shop with your friends, that allows you to build your own pizza. You have two different choices of crust, three types of sauce, three different types of cheese, 6 different types of vegetables, and 4 different types of meat to choose from. You can also choose to not have a meat or vegetable, but you must choose a crust, sauce, and cheese. How many different pizzas could you theoretically construct?
4. How many different committees of 12 can I form from 20 people?
5. How many different ways can I rearrange twelve chairs in a row?

Graph Theory

1. Determine whether or not the following graph is bipartite and/or tripartite. Either organize the graph to show that is bi/tri-partite or argue why there is no way to arrange the vertices into 2 (or 3) separate groupings where no tow vertices in each grouping are connected.

2. A tree is a graph with no closed walks (i.e. no “cycles”). Prove the statement “Every tree is bipartite.” (Hint: Contradiction; suppose that there is a tree that is NOT bipartite, and then argue why that is not possible based on the definition of “tree”).

3. Find three distinct (i.e. no repeats) subgraphs on five vertices of the graph shown above.

4. Prove (or explain well) or disprove that any graph that has an Euler path also has a Hamiltonian path (i.e. a path that passes through each vertex exactly once, without repeats).