Monday, October 30, 2006

HW due Nov 6

4.3 #33,37,43,47
4.4 #54
5.1 #1,6,7

Wednesday, October 25, 2006

HW due Monday Oct 30

[FP]
3.5 #102,106
4.1 #16
4.3 #29
4.5 #69,73,82

IMPORTANT REMINDER

No class or office hour on Friday Oct 27.

Wed Oct 25

Ordered pairs. Cartesian product. Relations. Functions. Equivalence relations.

Monday Oct 23

Congruence notation and some applications (divisibility by 9,3,37,11).

Friday, October 20, 2006

Friday Oct 20

Finished proving unique factorization.
Noted that in other contexts, like Z[i] and Z[sqrt{-5}], the primes may be different, and unique factorization may fail.
Used unique factorization to study the following question: what fraction of integer points in the plane are visible from the origin? Answer: 6/pi2.
Notation: pa || n if p is prime and pa|n but pa+1 doesn't |n.

Wednesday Oct 18

Midterm review.
We proved existence of factorization of natural numbers into primes (by strong induction).
We started proving uniqueness.

Tuesday, October 17, 2006

HW #3 due Monday Oct 23

From [FP]:

3.1 #2,7,9,13
3.2 #20,35
3.4 #84,92,93

Monday, October 16, 2006

Results of midterm #1 -- LINK CORRECTED

The midterm with answers is available here in PDF. (Really this time!)

The grading is done. The number -> letter correspondence is as follows:

0- 20 F 1 of these
20- 40 D 4 of these
40- 55 C 5 of these
55- 75 B 5 of these
75-100 A 4 of these


What do these letters mean?

If the term ended today, and all records of your homework disappeared so that only midterm #1 could form the basis of your grade, that's what I'd give you. It's only here so that your final grade won't be a big surprise.

I am not going to toss out the number and average together the letters you get, at the end of the course. So there is no point worrying about "I got a 74 instead of a 76 -- please give me two more points!" It's exactly like someone with a 76 looking for a 78.

Thursday, October 12, 2006

Topics of midterm #1

