Zvezdelina Entcheva Stankova

Visiting Professor


713 Evans Hall

Department of Mathematics

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:

Course Syllabus for MATH 55, Fall 2014.

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.

For enrollment questions:

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

Email is ONLY for emergencies (e. g., medical and family emergencies).

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.

Videos on Game and Geometry Puzzles from the Numberphile Channel, containing many of the proof and problem-solving ideas discussed in class:

1) Three Squares: http://youtu.be/m5evLoL0xwg

2) Free the Clones: https://www.youtube.com/watch?v=lFQGSGsXbXE

Homework Assignments and Notes:

HW8 Solutions.

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.

Homework 9A, due Wed, Oct 29:

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:

1. n distinguishable balls into k distinguishable boxes so that there are n_i balls in the i-th box, for i=1,2,...,k. This problem has the same answer as the number of permutations of n objects with n_i repetitions of type i, for i=1,2,...,k. The answer to both problems is the multinomial coefficient:

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).

2. r indistinguishable balls into n distinguishable boxes. This problems has the same answer as the number of r-combinations with repetitions from n distinguishable objects; and as the number of non-negative integer solutions to x_1+x_2+...+x_n=r where the order of the variables matter; e.g., 2+1+1=4 and 1+2+1=4 are two different solutions and must each be counted; and as the number of strings of (n-1) I's (n-1 "interior walls") and r 1's (r "biscuits"). The answer to all problems is the binomial coefficient:

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

3. n distinguishable objects into k indistinguishable boxes. This problem was interpreted as "4 distinguishable kids in 3 identical playstations". For small n and k, you are expected to solve this problem by splitting into cases and counting by brute force. The number in each case was a "Stirling number of the second kind", S(n,j), which counts the number of ways to distribute n distinguishable kids into j playstations so that no playstation is empty. You do not have to memorize (for now) the complicated formula for S(n,j) (which we haven't proven yet). You are expected to recognize this type of problem and solve it by brute force. If a question asks specifically for S(n,j), you are expected to know what S(n,j) is and to count it by brute force.

4. n indistinguishable objects into k indistinguishable boxes. The problem was as "a quadruple of identical kids in 3 identical playstations". It was also interpreted as the number of non-negative integer solutions to x_1+x_2+x_3=4 where the order of variables do not matter, e.g., 2+1+1=4 is the same solution as 1+2+1=4). We did not give a direct way or a formula to solve this problem. You are expected to recognize this type of problem and, for small n and k, to be able to solve it brute force by splitting into cases.

Let me know if you see any typos above!

Homework 8B, due Wed, Oct 22:

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:

1. Use the factorial formulas for binomial coefficients and (brute-force) an algebraic calculation of the identity;

2. Use algebra by plugging for x and y into the Binomial Theorem or Vandermonde's Theorem, or some versions of them;

3. Use induction (perhaps on the row number in Pascal's Triangle, or on the "length of the hockeystick", etc.);

4. Find a combinatorial way by counting something in two different ways and equating the results;

5. Use a picture/combinatorial geometry (e.g., prove the Hockeystick Identity using as an illustration what happens directly on the Pascal's triangle);

6. Use calculus, e.g. ,take derivatives of the two sides of the Binomial Theorem, where, say, y=1. This method is optional, as students are not required to have taken Calculus for this class, but if a student presents a Calculus solution to a binomial identity, it will be accepted as correct (unless there are restrictions in the problem asking for a specific other type of solution).

7. Some combination of the above. (How many combinations of the above methods are there? :))

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.

Homework 8A, due Wed, Oct 22:

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.

Homework 7B, due Wed, Oct 15:

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*.

Homework 7A, due Wed, Oct 15:

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.

Homework 6, due Wed, Oct 8:

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.

Homework 5B, due Mon, Sept 30:

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.

Homework 5A, due Mon, Sept 29:

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.

Homework 4B, due Wed, Sept 24:

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.

Homework 4A, due Wed, Sept 24:

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.

Homework 3B, due Wed, Sept 17:

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.

Homework 3A, due Wed, Sept 17:

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.)

Homework 2B, due Wed, Sept 10:

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.

Homework 2A, due Wed, Sept 10:

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.)!

Homework 1, due Wed, Sept 3:

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.