713 Evans Hall

University of California at Berkeley

Berkeley, CA 94720-3840

Tel: 510-642-3768

Fax: 510-642-8204

Email: stankova@math.berkeley.edu

Office Hours TTh 9:30-10:50am in Evans 713.

Webpage: http://math.berkeley.edu/~stankova

Click below for the syllabus:

GSIs finalized office hours were revised in the syllabus on 9/6/2014. Check them out and keep them with at all times. You are welcome to visit any GSI's office hours, along with the professor's office hours.

Do NOT contact the
instructor or the GSIs. We have no control over enrollment.
Contact instead **Thomas Brown, 965 Evans.**

Email is NOT for resolving enrollment questions, or asking for letters, or for discussion of midterm results, or for any discussion about how the student is doing in the class or how to improve. I have received lately a number of such emails, to all of which the response is to come see me in person in office hours (bringing all necessary documentation with you). You are also welcome to visit any GSI's office hours to discuss math questions or how to improve in the course; the GSIs are very qualified to discuss any math question. This is clearly written in the syllabus and was discussed in detail during the first lecture.

HW Solutions are posted about a day before the quiz and will be taken off the web in a week. Do NOT ask for solutions to be posted earlier: you must attempt to do your homework without help from posted solutions. If you are late copying them, or you lose them, or some other thing happens: do NOT ask us for the files of the previous solution since we do NOT distribute electronic files of the HW solutions. Instead, ask your classmates for the HW solution files. Make sure you download and save the solutions as soon as they are posted, to avoid having to ask your classmates later on for them.

If not specified odd or even exercises, it is assumed only even exercises, e.g., #2-8 means 2,4,6,8.

Read 7.1. Write: #6,8,12,16,18,22,24(d),26(b),30,34,36. Extra Challenge: #38,40,41.

Read 6.2. (May skip for now Theorem 3.) Write: #2,4,6,8,12. Extra Challenge: #10*.

** Hints for 6.2.** #12 and #10 are really the same type of problem. In challenge #10, you are working mod 2 (why?) and looking for a pair of points whose x-coordinates have the same parity, and whose y-coordinates also have the same parity (to have the "same parity" means to be "both even or both odd"). In #12, you are asked the same question but mod 5. In each problem, let the "holes" be remainders mod 2 or mod 5 respectively; apply PHP to the x-coordinates first, and then for those points whose x-coordinates fall into the same "hole" apply another PHP to their y-coordinates.

Read 6.5. Write: #2,4,8,12,14,18,20,22,24,26,31,38,42,50,65. Extra Challenge: #40,44,46,66.

The material we saw in lecture today can be roughly summarized as follows. Problems on the number of ways to put:

n!/[(n_1)!(n_2)!...(n_k)!], where n_1+n_2+...+n_k=n.

The multinomial coefficients appear in the expansion of, say, (M+I+S+P)^{11}. For example, 11!/(4!4!2!1!) is the coeffiecient of (I^4)(S^4)(P^2)(M^1), because it counts in how many we can permute the letters in the string IIIISSSSPPM (or equivalently, the letters of MISSISSIPPI).

(r+n-1 choose r) = (r+n-1 choose n-1).

Read 6.4 (finish, concentrate on Identities Involving Binomial Coefficients). Write: #20,22,23 (just show the identity),24,25,28,29. Extra Challenge: #26,30.

This HW emphasizes doing problems in more than one way where possible: e.g., here are some ways which we saw today in lecture:

