Wednesday, December 06, 2006

Answers to the final exam

You can view the questions and answers here.

Tuesday, December 05, 2006

Answers, and what to bring to the final

One twist:
To the final you may bring one double-sided sheet of handwritten notes, and your midterms. One question from the midterms will make a surprise appearance!


1a. Let a,b be integers such that a2 = b3.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

ANSWER. Yes, it's true. Write out the prime factorizations, and look at the power of a prime p occurring in the equation: 2ap = 3bp. Hence each bp must be even. Then the product over all p of p(bp/2) is an integer, and a square root of b.

1b. Let a,b be integers such that a10 = b15.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

ANSWER. No. In fact this equation is just the 5th power of the one above! For a small solution to the equation above, take b = 22 = 4, a = 23 = 8. Then this second equation holds but b=4 is not a 10th power of an integer.

1c. Let a,b be integers such that a323 = b391.
Then a,b are both powers of some other integer. What are those powers?

ANSWER. Follow the same analysis as in 1a to get 323ap = 391bp. To simplify this equation, divide by the gcd of 323 and 391, which we can calculate with Euclid's algorithm. 391-323 = 68, 323-4*68 = 323-272 = 51, 68-51 = 17, 51-3*17 = 0. So 17 is the gcd, and dividing we get 19ap = 23bp. Hence each bp is a multiple of 19, and b is a 19th power of some guy, where a is the 23rd power of that same guy.

2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).

ANSWER. The easiest base case is n=0, where this says 0=0. (If you wanted to do the base case n=1 where this says 1/1*2 = 1 - 1/2, that's not so hard either, but it is harder.)

Then for n>0, the LHS can be rewritten as (sumi=1...n-1 1/i(i+1)) + 1/n(n+1) by separating out the last term. (When n=0, there is no term at all, much less a last term.) By induction, the first part of that adds up to 1-1/n. Then we check that
1-1/n + 1/n(n+1) = 1 - 1/(n+1)
which is easy.

3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.

ANSWER. By induction on N. The base case is N=n, which is given to us. (So in fact we're going to show it for all N greater than or equal to n.)

Now we can assume that it's true for N, and wish to prove it for N+1. Look first at (N+1)! = (N+1) N! > (N+1) kN. We would like for that to be > kN+1, i.e. we would like N+1 > k.

We know N+1 > n. Do we know n > k? If not, then n is less than or equal to k, in which case n! is a product of n numbers less than or equal to k, and this product is therefore less than or equal to kn. But we were told that isn't true.

Having reached that contradiction, we learn n > k, so N+1 > k, which was the remaining step in showing that (N+1)! > kN+1. This completes the induction step.

4. Let R,S be two equivalence relations on the same set X.

a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).

ANSWER. Let x,y,z denote elements of X.
Reflexive: since R,S are reflexive, (x,x) is in R and S, hence in the
intersection.
Symmetric: if (x,y) is in R intersect S, it's in both R and S. Since R and S are symmetric, that implies (y,x) is in both R and S. Hence it's in the intersection.
Transitive: same deal as symmetric. If (x,y) and (y,z) are in R intersect S, they're in both R and S. Since R and S are transitive, (x,z) is in both R and S. Hence it's in the intersection.

b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.

Reflexive. Yes. Since for any x we know (x,x) is in R, it's in RuS.
Symmetric. Yes. Say (x,y) is in RuS. Then it's in either R or S. If it's in R, then (y,x) is in R since R is symmetric, so (y,x) is in RuS. Same proof for "in S".
Transitive. No. Say X has three elements {x,y,z}, and R has the associated partition { {x,y}, {z} }, whereas S has the associated partition { {x}, {y,z} }. Then (x,y) is in R, and (y,z) is in S, so both elements are in RuS, but (x,z) is not in RuS.

5. "Let b,c,n be integers, such that bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.

ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bn > cn, for all N>n, bN > cN."
To negate:
"There exists b,c,n integers, such that bn > cn,
and there exists N>n, where bN is less than or equal to cN."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)2 > 22, but (-3)3 is less than 23.

Basically a trick question, in that it had silly negative numbers to confuse you, but at least it wasn't a "Prove or disprove" gotcha question.

Monday, December 04, 2006

Office hours and practice final

I will be available for office hours from 10-1 on Tuesday and Wednesday. HOWEVER these are not drop-in times -- if you want to see me, email me (ideally the night before, or at least half an hour in advance).

I will be putting up practice final questions tonight, with answers posted tomorrow night. Here are the first few:

1a. Let a,b be integers such that a2 = b3.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

1b. Let a,b be integers such that a10 = b15.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

1c. Let a,b be integers such that a323 = b391.
Then a,b are both powers of some other integer. What are those powers?

2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).

3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.

4. Let R,S be two equivalence relations on the same set X.

a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).

b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.

5. "Let b,c,n be integers, such that bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.

Monday, November 20, 2006

Friday Nov 17 and Mon Nov 20

Inversions of a permutation = number of pairs (i < j) such that pi(i) > pi(j).
Neighborly transpositions = (i i+1), in cycle notation.
Theorem: pi can be written as a product of invs(pi) many neighborly transpositions.
Theorem: if pi is written as a product of k neighborly transpositions, then k is greater than or equal to invs(pi), and k is congruent to invs(pi) mod 2.
Definition. An even permutation is one with invs(pi) even, similar def for odd permutations.
Theorem: invs(pi) + invs(rho) is congruent to invs(pi o rho) mod 2.
Theorem: invs(any transposition) is odd.
Theorem: if pi is written as a product of k transpositions, then k is congruent to invs(pi) mod 2.
Theorem: the Sam Loyd 14-15 puzzle is insoluble.