From [FP]: sections 1.2-1.6, 2.2, 3.1-3.2.
From class: definitions from class related to graphs. (They'll be written on the test, too, but better if you already know them!)

There will be problems of the form

"Here is an English statement.
Which of the following statements follow from it?
[big mess of for-alls vs. there-exists in various different orders]."

You should be able to write out a proof by weak induction -- base cases, induction step, everything in place.

Wednesday, October 11, 2006

Wednesday Oct 11

We finished proving that Euclid's algorithm works. This required strong, not just weak, induction.
The main consequence: the GCD of A and B can be written as mA+nB for some integers m,n. With this we'll eventually prove that integers have unique factorizations into primes.

Next time (Friday) we'll review the course to date, in preparation for the first midterm, on Monday October 16. See the course web page for details.

Monday, October 09, 2006

HW #2 solutions (non-book problems)

1. Show that n3-n is a multiple of 6, for any integer n.

Answer. Write n = 6m + r, where r is one of 0,1,2,3,4,5.
Then n3-n = (6m+r)3 - (6m+r) = some multiple of six plus r3 - r.
Then we check r3-r for each possible r, getting 0,0,6,24,60,120, each of which is a multiple of six.




2. Let G be a connected graph and v a vertex of degree 1. Using the
vertex-based definition we came up for of connectedness, prove that
the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v...")




A. Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v of vertices v_1..v_n such that v_1=w, v_n=x,
and {v_i,v_{i+1}} is an edge for each i=1..n-1.

Since G is assumed connected, we know there exists such a chain
of vertices in G, call it (w_1..w_m). (So w_1=w, w_m=x.)
(If for all i, w_i is not v, then this chain is also in G\v,
but we have to deal with the possibility that some w_i=v.)

Let u be the unique vertex such that {u,v} in E_G (unique by the
assumption that degree(v)=1).

For each i such that w_i=v, the only possibility for w_{i-1},w_{i+1} are
that each is equal to u. (Note that i is not 1 or n, since w,x are not v.)
Remove w_i, w_{i+1} from the chain, so that the new, shorter chain
goes ...,w_{i-1},w_{i+2},... We need to be sure that this still
has each vertex adjacent to the next one:
{w_{i-1},w_{i+2}} = {u,w_{i+2}} = {w_{i+1},w_{i+2}} in E_G. Voila.

In this way, we have constructed a chain of vertices connecting w to x,
none of which are equal to v. So this new, shorter chain is in G\v.
Since w,x were any two vertices of G\v, this shows G\v is connected.



3. Let G be a graph and v a vertex of degree 1. Assume that the
deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself...")




A. Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself.

As in #2, let u be the unique element of V_G to which v is connected.
Note that u is not equal to v, so u is a vertex of G\v.

There are then two cases: u in V1, or u in V2, since V1 union V2 = V_(G\v).

Assume u in V1. Let V1' = V1 union {v}.
Then we claim that (V1', V2) is a decomposition of G.
There are several things to prove:
1. V1' union V2 = V_G
2. V1' intersect V2 = {}
3. For any vertex a in V1' and b in V2, {a,b} is not in E_G.
We take them in order.

1. V1' union V2 = {v} union V1 union V2 = {v} union V_{G\v} = V_G,
by the definition of V_{G\v} as V_G with only v ripped out.
Also, we know V1 union V2 = V_{G\v} by the assumption that
they form a decomposition of G\v.
2. We know V1 intersect V2 = {}, by the assumption that they form
a decomposition of G\v. So the only chance for V1' to
share an element with V2 is if v is in both. But since
V1 union V2 = V_{G\v} doesn't contain v, V2 doesn't.
So V1' intersect V2 is empty.
3. a is either in V1, or a=v. Since V1,V2 is a decomposition,
if a is in V1 then there is no b in V2 with {a,b} in E_G.
So the other case is a=v. But then the only b in V_G such that
{a,b} is in E_G is b=u. And u is in V1, by assumption.
Hence u is not in V2, since V1 intersect V2 = {}.
So there is no b in V2 such that {a,b} is in E_G.

The other case, u in V2 instead of V1, is exactly the same except
with "V1","V2" switched throughout the proof.




4. What's the relation between #2 and #3?




A. We proved (mostly) in class that a graph has a decomposition iff it
is not connected. In light of that, #2 is equivalent to the
contrapositive of #3.

G connected ===> G\v connected
has contrapositive
G\v disconnected ===> G disconnected
or equivalently
G\v has a nontrivial decomposition ===> G has a nontrivial decomposition

Monday Oct 9

Weak induction proof of the "division algorithm".
GCDs. Euclid's algorithm for computing GCDs.
We started proving, by strong induction, that this does actually compute GCDs, but didn't finish it.

Friday, October 06, 2006

Friday Oct 6

Examples of weak induction proofs.
Thm: 1 + 2 + ... + n = (n+1 choose 2).
Thm: The number of subsets of X is 2|X|, for X finite.
Thm: If G is a finite graph, the sum of the degrees is even.

Next time: Euclid's algorithm for computing GCDs, and a proof that it works, using strong induction.

Wedneday Oct 4

Two properties we will need of the naturals: only 0 is not a successor, and every nonempty subset has a least element (Well-Ordering). Examples of non-well-ordered sets.
Weak induction. Strong induction.
Theorem about theorems: weak induction proofs are actually proofs. Proof: uses Well-Ordering.
Sample weak induction proof: If n>4, then 2n > n2.

Monday Oct 2

Basic proof technique: splitting into cases.
Sample theorem: For any integer n, n(n-1)/2 is an integer too.
Proofs by contradiction are "really" splits into the cases "what I want to be true is true vs. what I want to be true is false."
When a proof by contradiction is silly.
Why proofs by contradiction are dangerous.

Monday, October 02, 2006

HW #2: due Oct 9

1. Let n be an integer. Prove that n3-n is a multiple of 6.

2. Let G be a connected graph and v a vertex of degree 1. Using the vertex-based definition we came up for of connectedness, prove that the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there exists a chain in G\v...")

3. Let G be a graph and v a vertex of degree 1. Assume that the deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to build one of G itself...")

4. What's the relation between #2 and #3?

From [FP]:

1.4 #56,58,59,67
1.5 #84,90
1.6 #93,99,100,102