** Hints for 6.4.** In #20: first choose some suitable small values for k and n and locate the six points in Pascal's triangle that correspond to the six binomial coefficients in the hexagon identity; draw the hexagon with vertices these six points; now prove the hexagon identity by substituting the factorial formulas for the six binomial coefficients, cancelling, and showing that the two sides are equal. In #22: the algebraic proof simply uses the factorial formulas for the binomial coefficients; the combinatorial proof may involve choosing from n people a team of r "teachers", k of whom will be the "math teachers" and the rest will be the "other teachers"; the process of choosing the team of teachers can be done in two ways: first choosing all teachers and then the math teachers, or first the math teachers and then the other teachers. In #24 give yourself a couple of examples first, and then use the fact that the prime p must be relatively prime with the denominator of the facitorial formula for (p choose k). In #28: the algebraic proof should not be hard, as long as one uses the shortcut formula for (k choose 2) (i.e., k(k-1)/2); for the combinatorial proof, imagine that you have n men and n women and you want to choose a pair of people to lead an event; the pair can be of the same gender or of opposite gender; in how many ways can you choose the pair? Yes, redo #29 in as many ways as you can; compare with your classnotes; I can see at least three ways to do it.

In challenge #26: the LHS is Vandermonde's identity in disguise: start by replacing (n choose k) by another binomial coefficient equal to it; the RHS can be replaced by something simpler from #25. In challenge #30: the combinatorial way is outlined in the textbook hint; for a second way, algebraically manipulating "k times (n choose k)" will turn the whole identity into the form of Vandermonde's identity multiplied by n on both sides.

Read 6.3. Write: #4,6(b)(d)(f),10,12,13,16,22(c)(d),24,26,28,30,36. Extra Challenge: #29*,42.

