# Math 300:01 Introduction to Mathematical Reasoning Prof. Weibel, Fall 2003 Homework Assignments

Due Thursday Sept. 11th:
1. p.13 Exercises 1.3.2 and 1.3.3
2. Consider a collection of small square tiles. It is known that each tile has a letter on one side and a positive integer on the other side, but no other information is known about the tiles. The tiles are laid out, some with letter side up and some with number side up.
Someone tells you, ``Every tile that has a vowel on one side has an odd number on the other side''.
Which tiles need to be examined in order to check whether this is true? Explain your answer.
(Hint: you should not try to do this problem without making up some examples for yourself and thinking them through.)

3. Four people, Bob, Carol, Ted and Alice, are walking in the mountains at night with one flashlight. They arrive at a chasm that is crossed by a flimsy rope bridge. They decide that at most two people can cross at a time, and whoever crosses must have the flashlight with them. None of them can throw the flashlight across the bridge.
Each person walking alone would need the following amount of time to cross the bridge:
 Bob 1 minute; Carol 2 minutes; Alice 5 minutes; Ted 10 minutes;
Whenever two people travel together, they go at the speed of the slower person.
Determine the fastest way to get all four people across the bridge. Give a careful argument that your plan is best possible.

Due Sept. 18:
1. (From text) Exercises 1.7.1, 1.8.5(2,3,5,6), 1.8.7 and 1.11.1
2. Let S denote the set {1,4,11,14,17,19}. For each of the following statements, determine whether the statement is true or false.
Give a careful explanation for each answer. (Hint: ``careful'' does not mean ``long''.)
1. For all elements x belonging to S there is a y belonging to S such that x+y is a multiple of 3.
2. There exists an element x belonging to S such that for all elements y belonging to S, x+y is a multiple of 3.
3. For all x belonging to S there is a y belonging to S such that x+y is a multiple of 5.

3. Here are seven universal statements. For each one, (i) prove that the statement is incorrect, and
(ii) if possible, find a simple restriction of the hypothesis of the statement that makes it true. (This is not possible for all of them.)
In choosing your restriction, try to add a condition which is least restrictive.

