Math 300:01 Introduction to Mathematical Reasoning
Prof. Weibel, Fall 2003
Homework Assignments
Return to Weibel's Math 300 page
current assignment
proper homework format
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''.)
- For all elements x belonging to S there is a y belonging
to S such that x+y is a multiple of 3.
- There exists an element x belonging to S such that for all elements
y belonging to S, x+y is a multiple of 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.
- 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.
- For any two real numbers a and b, if a < b then
a2 < b2.
- 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'.)
- For any positive number a and positive number b,
the square of their average is greater than their product.
- For any positive integer a, positive integer b and positive
integer c, a(bc)=(ab)c.
- For any a>=0 and b>=0, sqrt{a+b} < sqrt{a}+sqrt{b}.
- 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.
- Suppose you replace the words ``real number'' by ``integer''
in each of the statements. Which of the seven statements
is now false? Explain.
- 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.
Due Oct. 20: Re-read supplement 5, and read supplement 6.
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).
- (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).
- If a is a real number and f(x) is a polynomial such that f(a)=0,
show that (x-a) divides f(x).
- Prove or disprove: the relation g|f is a partial ordering on
the set of monic polynomials.
- End of chapter 4, problem 3(a,b,c).
- 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.
- 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.
- 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.
- 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.
Return to Weibel's Math 300 page