Read 6.4 (up to section on Pascal's Identity and Triangle, inclusive). Write: #6,8,12,14,15,17*,19. Extra Challenge: #10*,16*.

** Hints for 6.3.** In #12(b)(c): using just combinations will not suffice; split into disjoint cases and add. In #13: arrange first the men in a row, then spread them by one place between adjacent men; then arrange the women in a row and complete the solution using the product rule. In #16: again split into non-disjoint cases and add; some cases will yield the same answer; why? The hint for #24 outlines the process that will yield an easier way to solve the problem. #26(c) may be easily solved by "counting the complement"; alternatively, do it by splitting into disjoint cases and adding; compare your answers. In #28 just choose where to place the false answers and count how many possibilities this yields. #30(a) should remind us of another problem on this HW assignment; in #30(b): how many committees of 5 faculty members are possible at all? what is the size of the overlap of the set from #30(a) with the analogous set of the committees with at least one man? In #36: use blocks of "glued"-together 011.

In challenge #29*(a): select the three consecutive integers k,k+1, and k+2 first, then select the fourth integer, and finally see in how many places can you insert it into (or append it to) the sequence {k,k+1,k+2}; make sure you do NOT overcount the arrangements of 4 consecutive integers {m,m+1,m+2,m+3}. Challenge #29(b) is solved in almost the same way as #29(a) except that there are fewer places to insert/append the fourth integer to the sequence {k,k+1,k+2}. In challenge #42: seat one person somewhere and don't move him; then calculate how many ways there are to seat the remaining people, and finally, see why you have counted twice each seating arrangement.

** Hints for 6.4.** In #14: start with a conjectured inequality C(n,k) < C(n,k+1) among two consecutive binomial coefficients; use then the factorial formula for each C(n,k) and C(n,k+1), cancel stuff and simplify to arrive at an equivalent inequality k<(n-1)/2; this indicates that in any row of Pascal's triangle, the binomial coefficients strictly increase until the middle of the row and then decrease; if n is even, there will be a single largest (middle) number in the row; if n is odd, there will be two "middle" binomial coefficients that are equal to each other and, therefore, are the largest in the row. (Alternatively, slightly more elegantly, but using a non-trivial version of induction, you can prove the above pattern of increase and decrease in each row by induction on the number of the row.) In #15: use the fact that all binomial coefficients in Pascal's triangle are positive and that all of them in the nth row add up to 2^n. In #17: the LHS of the inequality, (n choose k), can be written as a product of fractions: (n/1) . ((n-1)/2) . ((n-2)/3) ... ((n-k+1)/k); each of these fractions is less than (n/2) (why?), except the first fraction (n/1), which is n; the RHS can also be written as a product of k fractions, one of which is n/1 and the rest are all (n/2). In #19: in Pascal's Identity, replace all three binomial coefficients by their corresponding factorial formulas of the kind n!/(r!(n-r)!), put the two fractions in the RHS under a common denominator (make sure you choose as small a common denominator as possible), factor and cancel, to arrive at the factorial formula for the fraction in the LHS.

In challenge #10*: exactly one of the products x^{100-j} (1/x^j) will equal x^k; what is this j? In challenge #16(a): start by multiplying both sides of the desired inequality by n;the inequality can now be rephrased as follows: adding n copies of the largest (middle) binomial coefficient in the nth row is at least as large as the sum 2^n in that row; this inequality would have been trivial if we added (n+1) copies of this largest coefficient (why? there are n+1 numbers in the nth row of Pascal's triangle); however, we are adding only n copies of this largest middle term; still, the first and the last coefficients in the nth row are 1's, so the two of them add up to 2, and 2 is less than or equal to any other number in this row, including the largest (middle) coefficient; this will be helpful to argue that n copies of this middle coefficient are already more than or equal to the whole sum of the row. In challenge #16(b): replace n in 16(a) by a suitable expression.

Read 6.1. Write: #3,8,12,14,16,22(b)(f)(g)(h),24(a)(b)(g)(h),32(d)(e),34(d),40,44,46,52. Extra Challenge: #50*.

Finish 5.2, emphasizing direct usage of the WOA (or the "Extreme Principle"). Write: #36*.

Read 5.3 (may skip for now Lame's Theorem). Write: #2(c),4(d),6,8,12,20*,22,24,26,35,46. Extra Challenge: #14*,16*,58.

Read 5.1 (may skip for now Proving Results about Algorithms). Write: #4,6,10,14,18,20,22,34,40,49,60,64,75. Extra Challenge: #74.

Read 5.2. Write: #4,6,10,12,14,32. Extra Challenge: #19*, 38.

Read 4.4 (may skip Computer Arithmetic with Large Integers and Pseudoprimes). Write: #2,4,6(a)(c),8(try an example first),10,12(b),16* (do (a) with brute force if necessary),20,22,32,34,38(a),40,54,55.

Read 4.3. Write #4,10,12,13,16(b)(d),18(a)(b)*,20(a)(b),24(a)(b),26(a)(b),28,30,32(c),40(f). Extra challenge: #11*,36*-37*.

**Hints:****
**In #10: argue by contradiction and assume that there is an odd
divisor of m; this odd divisor is denoted by k in the hints; the
hint is asking you to show the given factorization and use it to
prove that 2^m + 1 will turn out to be composite in this
situation; try some small cases for m to get a feeling for what is
going on. In #11*: argue by contradiction, get rid of all
inconvenient functions to turn the statement only about integers,
and then use the prime factorization of these integers. In #12:
use the hint; if it is hard at first, try it in an example with a
small n, e.g., n=3, 4. In #13: the asterisk * may be “overrated”;
try out an example? In #18(b)*: write out ALL divisors of the
given number and add them up using the formula for the geometric
progression. In #20: memorizing all powers of 2 up to 2^{10} is
good.

Read 4.2 (up to p. 249, inclusive). Write #2,4,29,31,32.

**Hints:****
**In #31, show first that 10^n is congruent to 1 (mod 3) for any
natural number n; then use the decimal expansion of a positive
integer a and modular arithmetic mod 3 to show that a is congruent
to the sum of its digits (mod 3). Try exactly the same approach
for divisibility by 9. In #32: similarly, start by noting that 10
is congruent to -1 (mod 11), then show that 10^n is congruent to 1
(mod 11) when n is even, and to -1 when n is odd; finish by using
the decimal expansion of your number a and replacing all powers of
10^n by +1 or -1, respectively. Try all these divisibility
criteria on 3- or 4-digit numbers to see how they work out in
practice.

Read 2.4. Write #6(a)(b)(d)(e), #8,10(d), #12(d), #14(c)(f)(g), #16(c)(g), #22, #26(e)(f), #32(a)(d), #34(b)(c), #40.

Read 4.1. Write #6, #8, #10(d)(e), #12(c), #14(d), #18, #28(a)(d), #32(c), #36, #38, #40.

Read 2.3. Write #2,6(a)(b)(d),12,14(a)(b)(e),20,22(b)(c),26,30(d),40,50,54,64,74(b). Extra challenge: 76.

Read 2.5. Write #2,4,6,8,10,16,18,20(use bijections),24.

Read 2.1. Write #10,12,16,18,20,22,24,26,32(b)(d),38.

Read 2.2. Write #2,4,12,14,16(d),18(c),24,26(b),30,44.

Read 1.8. Write #4,6,10,14,18,22,30,32,34,36,42,44.

This HW will be tough for those who are not experienced with problem solving and proofs, which is natural at this level. Hence some hints are listed here. Do your best.

**Hints: **#4 (arrange
a,b,c in increasing order in your cases); #6 (x being odd and y
being even is symmetric to another case); #8 (definitely try some
small cases first before you find your example); #10 (Could they
BOTH be perfect squares? Could (n+1)^2 - n^2=1? Why is this
relevant in the problem?) #18 (place r on the real line between
two consecutive integers, exactly one of which will be the
required unique n in the problem; why?; what could go wrong if we
allowed for r to be rational?) #22 (Do it as the hint suggests.
And then apply the inequality from Example 14 to x^2 and 1/x^2
(instead of x and y) for a direct proof.) #30 (If they were such
integers, how large can possibly be |y|?) #32 (The hint is giving
you specific formulas for the integers x, y, and x. Substitute
these formulas into the Pythagorean equation to show that they
satisfy the equation. Do these formulas give infinitely many
triplets of solutions? Why?) #34 (Adapt the proof that square root
of 2 is irrational.) #36 (What kind of a number lies exactly in
the middle between a rational and an irrational number? Use the
average to get a formula for this middle number and show why it
must be irrational by contradiction.) #42 (Direct tiling should do
it. Try it.) #44 (What happens if you color the 5 x 5 board as a
regular chessboard? Try finding an invariant.)

