414/514 – Convexity

November 16, 2011

This is the last homework set of the term. It is optional. If you decide to turn it in, it is due Wednesday, December 14 at noon.

Read the rest of this entry »

187 – Presentations

November 14, 2011

David Miller will give a short presentation on Wednesday, November 16, on Augustin Cauchy and Cauchy’s dispersion equation.

Taylor Mitchell will give a presentation on Friday, November 18, on Lajos Pósa.

Sheryl Tremble will give a presentation on Monday, November 28, on Pythagoras and the Pythagorean theorem.

Blake Dietz will give a presentation on Wednesday, November 30, on \mbox{\em Paul Erd\H os}.


414/514 – Series

November 8, 2011

This is homework 5, due Friday November 18 at the beginning of lecture.

First of all, some of you did not realize that the first question in the previous homework set was indeed a question, and skipped it. If that was the case, please solve it now and turn it in. The sooner you do so, the sooner I’ll be able to grade it and return it with the rest of your homework 4. The question was as follows:

  • Suppose that f is monotonically increasing. Then f(x-) and f(x+) exist for all x\in{\mathbb R}. Moreover,

    f(x-)\le f(x)\le f(x+),


    f(x+)\le f(y-)

    for all x<y.

To be explicit: You need to prove all the assertions in the paragraph above.

The new set follows.

Read the rest of this entry »

187 – An exploration

November 7, 2011

Problem 6 in the midterm asked to prove that if n is an integer and n^2 is a multiple of 3, then n is already a multiple of 3.

As we now know from lecture, the key seems to be that 3 is a prime number. For example, it is not necessarily the case that if n^2 is a multiple of 4, then n is a multiple of 4. For a counterexample, we can take n=2.

The proof I was expecting was by contrapositive: If n is not a multiple of 3, then it has a non-zero remainder when divided by 3, so n=3k+1 or n=3k+2 for some integer k. This means that n^2=9k^2+6k+1 or n^2=9k^2+12k+4. After some rearranging, we see that in both cases we have n^2=3t+1 for some integer t, but then n^2 is not a multiple of 3 after all.

Using Euclid’s lemma, we can give another proof that is particularly short: Since 3 is a prime, then whenever 3 divides a product, it divides one of the factors. We are told that 3 divides n^2=n\cdot n, so it divides n or it divides n. On the other hand, this brevity is only apparent, as the proof uses Euclid’s lemma, which makes use of the Euclidean algorithm and the possibility of writing the GCD of two numbers as a linear combination of them. When written in full detail, this argument ends up being longer than the one we gave first.

A different approach was suggested during lecture, and I think it leads to a nice argument, so I am presenting it here.

Read the rest of this entry »

187 – Presentation

November 7, 2011

Keith Ward will give a short presentation on Monday, November 7, on Grigori Perelman and the Poincaré conjecture.

187 – Some extra credit problems

November 7, 2011

I have extended the deadline for extra credit problems: They are now due at the beginning of the final exam. In addition to the previous problems, I will be adding a few more through the next few days in this post.

  • The problem at the end of the second midterm. Specifically, find (with proof) the correct formula for the resulting number of regions, when n points are positioned on the circumference of a circle, and all possible lines between them are drawn. This problem is due to Leo Moser and is discussed in a few places, for example, in Mathematical Circus, by Martin Gardner.
  • Given n+1 numbers from \{1,2,\dots,2n\}, show that there must be two such that one divides the other. This problem can be solved using mathematical induction, but feel free to solve it by other methods.
  • Solve this self-referential test.

187 – Timothy Gowers

November 2, 2011

Professor Gowers is a British mathematician, Fields medalist 1998. Besides his many interesting and significant results, Gowers has contributed to the mathematical community in several other valuable ways, for example, by prompting the creation and development of polymath projects, “massively collaborative mathematics“.

His blog is very interesting. Recently, he has been posting on topics that are quite close to the content of our course, starting with his Welcome to the Cambridge Mathematical Tripos. I recommend that you take a look at his recent postings (and their comments), as one of Gowers’s strengths is his clarity of exposition helping one understand how even complicated results can be naturally motivated and proved.

Here is a link to a lecture he gave at the Millennium Meeting on May 2000, On the importance of mathematics, also highly recommended. The lecture is split into a series of short videos and lasts about one hour. I hope you can find the time to watch it on its entirety. Here is a pdf transcript of the talk.

Here is the list of his recent postings on topics relevant to our course:

The subject of his next few postings will be one of our coming topics, and they all certainly come up in more advanced courses, so it may be useful to read these as well:

187 – Selected solutions from Chapter 3

November 2, 2011

Professor Warren Esty, has made available a list of partial solutions to some of the problems from Chapter 3. As before, please let him (or me) know if you find errors or typos, or if you have suggestions for alternative solutions or different approaches. Unfortunately, it is my understanding that no solutions will be provided for later chapters.

Solutions (Chapter 3)

Also, Joanna Thompson, our reader, has supplied solutions for last week’s homework.