1. For any positive integer a, positive integer b and positive integer c, if bc is a multiple of a then b is a multiple of a or c is a multiple of a.
2. For any two real numbers a and b, if a < b then a2 < b2.
3. For any four positive real numbers a,b,c,d, if ab < cd then (a+b) <= (c+d). (The symbol `<=' means `less than or equal to'.)
4. For any positive number a and positive number b, the square of their average is greater than their product.
5. For any positive integer a, positive integer b and positive integer c, a(bc)=(ab)c.
6. For any a>=0 and b>=0, sqrt{a+b} < sqrt{a}+sqrt{b}.
7. For any two real numbers x1,x2 belonging to the interval [- π , π ], if sin(x1)=sin(x2) then x1=x2.
(The symbol `π' is the Greek letter "pi".)

4. In section 8.1 of the book on page 180 are listed five ``bullets'' which state some properties of the real numbers. Bullets 1,2 and 5 each give a single universal statement, bullet 3 has two existential statements, and bullet 4 has two universal statements, for a total of 7 statements.

1. Suppose you replace the words ``real number'' by ``integer'' in each of the statements. Which of the seven statements is now false? Explain.
2. Suppose you replace the words ``real number'' by ``positive integer'' in each of the statements. Which of the seven statements is now false? Explain.

Due Sept. 25: Read supplement 3
1. Exercises 2.3.15 (p.47),   2.4.4 (p.48)   and problem 5 at end of section two (p.54).

2. Prove: ``For all positive real numbers x and y, x/y+y/x is greater than or equal to 2.''

3. Prove: for all positive real numbers x, y satisfying x² < y there exists a real number z satisfying x < z and z² < y . (Hint: There is an example in supplement 3 that is very similar to this.)

4. Consider the following statement: ``For all integers x,y,z, if z is a divisor of x and z is a divisor of y then 2z is a divisor of x+y.'' Here is a faulty proof:

Proof. We use the arbitrary value method. Let a, b, and c be arbitrary integers such that c is a divisor of a and c is a divisor of b. We will show that 2c is a divisor of a+b.
Since c is divisor of a, there is an integer k such that ck=a. Since c is divisor of b, there is an integer k such that ck=b. Then a+b=ck+ck=2ck. Since k is an integer, we conclude that 2c is a divisor of a+b.
Since a,b and c are arbitrary integers satisfying that c is divisor of a and c is a divisor of b we conclude that for all integers x,y,z if z is a divisor of x and z is a divisor of y then 2z is a divisor of x+y.
Use ``test by trial value'' (see supplement 3) to uncover the flaw in the proof and carefully explain the flaw.
Due Monday Oct. 6: Read supplement 4
1. Exercises 3.2.3 and 3.2.6 (p.62).
2. Problem 1 at the end of section three (p.64).

3. Prove: For all positive integers n,  52n -1   is divisible by 8. Note that this fails for 5n-1.

4. Prove: For all real numbers x >= -1 and for all nonnegative integers n, (1+x)n >= 1+nx.
(The symbol `>=' means `greater than or equal to'.) A distraction: equality holds when x=0.

Due Oct. 9: Read supplement 5
Consider the following statement: ``Every system of n [nonzero] equations in n unknowns has a solution.'' This means that for every family of real numbers aij and bi (i,j=1,...,n) [where for each i there exists a j such that aij is nonzero] there exists some sequence of real numbers x1,...,xn satisfying the following system of equations indexed by i=1,...,n:
ai1 x1 + ... + ain xn = bi.
Here is a faulty proof:
We will proceed by induction on the number n of equations. The inductive hypothesis is that every system of n equations in n unknowns has a solution. If n=1 this means that ax=b has a solution [where a is nonzero], which is x=b/a. Inductively, suppose the assertion is true for n, and consider a family of n+1 equations in n+1 unknowns x1,...,xn+1. For i=n+1, there is a j so that an+1,j is nonzero. By reindexing the variables, we may assume that j=n+1. Set a= an+1,n+1. The last equation yields an equation giving xn+1 in terms of the other variables: xn+1= (bn+1/a)- (an+1,1/a) x1 - ... - (an+1,n/a) xn. Substituting it into the first n equations allows us to elimiinate xn+1 to get n equations in n unknowns. By induction, there are real numbers x1,...,xn solving that system of equations. Plugging these values into the last equation gives a real number xn+1, and the resulting set of n+1 variables xj solves the original system of n+1 equations.
The principle of mathematical induction allows us to conclude that every system of n equations in n unknowns has a solution.
• First apply this proof (with n=1) to show that the system of 2 equations in 2 unknowns has a solution: 2x+3y=2; 3x+4y=7.
• Then uncover the flaw in the proof and carefully explain the flaw.
There are certain steps in the proof which are not fully verified; I do not care about steps which can be verified, I care about the step (or steps) which cannot be verified.
Redo the first exam, and turn it in for re-grading. In problem 5, describe the union and intersection of the lines using inequalities and prove that your answer is correct.
Due Oct. 27: Read supplement 7. All polynomials in this assignment have real coefficients, and indeterminate x.
Definition: We say that g(x) divides f(x), and write g|f, if there is a polynomial h(x) such that f(x)=g(x)h(x).
1. (Euclidean Algorithm) Let g(x) be a fixed nonzero polynomial. Show that for every polynomial f(x) either g|f, or there are polynomials h(x) and r(x) such that f(x)=g(x)h(x)+r(x) and degree(r) < degree(g).
2. If a is a real number and f(x) is a polynomial such that f(a)=0, show that (x-a) divides f(x).
3. Prove or disprove: the relation g|f is a partial ordering on the set of monic polynomials.
4. End of chapter 4, problem 3(a,b,c).
5. End of chapter 4, problem 12.

Due Nov. 3: If ~ is an equivalence relation on a set A, the equivalence classes are just the subsets Ta forming the partition of A.
1. Define the relation ~ on set S=N² of pairs of natural numbers by: (a,b)~(c,d) if a+d=b+c.
Show that ~ is an equivalence relation, and prove that the equivalence classes may be identified with the integers.
2. Let f: X -> Y be a function. Define a relation on X by: x~x' if f(x)=f(x').
Show that ~ is an equivalence relation, and prove that the equivalence classes may be identified with a subset of Y.
3. End of chapter 4, problem 17.

