The notation "MN" refers to the Matoušek--Nešetříl text
The notation "LIN" refers to the instructor's Linear Algebra notes, currently in progress.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the
instructor's attention) and no deadline (except they expire when
discussed in class). Make sure you hand them in on a separate sheet,
state your name, the fact that this is a challenge problem
solution, and indicate the problem being solved. One further
request: if you hand in a solution a challenge problem, send email to the
instructor giving the problem number and the brief indication of the
problem (copied from the problem announcement: like "n+1 numbers"
or "another limit related to the def of "e"" -- no detailed description
needed, this suffices to remind me which problem it was). Such
email will create an easy record and help avoid mistakes in bookkeeping.
-- Please also send me email at this time about challenge problems
to which you handed in solutions earlier in this course. This will
help me create a complete record.
REWARD PROBLEMS are challenge problems that you should NOT hand in.
The solution is its own reward. No deadline. Of course you may discuss
your thoughts with the TAs and the instructor.
If you hand in material before its due date, make sure you
put it on a separate sheet since solutions are graded in batches
by their due dates.
17.1 READ LN Chapter 8 (Finite Markov Chains) (entire chapter; especially
the Perron-Frobenius Theorem)
17.2 HW: Determine the common (complex) eigenvectors of the
2 × 2 rotation matrices Rα discussed
in class (the first row is cos(α), -sin(α); the second
row is sin(α), cos(α)). (5 points)
17.3 DO: Determine Φ15(x) (the 15-th cyclotomic
polynomial).
17.5 DO: Prove: for n ≥ 2,
the sum of the n-th roots of unity is 0.
17.6 CHALLENGE PROBLEM. Prove that the sum of the primitive n-th
roots of unity is always 1, -1, or 0.
17.7 DO: LN 6.2.27 (periods of vertices in same strong component of
a digraph are equal)
17.8 HW: LN 8.1.33 (if the period of every vertex of a (not
necessarily irreducible) finite Markov Chain is divisible by d
then we can multiply each eigenvalue by any d-th root of unity)
(10 points)
17.9 HW: Read LN 8.2.1 with reference to Figure 8.3 (rather than 8.2,
a typo). Solve parts 1-4 (2+2+2+8 points) DO: part 5.
BONUS PROBLEM: Find the eigenvalues of the transition matrix without
any calculation. Describe your argument. (5 points)
16.1 HW The commutator of two group elements a and
b is the element
a-1b-1ab.
The support of a permutation is the set of elements
it actually moves. For instance, the support of the
permutation (27)(394) is the set {2,3,4,7,9}.
Consider two cycles in the symmetric group; assume that their
supports overlap in exactly one element. (For instance, the 3-cycle (123)
and the 6-cycle (345678).) Prove that their commutator is a
3-cycle. (5 points)
16.2 DO Find two permutations that commute even though their supports
overlap in more than one element.
16.3 HW The cycle structure of a permutation is a nondecreasing
sequence of integers ≥ 2 which describe the lengths of its disjoint
cycles. For instance, the permutation (95)(27)(3648) has cycle
structure (2,2,4). Count those permutations of n elements which
have cycle structure (5,5,5). (6 points)
16.4 DO: (a) Show that (123)(45678) as well as (1234)(5678)
are permutations which have "square roots"; but (123)(4567) does not
have a square root. (b)
Characterize the cycle structures of those permutations
which have a "square root."
16.5 DO: A permutation f is fixed-point-free if
xf ≠ x for all x in the permutation
domain (all points move, no point remains fixed). Prove: the number
of fixed-point-free permutations in
Sn is asymptotically n!/e.
16.6 DO: Prove: if all entries of an n×n matrix A
over the complex numbers are ≤ r in absolute value then
| det(A) | ≤ rnn!.
16.7 CHALLENGE PROBLEM. (Hadamard's Inequality)
Prove that under the conditions of the preceding problem,
| det(A) | ≤ rnnn/2.
16.8 DO: Prove: if all entries of a square matrix A are integers
then det(A) is an integer.
16.9 HW Let A be an n×n real matrix
of which all entries are ± 1. Prove that det(A) is
divisible by 2n-1. (6 points)
16.10 HW Let A be a matrix over the field F and
let v1,...,vk be eigenvectors:
Avi= λivi
and vi ≠ 0.
Assume all the λi are distinct. Prove that
the vi are linearly independent. (10 points)
(Hint: induction on k.)
16.11 BONUS PROBLEM. Suppose we have k pairwise independent
non-constant random variables over a sample space of size n.
(a) Prove n ≥ k. Hint: first show that we may assume
each variable has zero expectation. Then show that the variables
are linearly independent (as functions from the sample space to
the reals - what is the dimension of that space?). (b) Prove
that n ≥ k+1. (6+2 points)
16.12 BONUS PROBLEM. Let A be an n×n matrix
over the field F2 of order 2. Assume all columns
of A are distinct. Prove: rk(A) ≥ log2n.
(6 points)
16.13 BONUS PROBLEM. LIN 2.5.2 (Sam Lloyd's puzzle) (6 points)
16.14 CHALLENGE PROBLEM. Prove that for an n×n matrix
A, the following are equivalent: (a) all expansion terms of
det(A) are zero; (b) A has a (k+1) × (n - k)
all-zero submatrix (i.e., all entries in the intersection of certain
k+1 rows and n - k columns are zero) for some k,
0 ≤ k ≤ n - 1.
15.1 READ LIN Chapter 1 (Basic Structures), Chapters 2.1, 2.2, 2.4,
2.5, 2.11 (basic group theory to the extent needed in this course),
Chapter 3 (first concepts of linear algebra). (LIN is a new on-line
lecture note in progress, see the top of this page for a link.)
15.2 DO: all non-starred exercises in LIN, Chapter 3.
15.3 HW: LIN 3.2.5 (union of two subspaces) (5 points)
15.4 BONUS PROBLEM: LIN 3.2.6 (union of several subspaces) (8 points)
15.5 HW: LIN 3.3.11 (subfield) (5 points)
15.6 HW: LIN 3.6.4 (Fibonacci-type sequences) (2+4 points)
15.7 HW: LIN 3.6.5 (rank of the matrix (i+j)) (6 points)
14.1 REVIEW all previous material for Tuesday's test. The test includes
linear independence, rank, subspace, span, systems of linear equations
(from class) but does not include determinants and eigenvalues.
14.2 HW: Let A and B be real matrices. Prove:
(a) rank(AB) ≤ rank(A) ;
(b) rank(A+B) ≤ rank(A)+rank(B).
14.3 DO: Let A and B be n × k real matrices.
Prove: if for
every vector x ∈ Rn we have
Ax = Bx then A = B.
13.1 READ LN Chap 6.2 (digraphs) pp 56-61.
13.2 READ LN Chap 8 pp 79-81 (first three pages of the Finite Markov Chains
chapter)
13.3 READ MN Chaps 3.4 and 3.5 (Eulerian graphs) and Chap 3.6 (Eulerian
digraphs)
13.4 READ MN Chap 10.6 (Random walk)
13.5 DO: MN 3.6.4 (p.131) (Eulerian orientations)
13.6 DO: MN 3.6.6 (p.131) (even cycles in digraphs)
13.7 DO: MN 3.6.8 (p.131) (tournament has Hamilton path) [not Hamilton cycle,
as previously mistakenly posted]
13.8 BONUS PROBLEM Prove that every strongly connected tournament has
a directed Hamilton cycle (6 points)
13.9 DO: LN 6.2.2, 6.2.3 (number of orientations)
13.10 DO: LN 6.2.4 (sum of in-degrees = sum of out-degrees)
13.11 REWARD PROBLEM LN 6.2.7 (number of quadratic residues)
13.12 DO: LN 6.2.20 (DAG <==> ∃ topological sort)
13.13 DO: LN 6.2.22 (counting walks by the adjacency matrix)
13.14 DO: LN 6.2.23 (regular tournament has an odd number of vertices)
13.15 DO: LN 6.2.24 (find strong components in picture)
13.16 DO: LN 6.2.25 (divisor graph)
13.17 DO: LN 8.1.2 (powers of a stochastic matrix are stochastic) (give an
elegant proof which involves no summations) (Hint: multiply to the right
by the all-ones column vector)
13.18 DO: LN 8.1.4 (in transition digraph, all outdegrees are ≥ 1)
13.19 HW: LN 8.1.8 (limit of the powers of a transition matrix)
(7 points)
Remember: problems 11.10, 11.11 and bonus problem 11.12 are due Nov 6.
12.1 READ LN, Chap 7 (Finite Probability Spaces) in full.
12.2 HW: Let us consider a sequence of n coin flips;
we represent the outcome of the experiment as a string of length
n over the alphabet {H,T}. Let X be the number of
occurrences of HTT as a substring of 3 consecutive coin flips;
and let Y be the number of occurrences of HTH. For instance
if the outcome of the experiment is the string HTTTHTHTHT then
X = 1 and Y = 2.
12.3 BONUS PROBLEM. (Strongly negatively correlated events) LN 7.6.6.
(6 points)
11.1 READ the relevant parts of MN, including Cayley's formula
for the number of trees, the Prüfer code, inclusion-exclusion,
the "derangement problem" (chapter 2.8). Review the multinomial theorem.
11.2 READ the relevant parts of LN, especially the independence of
random variables. Check Inclusion-Exclusion in Wikipedia.
11.3 HW: Prove: almost all graphs are not planar. In other
words, let pn denote the probability that a
random graph on a given set of n vertices is planar.
Prove that lim pn = 0 (as n goes
to infinity). A random graph on a given set of n
vertices is constructed by flipping an unbiased coin n
choose 2 times to decide adjacency between each pair of
vertices. (So for each pair (i, j) of vertices, the
probability that i and j are adjacent is 1/2
and these n choose 2 events are independent.)
(10 points)
11.4 CHALLENGE PROBLEM. Prove that
pn < exp(-|Ω(n2)|)
where pn is the probability of planarity
defined in the preceding problem and exp(x) means ex.
11.5 DO: We roll n dice. What is the expected value of
the product of the numbers seen? Your answer should be a
very simple closed-form expression.
11.6 DO: Prove: the events
A1,...,Ak are independent
if and only if their indicator variables are independent.
11.7 HW: We say that the random variables X and Y are
uncorrelated if E(XY)=E(X)E(Y).
Construct two random variables which are uncorrelated but not
independent. Use the smallest possible sample space.
(6 points; +2 bonus points for a proof that your
sample space is indeed smallest).
11.8 DO: Let X be a random variable and r a real
number. Let A denote the event that X = r.
Prove: there exists a polynomial f such that f(X)
is the indicator variable of A.
11.9 DO: (Making dependent variables independent)
Let G be a random graph on the vertex set [n].
Let D(i) denote the degree of vertex i. (a) Are the
random variables D(1) and D(2) independent? (b)
Are they independent under the condition that vertices 1 and 2 are adjacent?
(c) Are they independent under the condition that vertices 1 and 2 are
not adjacent?
11.10 HW: (Due Tuesday, Nov 6) (Truncated inclusion-exclusion)
With the notation used in class,
the Inclusion-Exclusion formula (in the probability version) says that
P(B) = S0 - S1 + S2 - ... .
11.11 HW: (Due Tuesday, Nov 6)
Find an infinite family of connected planar graphs
Gn
with two specified vertices sn and tn
such that (a) Gn has O(n) vertices;
(b) there are exponentially many shortest paths between
sn and tn. Here "exponentially
many" means exp(|Θ(n)|) where
exp(x) means ex. (9 points)
11.12 BONUS PROBLEM (Due Tuesday, Nov 6) For every n,
let Gn be a connected graph with n vertices
and let sn and tn be two vertices
of Gn. Prove that the number of shortest paths
between sn and tn is
exp(|O(n)|). (6 points)
10.1 READING: MN Chapter 5 (drawing graphs) In Chap 5.1 you may ignore
the part about drawing graphs on surfaces other than the plane and the
sphere.
10.2 READING: LN pp.53-55 "Planarity" (ignore the bottom portion of p.55
starting with the section title "Ramsey Theory"). Make sure you understand
Kuratowski's Theorem.
10.3 HW: LN 6.1.63 (bipartite nonplanar graph without a subdivision of
K3,3) (5 points)
10.4 DO: (a) Prove: a connected nonplanar graph has at least n+3 edges.
(b) Prove that this inequality is tight for every n ≥ 6, i.e.,
for every n ≥ 6, there exists a nonplanar graph with
n+3 edges.
10.5 HW: Prove: every planar graph has a vertex of degree ≤ 5.
(Hint: The proof should be just a couple of lines. Use the
m ≤ 3n - 6 theorem.) (5 points)
10.6 HW: Prove: every planar graph is 6-colorable. The proof should be
very simple, using the preceding exercise. (5 points) (Note: actually,
every planar graph is 4-colorable. This is the famous 4-Color Theorem.)
10.7 DO: Prove: If every vertex of a planar graph G
has degree ≥ 5 then G has at least 12 vertices of
degree exactly 5. ("Soccerball problem" - if you sew a ball together
from pentagons and hexagons, you need at least 12 pentagons)
10.8 DO: Let G be a plane graph (drawing) with at least 3 vertices.
Prove that the following are equivalent: (a) all faces of G are
triangles; (b) G has exactly 3n - 6 edges.
10.9 DO: (a) Prove, using Euler's formula: if a planar graph with
at least 3 vertices contains no triangle then m ≤ 2n - 4.
(Hint: solve LN 6.1.58 and LN 6.1.60.)
(b) Infer that K3,3 is not planar.
10.10 HW: Suppose both the graph G and its complement are planar.
Prove: n ≤ 10. (6 points)
10.11 DO: Prove that every tree is bipartite. (Hint: induction using
the fact that a tree with ≥ 2 vertices has a vertex of degree 1.)
10.12 HW: Prove: if a graph has chromatic number c and its
complement has chromatic number d then cd ≥ n.
(7 points)
10.13 DO: Suppose both the graph G and its complement are
k-colorable. (a) Prove: n ≤ k2.
(b) Prove that this bound is tight, i.e., construct a k-colorable
graph with n = k2 vertices
10.14 DO: LN 6.1.18 (counting trees with given degrees)
10.15 DO: LN 6.1.37 (triangle-free 4-chromatic graph)
10.16 CHALLENGE PROBLEM: Problem 6 from the
third set of puzzles
(number of occurrences of max distance)
9.1. HW LN 7.1.20 (b)(c)(d) (degrees of random graph) (6+4+6 points)
9.2. BONUS PROBLEM. LN 6.1.31 (random triple in bipartite graph) (8 points)
WARNING. This problem was mistakenly posted as LN 6.1.30. That
problem is not consistent with the description "random triple in
bipartite graph." Also, that problem is too easy to be a bonus problem.
This correction was posted on 10-24 at 6pm. The deadline for
this problem is extended to Tuesday, Oct 30.
8.1. READING: MN Chapters 3.1, 3.2 (graphs), 4.1 (trees)
8.2. READING: LN Chapter 6.1 (graph terminology)
8.3. HW: LN 6.1.5 (self-complementary graphs) (3+3+6 points)
8.4. DO: LN 6.1.6 (a) (asymp equality related to number of graphs)
8.5. BONUS PROBLEM: LN 6.1.6 (b) (bounds on number of graphs) (5 points)
8.6. CHALLENGE PROBLEM: LN 6.1.6 (c) (asymp # graphs)
8.7. HW: LN 6.1.8. (3+3 points) (count induced and spanning subgraphs)
8.8. DO: LN 6.1.10 (max # edges of a bipartite graphs)
8.9. REWARD PROBLEM: LN 6.1.11 (Mantel - Turan)
(in LN, Mantel's name is misspelled)
8.10. DO: LN 6.1.15 (connected graph has at least n-1 edges)
8.11. HW: LN 6.1.16 (list 7-vertex trees) (8 pts; lose 2 pts per error)
8.12. DO: LN 6.1.21 (count 4-cycles in complete bipartite graphs)
8.13. DO: LN 6.1.23 (diameter of certain graphs)
8.14. DO: LN 6.1.27 (count shortest paths in grid)
8.15. DO: LN 6.1.29 (bipartite iff no odd cycle)
8.16. HW: LN 6.1.33 (degree + 1 colors suffice) (6 points)
8.17. DO: LN Figure 6.9 (p.52) (another drawing of the Petersen graph)
8.18. REWARD PROBLEM: LN 6.1.46 (chessboard vs dominoes) (an AH-HA problem)
8.19. REWARD PROBLEM: LN 6.1.47 (mouse vs cheese) (an AH-HA problem)
8.20. HW: LN 6.1.49 (6 points) regular graph of girth 5
8.21. DO: LN 6.1.50 (a) regular graph of diameter 2
7.1. READING: LN 7.1, 7.2 (Finite probability spaces,
random variables, expectation)
7.2. READING: MN 9.2, 9.3 (same subjects) pp. 269-284
7.3. HW: MN 9.2/Ex.5 (p. 278)
(pairwise but not fully independent events)
Make your sample space as small as possible. (6 points)
7.4. HW: MN 9.2/Ex.7 (p. 278) (prime size uniform space) (5 points)
7.5. HW: MN 9.3/Ex.1 (p. 284) (3 counterexamples)
For each counterexample, make your
sample space as small as possible and
calculate the expected values occurring in the statements.
(3+3+3 points)
7.6. HW: LN 7.2.13 (2000 members) Give a clear definition of the
random variables you use; the clarity of the definition accounts
for half the grade. (8 points)
7.7. DO: LN 7.1.25 (sample space for n independent events)
7.8. CHALLENGE PROBLEM: LN 7.1.26 (a) (b) (pairwise independent events
on small sample space)
7.9. CHALLENGE PROBLEM: LN 7.1.27 (lower bound for
pairwise independent events)
6.1. READ: MN Chapters 10.1--10.3 (pp 294--317) (generating functions)
6.2. HW: Express the function (1 - x)-1/2 as a power series
via Newton's Binomial Theorem; and express the coefficients of this
power series through "ordinary" binomial coefficients (where the top
number is a positive integer). You should get a simple closed form
expression. Show your work (it is not enough to give the final
expression). (6 points)
6.3. HW: LN 5.2.3 (Fibonacci-type sequence) (4+4 points)
6.4. DO: LN 5.2.4 (generating functions of known sequences)
6.5. READ: LN Chapter 2 (Asymptotic Notation). Compare with the
corresponding sections in MN. Wherever there seems to be a conflict
between the definitions, LN governs. Try to reconcile any such
conflict; let me know by email if you find this difficult or
impossible.
6.6. REWARD PROBLEM: LN 2.1.4. (limit of towers) (fun problem!
not required; do not hand in, but send email to the instructor
with your answer (not the proof) to the last question, "what
is the largest value ..." -- state the value only)
6.7. DO: LN 2.2.3 (asymptotic equality is an equivalence relation)
6.8. DO: LN 2.2.4 (multiplication and division of asymptotic equalities)
6.9. DO: LN 2.2.5 (addition of asymptotic equalities)
6.10. DO: LN 2.2.6/1. (asymptotics of quotient of polynomials)
6.11. HW: LN 2.2.6/2,3 (4+4+4 points) (part 2 has 2 parts)
(asymptotics involving sin, ln, sqrt). Hint for part 2:
use the definition of the derivative of these functions.
Your solution should be very simple.
6.12. HW: LN 2.2.7. (6 points) (asymptotics of powers)
6.13. DO: LN 2.2.9. (asymptotics of middle binomial coefficient)
6.14. DO: LN 2.2.10. (asymptotics of ln(n!))
6.15. CHALLENGE PROBLEM. LN 2.2.12. (asymptotics of n-th prime)
(READ the
updated
instructions for handing in
challenge problem solutions)
6.16. DO: LN 2.2.13. (generating a random 100-digit prime)
6.17. DO: LN 2.3.2 -- 2.3.7 (problems concerning the little-oh notation)
6.18. DO: LN 2.4.2 (limit vs asymptotic notation)
6.19. HW: LN 2.4.3 (5 points) (same order of magnitude but no limit)
6.20. DO: LN 2.4.4 - 2.4.6 (big-Oh, Θ, Ω notation)
6.21. HW: LN 2.4.7 (8+8 points) (ln of asymptotic relation)
6.22. DO: LN 2.1.3. (a limit related to the def of "e")
6.23. CHALLENGE PROBLEM: LN 2.7.10 (another limit related to the def of "e")
6.24. HW: Count the solutions to the equation
x1+...+xk=n
where all the xi are integers ≥ 2.
Your answer should be a binomial coefficient.
Prove your answer! (You may use a result proved in class,
no need to repeat that proof, just state clearly the
result you are using.) (6 points)
6.25. REWARD PROBLEM: LN 2.7.11 (O0 as limit "almost always")
(not required; do not hand in)
6.26. REWARD PROBLEMS: Three sheets of fun problems for your amusement.
Do not hand them in, except for those stated as challenge problems
below or later: First set of puzzles,
Second set of puzzles,
Third set of puzzles.
6.27. CHALLENGE PROBLEM. (Cleaning the corner) Problem 3 in the
Second set of puzzles.
This is a particularly sweet one.
6.28. REWARD PROBLEM. (Spreading infection) Problem 4 in the
Second set of puzzles.
One of the most beautiful AH-HA problems I have ever seen.
There is a one-word hint which tells it all. Find that word,
email it to the instructor. Remember, reward problems have no
deadline, so you can return to this problem five years from
now and then send me the one-word answer (well, G-d willing...
there is an ultimate "deadline" lurking somewhere in the dark,
after all, so don't procrastinate :)
6.29. REWARD PROBLEM. (Artistic image) Picture Pascal's Triangle mod 2.
(0=blank, 1=dot)
Discover beautiful self-similar pattern. Find the name of the picture
in the (web) literature. Send email to instructor with just that name.
Homework set #17 (posted Tue, Nov 20, 11:40 am; due Tue, Nov 27, before class)
Homework #15 has been graded; please
come and pick it up from the instructor today (Tuesday, Nov 20).
Homework set #16 (posted Sun, Nov 18, 4am;
due Tue, Nov 20, before class)
Homework set #15 (posted in advance Sun, Nov 11, 6am,
due Thu Nov 15 before class)
Homework set #14 (posted Sat, Nov 10, 9pm, due Tue Nov 13 before class)
Here we assume that the dimensions of these matrices are right for
the operations required, i.e., if A is q × r
and B is s × t then
in part (a), r = s; and in part (b),
q = s and r = t. (6+6 points)
(Use the definitions and facts stated in class.) Hint: The
column space of a matrix is the subspace spanned by the
columns of the matrix. We know from class that the rank of a matrix
is the dimension of its column space. For (a), prove that
all columns of AB belong to the column space of A. For (b), use
this version of Miracle #1: if S and T are two sets of vectors and
S ⊆ span(T) then rank(S) ≤ rank(T).
Homework set #13 (posted Tue, Nov 6, 8:50pm, due Thu Nov 8 before class)
Homework set #12 (posted Fri, Nov 2, 1:30am, due Tue Nov 6 before class)
(a) Determine E(X) and E(Y). (b) Determine Var(X).
(c) Determine Var(Y). (d) State the quantity Var(X) - Var(Y).
Which of Var(X) and Var(Y) is greater?
Your answers should be simple closed-form expressions. (6+6+6+3 points)
Hint. Represent X and Y as sums of (how many?) indicator
variables. Half of the credit for part (a) is due for
the clarity of this definition. Calculate the pairwise covariances of
your indicator variables and use these results to compute the required
variances.
To check your answer to the question in (c), give an argument that could
have predicted which of the two variances is greater, with virtually no
calculation. (You are not required to write down this argument but if you do
and your argument is correct, you will receive partial credit for part (d)
even if your answers to (b) and/or (c) are in error.)
Homework set #11 (preview posted Mon, Oct 29, 2am; finalized
Tue, Oct 30, 12:30pm)
Let now Ri denote the truncation of the right hand side
at item i, i.e.,
R0 = S0 ;
R1 = S0 - S1 ;
R2 = S0 - S1 + S2 ; etc.
Prove: if i is even then P(B) ≤ Ri; and if
i is odd then P(B) ≥ Ri. (10 points)
Homework set #10 (posted Fri, Oct 26, 8pm;
due Tue, Oct 30, before class)
Homework set #9 (posted in advance on Tue, Oct 23, 1am;
due Thu, Oct 25, before class)
Homework set #8 (posted Thu, Oct 18, 9:45pm;
due Tue, Oct 23, before class)
Homework set #7 (posted Tue, Oct 16, 12:10pm;
due Thu, Oct 18, before class)
Homework set #6 (posted in advance on Wed, Oct 10, 12:40am;
due Tue, Oct 16, before class)
Homework set #5 (posted Tue, Oct 9, 11:30 am; due Thu, Oct 11, before class)
5.1. READ: MN Chapters 2.1--2.3 (pp. 47---65) esp. Prop. 2.3.4 (p. 60) (Vandermonde's identity)
5.2. READ: MN Chapters 2.5--2.6 (pp. 73---86) esp. Thm. 2.6.1 (pp 81-82) (estimating the binomial coefficients)
5.3. DO: MN, p.62. Exx. 3, 4, 5(b) (closed form expressions for binomial sums)
5.4. HW: MN, p.62. Ex. 5(a) (closed form expression of sum involving binomial coefficients) Prove your answer. (5 points)
5.5. HW: MN, p.62, Ex. 7 (count monotone functions) State your answer as a closed-form expression (no summations or dot-dot-dots). Prove your answer. (7 points)
5.6. HW: MN, p.79 Ex 5 (a)(b)(c) (4+4+4 points) (asymptotic relations involving n! - Hint: use Stirling's formula)
5.7. REWARD PROBLEM (not required, challenging problem, solve for your amusement and edification - the solution will be its own reward. Do not hand it in because the solution is widely accessible) MN p. 86 Ex.2 (Chebyshev's weak version of the Prime Number Theorem: an amazingly powerful result proved in just a few lines using binomial coefficients)
5.8. REWARD PROBLEM MN p. 80 Ex. 7 (inequality between the arithmetic and geometric mean)
5.9. CHALLENGE PROBLEM. Let S(n,4) be the number of those subsets of an n-set which have size divisible by 4. (a) Find a closed-form expression for S(n,4). (b) For what values of n is S(n,4) = 2n-2?
5.10. CHALLENGE PROBLEM. Define S(n,3) analogously. Prove: | S(n,3) - 2n/3 | < 1.
4.1. DO: Review the Chinese Remainder Theorem on Wikipedia or using your class notes.
4.2. DO: LN 4.1.18 (CRT) Show your work! It is insufficient just to state the solution. (Added on 10/8: point value previously stated by mistake.)
4.3. HW: LN 4.1.19 (CRT) Show your work! (8 points)
4.4. HW: LN 4.1.26 (a) (b) (FlT with composite modulus) (8+4 points)
4.5. DO: (a) Define the least common multiple in analogy with our definition of the greatest common divisor.
(b) Prove that l.c.m. exists. Hint: do not try to mimic the proof of the existence of a g.c.d.; use instead the fact that g.c.d. exist: represent the l.c.m. as the g.c.d. of a certain set of numbers (which numbers?).
4.6. DO: LN 4.2.10 (Product of g.c.d. and l.c.m.)
4.7. HW: Prove: there are infinitely many primes of the form 4k-1 (such as 3, 7, 11, 19, 23, etc.). Hint: modify Euclid's trick. (8 points)
4.8. CHALLENGE PROBLEM. Prove: there are infinitely many primes of the form 4k+1 (such as 5, 13, 17, 29, etc.). Hint: modify Euclid's trick. Prove and use the following lemma: if x is even then all primes dividing x2+1 are of the form 4k+1.
4.9. BONUS PROBLEM (you are not required to solve this; the same deadline applies). LN 4.2.16 (Wilson's Theorem) (5 points)
4.10. CHALLENGE PROBLEM. LN 4.3.4. (Determinant of gcd's.)
4.11. CHALLENGE PROBLEM. LN 4.2.13 (Integer-preserving polynomials)
4.12. CHALLENGE PROBLEM. LN 4.2.2, part 2. (Divisor game)
4.13. DO: LN 4.1.27 (tiny questions on gdc, lcm, congruence mod 24)
4.14. DO: LN 4.1.30 (FlT mod 12,328)
4.15. DO: LN 4.1.21 (gcd vs congruence mod 5)
4.16. HW: LN 4.1.23 (application of FlT to very large exponent) Show your work! You may use a calculator for division but for nothing else. (6 points)
4.17. DO: Review the Binomial Theorem and its proof on Wikipedia.
4.18. HW: LN 5.1.1. (Inductive proof of an identity involving binomial coefficients) (6 points)
4.19. DO: LN 5.1.2. (p divides "p choose k")
4.20. HW: LN 5.1.4 (a) (b) (Prove that the number of odd subsets equals the number of even subsets. A subset is odd if it has an odd number of elements. A "bijective proof" proves that two sets have equal cardinality by finding a bijection between them. Both problems are "AH-HA," each proof is just a couple of lines. Clarity is paramount.) (12+6 points)
3.1. DO: Prove the multiplicativity of Euler's φ function (see LN, Definition 4.3.25)
3.2. DO: LN 4.3.3 (summation of the φ function)
3.3. DO: Prove: inf φ(n)/n = 0 (where the infimum is taken over all positive integers). Hint: use the divergence of the sum ∑ 1/p and the inequality 1+x ≤ ex which holds for all real numbers x.
3.4. DO: LN 4.4.22 (sum of two squares never -1 mod 4)
3.5. DO: LN 4.2.15 (existence of multiplicative inverse)
3.6. HW: LN 4.1.17 (b) (c) (4+6 points) (muliplicative inverses) (for part (b), show your work, explain how you got your answer)
3.7. HW: LN 4.1.33 (solving congruence of degree 3p) (10 points)
3.8. HW: LN 4.1.31 (no square root of -1 mod 103) This is an "AH-HA" problem; the solution should be just one line. (10 points)
3.9. DO: LN 4.1.32 (a) (n+1 integers)
3.10. CHALLENGE PROBLEM: 4.1.32 (b) (n+1 integers)
2.1. HW: LN 1.2.5 (d)(f)(h) (8+8+8 points) (logic and numbers)
2.2. DO: Prove: gcd(a-b,b) = gcd(a,b).
2.3. DO: LN 4.2.9 (gcd vs congruence)
2.4. DO: LN 4.1.27 (logic and gcd)
2.5. HW: Prove: if d is a common divisor of a and b and at the same time d is a linear combination of a and b then d is a greatest common divisor of a and b. (8 points)
2.6. DO: Study Euclid's Algorithm (LN Sec 4.1)
2.6. DO: LN 4.14 (a) (b) (compute gcd's using Euclid's Algorithm). In addition, find a representation of the gcd's obtained as linear combinations.
2.8. HW: LN 4.1.24 (a) (b) (6+6 points) ("square root mod m")
2.9. DO: LN 4.1.22 (a) (consecutive Fibonacci numbers are relatively prime)
2.10. BONUS PROBLEM (you may hand it in but not required; normal deadline applies): LN 4.2.6 (8 bonus points) (gcd of powers of a minus 1)
2.11. CHALLENGE PROBLEM (no point value but earns instructor's attention; no deadline): LN 4.2.8 (gcd of Fibonacci numbers)
1.1. DO: review the concept of limits, especially at infinity. Define them using properly quantified formulas.
1.2. DO: Prove: every equivalence relation arises from a partition. (Two elements are equivalent if and only if they belong to the same class in the partition.)
1.3. DO: (a) When are two integers congruent modulo 1? (b) When are two integers congruent modulo 0?
1.4. HW: LN 1.2.5 (a)(b)(c) (5+5+5 points) (Numbers and quantifiers) Give clear TRUE/FALSE answers to each problem and prove your answers. The proofs should be very short.
1.5. DO: LN 4.1.15 (a)(b) (Number of divisors)
1.6. HW: LN 4.1.15 (c) (10 points) (Upper bound on the number of divisors) due next Tuesday (Oct 2) before class.
1.7. HW: LN 4.2.12 (10 points) (Periodicity of the Fibonacci numbers modulo m) due next Tuesday (Oct 2) before class.
WARNING: Start working now on the last two problems; these are creative problems and may require more than one session for you to solve. In each case, the solution should be short and elegant. -- More problems due on Oct 2 will be added this Thursday.