Last HW, due Wednesday Nov 29

1. Let w0 denote the permutation of {1..n} with the most inversions. Show that w0 o w0 = identity.

2. For any pi, show that invs(pi) + invs(w0 o pi) = invs(w0). Also show invs(w0 o pi) = invs(pi o w0).

[More coming in a couple of days]

Thursday, November 16, 2006

Wednesday Nov 15

Midterm review.
Chinese Remainder Theorem.
Permutations: one-line notation and cycle notation.

HW due Monday (short)

1. Let pi be a permutation of {1..n}. When written out in cycle notation (including each i s.t. pi(i)=i as a cycle of length 1), let k be the number of cycles.

Let (i j) be the permutation that switches i and j, and leaves the other elements alone. (So this permutation has n-1 cycles, according to the definition above.)

Show that the product pi * (i j) has either k-1 or k+1 cycles, and explain when it's k-1 and when it's k+1.

5.3 #34,35,38

Tuesday, November 14, 2006

Midterm results

The midterm, with answers, is here.

Grade histogram:

100-80 A ******
80-60 B ****
60-40 C ******
40-20 D **
20-0 F

Monday, November 13, 2006

Answers to the real midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the actual midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the actual midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the practice midterm


1. Say that p is prime, and p | a. Show that for some integer m,
p2 | ma.


Let m=p. Then p | a
=> a = pb for some b
=> ma = mpb = p2b for some b
=> ma is a multiple of p2
=> p2 | ma.


2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.


It is impossible to make a function from X to Y, since the elements in X have nowhere to go. So indeed, every function from X to Y is raining frogs1:1.


3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mn.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.


To specify a function from X to S, we need to say where each element of X goes. We already know where the m elements of S go: to themselves. It remains to specify where the other n-m elements of X go, in S. Each has m independent possibilities, giving mn-m, just as when we counted all functions X->S.


4. Let X be a set. How big can X be, if

  • every relation is symmetric?
  • every relation is transitive?
  • every relation is reflexive?


  • Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.


    Sym: 1. The relation {(a,b)} on {a,b} is not symmetric.
    Trans: 1. The relation {(a,b),(b,a)} is not transitive.
    Ref: 0. The relation {} on {a} is not reflexive.


    5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).


    For p o f to not be onto, either everything in X goes to even, or to odd.
    If X all goes to odd, then f:X->Y has to take everything to 1. One function so far.
    If X all goes to even, then f:X->Y is really a function to {0,2}, and there are 23 such functions. Eight more.

    Forgive me for not drawing these in ASCII.


    6. (The "Freshman's Dream".) Let a,b be integers. Show that
    (a+b)3 is congruent to a3+b3 mod 3.


    (a+b)3 = a3 + 3a2b + 3ab2 + b3.
    So the difference between that and a3 + b3 is 3(a2b + ab2), a multiple of 3.


    7. Is the same true with each 3 replaced by 4?
    (I shouldn't have to add:) If true, prove it; if false, provide a counterexample.


    No; let a,b=1. Then (a+b)4 is 0 mod 4, but a4+b4 is 2 mod 4.
    (In fact it holds for all prime exponents.)

    Saturday, November 11, 2006

    Some practice midterm questions

    If having thought about a question you decide you're really stuck, leave a comment asking for a hint. Conversely, if you have a hint to suggest, leave that comment!

    1. Say that p is prime, and p | a. Show that for some integer m,
    p2 | ma.

    2. Let X be a set with 5 elements, and Y a set with 0 elements.
    Show that every function from X to Y is 1:1.

    Yes, really. This question is written correctly, and means exactly what it says.

    3. Let S be a subset of X, where S has m>0 elements and X has n elements.
    We already showed that the number of functions from X to S is mn.
    How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.

    (I'll leave the actual number in the comments, but then you still should think about proving it.)

    4. Let X be a set. How big can X be, if

  • every relation is symmetric?
  • every relation is transitive?
  • every relation is reflexive?


  • Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.

    5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).

    6. (The "Freshman's Dream".) Let a,b be integers. Show that
    (a+b)3 is congruent to a3+b3 mod 3.

    7. Is the same true with each 3 replaced by 4?
    (I shouldn't have to add:) If true, prove it; if false, provide a counterexample.

    Friday, November 10, 2006

    Office hour today 3-4 / Midterm topics

    Usually it's 4-5 (after class), but there being no class I'm moving
    it up an hour.

    This midterm will be run the same as the last one. Focus on number theory, equivalence relations, and 1:1/onto properties of functions.

    Wednesday, November 01, 2006

    Wednesday Nov 1

    Properties of functions: injective AKA 1:1, surjective AKA onto, bijective.
    Functions have inverses iff they're 1:1 and onto.
    If f,g are injective, so is g o f.
    If g o f is injective, so is f (maybe not g).

    Statement: every function X -> Y can be factored as a surjection X -> X/~, then a bijection X/~ -> S, then the inclusion of a subset S -> Y.
    We'll prove it next time.

    Monday Oct 30

    Equivalence relations vs. "partitions" of a set.
    From a partition, we built an equivalence relation, and vice versa.
    (There's lots to check about these recipes, and it took the whole hour, without even getting to prove that each recipe was the other's inverse.)

    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.