It was a pleasure to have you in my class this semester and I hope you enjoy your summer!

Math 1311: Study guide for final

The final exam will be Thursday, May 18.

Things you should know:

• Everything.
• Definitions: complete graph, connected graph, planar graph, Eulerian walk, Hamiltonian walk, one-to-one mapping, bijection.
• How to check whether a connected graph admits an Eulerian walk by looking at the degrees of the nodes.
• How to find an Eulerian walk on a graph.
• How to find a Hamiltonian walk on a graph.
• The four color theorem.
• How to fill out truth tables.
• Applications of truth tables.
• How to convert between binary and decimal.
• How to compute nim-sums.
• How to check whether a function is one-to-one or a bijection.

Sample problems, in addition to the sample problems from previous study guides:

1. Given a graph, determine whether it has an Eulerian walk. If it doesn’t, explain why. If it does, find a walk.
2. Draw a non-planar graph which has an Eulerian walk but no Hamiltonian walk
3. Convert 101 from decimal to binary.
4. Convert 101101110 from binary to decimal.
5. Compute the nim sum of 13, 37, and 42.
6. Write a truth table for “if A then (not B or if C then B)”.
7. Use truth tables to determine whether “not (A and B and C)” and “not A or not B or not C” are equivalent.
8. Determine which of the following functions from the real numbers to the real numbers are one-to-one.
1. $f(x) = x^3 - 1$,
2. $g(x) = e^x$,
3. $h(x) = \sin(x - \pi)$,
4. $j(x) = 4x^2 - 2x + 6$.
9. Describe a bijection from $\mathbb R$, the set of real numbers, to $\mathbb R^2$, the Cartesian plane consisting of pairs $(x,y)$ of real numbers.
10. Consider the function $f : \mathbb Z^2 \to \mathbb Q$, whose inputs are pairs of integers and whose outputs are rational numbers, defined as $f(a,b) = a/b$. Explain why $f$ is not a bijection.

Math 1311: Assignment 7

First, a few definitions. We will also discuss these in class, but I wanted to include them here for your reference.

• A set is a collection of things. Given a set, the only thing you can say is whether something is in the set or not. If $x$ is in the set $A$ we say that $x$ is an element of $A$ which we write as $x \in A$. Two sets are equal if they have exactly the same elements. In symbols, $A = B$ means that for all $x$, $x \in A$ if and only if $x \in B$.
• There are special names for the sets of various kinds of numbers.
• $\mathbb N$ denotes the set of natural numbers.
• $\mathbb Z$ denotes the set of integers (‘Z‘ comes from the German word “Zahl“, meaning number.)
• $\mathbb Q$ denotes the set of rational numbers (rational numbers are a quotient of two integers).
• $\mathbb R$ denotes the set of real numbers.
• One way to denote a set is to list all of its elements. The notation for this is to list the elements between curly braces. For example, $\{ 2, 3, 5, 7, 11, 13 \}$ is the set of prime numbers less than $16$. It’s common to use ellipses if the pattern is clear. For example, writing $\{ 1, 2, 3, \ldots, 10 \}$ rather than $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$.
• A mapping or function is an assignment of inputs (from some set) to outputs. You should already be familiar with functions whose inputs and outputs are real numbers (for example, the function $f$ from reals to reals defined as $f(x) = x^2 + 1$), but functions can have other sets of inputs or outputs. While many functions can be defined by a formula, you can also define them by other means.
• If $f$ is a function with inputs from $A$ and outputs from $B$, we write $f : A \to B$ to briefly express that fact.
• A mapping is one-to-one (or, synonymously, injective) if different inputs get mapped to different outputs. In symbols, a mapping $f$ is one-to-one if $f(x) = f(y)$ if and only if $x = y$ for all $x,y$ from the inputs.
• A one-to-one correspondence (or, synonymously, a bijection) between two sets $A$ and $B$ is a one-to-one function whose inputs come from $A$ and outputs come from $B$, with everything in $B$ being an output of the function. In symbols, a mapping $f : A \to B$ is a bijection if it is one-to-one and for every $y$ from $B$ there is $x$ from $A$ so that $f(x) = y$.
• A set $A$ is a subset of $B$, written $A \subseteq B$ if every element of $A$ is an element of $B$. In symbols, $A \subseteq B$ if $x \in A$ implies $x \in B$. As a special example, the empty set, meaning the set which has no elements, is a subset of any set. (Why?)
• The size or cardinality of a finite set is the number of elements in the set. This size is always a natural number (or $0$, if the set is the empty set). You can also define cardinality for infinite sets, but it is more difficult.

Now for the problems.

1. Consider the function $f : \mathbb R \to \mathbb R$ (in other words, $f$ is a function whose inputs and outputs are real numbers) defined by $f(x) = x^2$. Is $f$ a bijection from $\mathbb R$ to $\mathbb R$? Explain why or why not.
2. Describe a one-to-one mapping from the set of finite binary strings to $\mathbb N$. (A binary string is a list of 0s and 1s, for instance 011110 or 1110001010111. A string is finite if its length is finite.) [Hint: do the strings of length 1, then the strings of length 2, then length 3, and so on.]
3. Describe a one-to-one mapping from the set of infinite binary strings to $\mathbb R$. [Hint: think about how to write real numbers as decimal expansions.]
4. Convince yourself that if $A$ and $B$ are finite sets then there is a bijection $f : A \to B$ if and only if $A$ and $B$ have the same size. [Some sets to consider: the set of fingers on your left hand versus the set of fingers on your right hand; the set of integers between $0$ and $99$ versus the set of integers between $100$ and $199$; the set of sides of a triangle versus the set of corners of a triangle.]
5. How many subsets does a set of size $2$ have? (Don’t forget to include the empty set!) What about a set of size $3$? Size $4$? Come up with formula which tells you the number of subsets a set of size $n$ has. [Hint: define a bijection between the set of subsets of the set $\{1, 2, 3, \ldots, n\}$ and the set of binary strings of length $n$. How many binary strings of length $n$ are there?]

