Wednesday, December 06, 2006
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.
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.
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.
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]
2. For any pi, show that invs(pi) + invs(w0 o pi) = invs(w0). Also show invs(w0 o pi) = invs(pi o w0).
Thursday, November 16, 2006
Wednesday Nov 15
Midterm review.
Chinese Remainder Theorem.
Permutations: one-line notation and cycle notation.
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
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:
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
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
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
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.
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
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.
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.
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.)
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
Wednesday, October 25, 2006
Subscribe to:
Comments (Atom)