Due Nov. 10: Chapter 5,
Exercises 5.1.10, 5.1.14, and 5.1.15
Let B be any set. Prove that there exists a unique function f from the empty set to B, and that f is one-to-one.

Due Nov. 17: Problem 5.2.4, and prove 5.2.10
End of chapter 5, problems 5(a,b), 9, 27(b)
Due Nov. 24: Prepare for exam on Tuesday 11/25, covering 4/5/8
Problems 1,3,4,5(c,d) from Workshop on Thursday 11/20.
Happy Thanksgiving!

Due Dec. 8: Read chapter 7, sections 1-4
1. Let S,T be finite sets of the same cardinality n, and f: S --> T a function. Show that
i) if f is one-to-one, then f is a bijection;
ii) if f is onto, then f is a bijection;

2. If p,q are prime numbers, let S be the set {1,2,...,pq} and let T be the set of pairs (a,b) of integers with a between 0 and p-1, and b between 0 and q-1.
i) Show that card(T)=pq.
ii) Consider the function f: S --> T sending a number r to (a,b), where r is congruent to a(mod p), and to b(mod q). Show that f is one-to-one. Hint: If s>r and f(r)=f(s), show that f(s-r)=(0,0).
iii) Show that the function f in (ii) is a bijection.

3. Exercise 7.1.2.2 and 7.1.6
4. Show that for every n, the set Zn is countable.
Here Zn denotes the set of all length-n sequences (a1,...,an) of integers.

## Proper homework format

The grader and I will attempt to carefully grade your work, and give you feedback on it so that you can improve your skills. This is time consuming work, but is an important part of your learning in this course. Evaluating student's work is made more difficult (or impossible) when it is sloppily written, when there are loose pages, when there are many words crossed out, etc. So you have to do your part to help us evaluate your work efficiently. Your homework must conform to the following rules:
• Work should be written on 8x11 paper without ragged edges.
If you tear pages out of a spiral notebook, be sure to cut off the ragged edges with a scissors.
• Your name should appear at the top of each page. Pages should be numbered and stapled together.
• You should have a cover page which gives your name and a list of the problems that were assigned.
• Your work should be presented neatly and legibly and your writing should be readable size. Also, you should make sure that you leave sufficient space for me to write comments.
After writing out your homework, you should check it for readability, and, if necessary, rewrite it.
• The rules of English grammar (including those of spelling and punctuation) should be obeyed.
• In the case of problems with a short answer, it is not enough to only give the answer. You must include enough additional information (explanations, diagrams, etc.) to justify your answer.
• Each problem should be followed by an ``Acknowledgement'' that provides the contributions of others (including the instructor) to your solution. For example, you might say ``Acknowledgement: Phil Smith explained the problem statement to me'' or ``Acknowledgement: I discussed this problem with Jennifer Jones'' or ``Acknowledgement: Professor Weibel got me started on this problem'' or ``Acknowledgement: I found a problem like this worked out in the book `Isn't Math Wonderful' by A. Bacus.''
If you worked entirely on your own you should write ``Acknowledgements: none''.
As an alternative, you may put a list of all of your acknowledgements on the cover page.