Math 1311: Research Project

Due to time constraints, the oral presentations for your research project will be cancelled.

Videos on the mathematics of chess

The PBS webseries Infinite Series released a video last month about the mathematics of games, specifically focusing on infinite chess. It talks about Zermelo’s theorem, then moves on to discussing infinite games.

Also, in class we briefly talked about how there are more possible games of chess than atoms in the observable universe. This video by Numberphile talks about how to estimate the number of possible games of chess.

Math 1311: Study guide for midterm 2

The second midterm will be Thursday, April 27.

Things you should know for the midterm:

• Truth tables: filling out the truth table for a logical expression, using truth tables to show expressions are equivalent, using truth tables to check validity of an argument. You should also know the truth tables for and, or, not, and if/then.
• How to analyze the logical form of a sentence in ordinary English.
• How to convert between decimal and binary.
• How to compute the nim-sum of a collection of numbers.
• How to determine whether you are in a winning state in a game of nim and how to decide what move to make.

Sample questions:

1. Use truth tables to determine whether the following argument is valid.
• If (A or B) then C.
• Not C.
• Therefore, not A and not B.
2. Use truth tables to check whether “If A then (if B then C)” and “If (A and B) then C” are equivalent. Are they equivalent?
3. Consider the statement “If unicorns eat rainbows then rain drops worship the sun and the moon is not made of cheese”. Which of the following describes the logical form of this statement?
• U and (if R then M).
• If U then (R and not M).
• If U then (not R or not M).
• Not R or (U and not M).
4. Write a truth table for “If A then (not A)”.
5. Write a truth table for “Not A or (if A then not B) or B”.
6. Convert 235 from decimal to binary.
7. Convert 10111010001 from binary to decimal.
8. What is the nim-sum of 7, 13, and 23?
9. You are going to play nim. The set-up for the game is that there are two stacks, one with 5 objects and the other with 7 objects. Do you want to go first or second? If you want to go first, what opening move should you make to ensure that you win no matter how your opponent plays? Justify your answer.
10. You are playing another game of nim. It is currently your turn. There are four piles, with 2, 3, 5, and 8 objects respectively. What move do you make to ensure that you win no matter how your opponent plays? Justify your answer.
11. You are going to play yet another game of nim. The set-up for the game is that there are three stacks, with 7, 10, and 2 objects respectively. Your opponent will play first. However, they are not very observant. You have one extra object in your hand which you could add to one of the three piles without them noticing. (They would, however, notice if you took away any objects.) Assuming that you are okay with cheating in order to win, which stack do you want to add the extra object to? Justify your answer.

Math 1311: Paper

As I mentioned in class, the due date for your paper is being pushed back. Your papers are due Thursday, May 18. Additionally, if you want to give me a draft to get feedback on, I must get it by Thursday, April 27. This gives enough time for me to look at it and get it back to you with sufficient time for you to make any changes.

• 100 points total
• 10 points: Format. Your paper should be 5 to 10 pages, single space, 12pt font, and 1in margins.
• 10 points: Mechanics and sentence structure. You should use proper grammar, spelling, etc.
• 10 points: References and citations. Because this is a research paper, you should have references for the information you provide. All references must be properly cited. Any quotations must be sourced and cited as well. A bibliography or works cited section should appear at the end of your paper. (You can use whatever citation style—MLA, APA, etc.—you want. But be consistent in your formatting.)
• 20 points: Organization. Your paper should be clearly structured. You should have an introduction and conclusion. Information should be presented in a logical order.
• 25 points: Mathematical content. You should clearly and accurately present the mathematical content in your essay. You are not required to include any proofs (though you may do so) but any theorems or results you mention should be stated correctly and in an understandable manner.
• 25 points: Extra-mathematical content. The presentation of the non-mathematical content—bibliographic facts, historic details, connections to a broader context—of your paper should be cogent. You should demonstrate your knowledge of the subject you chose.

Finally, remember that in the last couple weeks of the semester you will give a short (5 to 15 minute) presentation about your topic to the rest of the class. I will give more details on the schedule and the grading for the presentations when we get closer to the end of the course.

Math 1311: Assignment 6

This is due Thursday, April 6.

1. Convert the following numbers from decimal to binary:
• 127
• 94
• 256
2. Convert the following numbers from binary to decimal:
• 101100
• 111000
• 100011
3. Compute the nim-sum of the following groups of numbers:
• 101101110, 100001 and 1110011000 (all in binary)
• 24 and 23 (both in decimal)
4. You are playing a game of Nim with three stacks, containing 12, 10, and 7 objects. Assuming that you want to win, do you want to go first or second? Explain why.

Math 1311: Assignment 5

This homework assignment will be due Thursday, March 30.

Assignment 5

On an unrelated note, you may find this youtube video by Numberphile about the four color theorem to be interesting.

Class canceled Tuesday

Brooklyn College is closed tomorrow, so we will not have class Tuesday, March 14.

This doesn’t effect the exam date, which will still be Wednesday, March 15.