Read 1.6. Write #2,4,8,12,16,18,24,28. Challenge: #35*.

Read 1.7. Write #6,8*,10,12,18,20,24,26,30,34.

Read 1.3. Write #6,8,10(b)(c),14,24,30,32,60,62(a).

Read 1.4. Write #6,10,16,20,32,50,60.

Read 1.5. Write #6,14,20,24,30,40,46.

**Note 1: **The first
quiz is on Wed, Sept. 3 and will be on the material from HW1. For
the quizzes, you are allowed to have a cheat sheet containing
material related to course. The cheat sheet can be only 1 page
(one-sided!) of a regular 8”x11” sheet. It has to be
hand-written by you (no zeroxing, copying, pasting, etc.)!

Read 1.1. Write #2,4,8,12,14,18,28,30,34,38. Extra Challenge: #40, 49.

Read 1.2. Write #2,12,16,24,28,40,42. Extra Challenge: #36, 38.

**Note 1: **The
implication "p --> q" can be read in a number of
ways. One of the most confusing ways to read it is "p only if
q", which means "if p is true then q must be true",
i.e., "if p then q". I would suggest avoiding, whenever
possible, the expression "only if" as it is doubly
dangerous. Indeed, in everyday life it is used to mean "if
and only if", while in math it is used only in one direction
and it is often counterintuitive. For example, Problem #3 from 1.1
can be translated mathematically as: "If p then [q1 AND (not
q2) AND (not q3)].", where p: "You graduate.", q1:
"You fulfilled all requirements for your major.", q2:
"You owe money to the university.", q3: "You owe a
library book."

**Note 2: **The first
quiz is on Wed, Sept. 3.