This link should take you to the YouTube channel of Algo-rythmics, or see their website.

Different sorting algorithms (bubble sort, insertion sort, quicksort, selection sort, shell sort) illustrated through folk dance.

Andrés E. Caicedo

For ease, I re-list here all the presentations we had throughout the term. I also include some of them. If you gave a presentation and would like your notes to be included, please email them to me and I’ll add them here.

**Jeremy Elison**, Wednesday, October 12:*Georg Cantor and infinity.***Kevin Byrne**, Wednesday, October 26:*Alan Turing and Turing machines.***Keith Ward**, Monday, November 7:*Grigori Perelman and the Poincaré conjecture.***David Miller**, Wednesday, November 16:*Augustin Cauchy and Cauchy’s dispersion equation.***Taylor Mitchell**, Friday, November 18:*Lajos Pósa and Hamiltonian circuits*.**Sheryl Tremble**, Monday, November 28:*Pythagoras and the Pythagorean theorem.***Blake Dietz,**Wednesday, November 30:*and the Happy End problem.*

Here are Jeremy’s notes on his presentation. Here is the Wikipedia page on Cantor, and a link to Cantor’s Attic, a wiki-style page discussing the different (set theoretic) notions of infinity.

Here are a link to the official page for the Alan Turing year, and the Wikipedia page on Turing. If you have heard of Conway’s Game of Life, you may enjoy the following video showing how to simulate a Turing machine within the Game of Life; the *Droste effect* it refers to is best explained in by H. Lenstra in a talk given at Princeton on April 3, 2007, and available here.

Here is a link to the Wikipedia page on Perelman, and the Clay Institute’s description of the Poincaré conjecture. In 2006, The New Yorker published an interesting article on the unfortunate “controversy” on the priority of Perelman’s proof.

Here are David’s slides on his presentation, and the Wikipedia page on Cauchy.

Here is a link to Ross Honsberger’s article on Pósa (including the result on Hamiltonian circuits that Taylor showed during her presentation).

Here are Sheryl’s slides on Pythagoras and his theorem. In case the gif file does not play, here is a separate copy:

The Pythagorean theorem has many proofs, even one discovered by President Garfield!

Finally, here is the Wikipedia page on . Oakland University has a nice page on him, including information on the number; see also the page maintained by Peter Komjáth, and an online depository of most of papers.

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

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

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

The proof I was expecting was by contrapositive: If is not a multiple of , then it has a non-zero remainder when divided by , so or for some integer . This means that or . After some rearranging, we see that in both cases we have for some integer , but then is not a multiple of after all.

Using Euclid’s lemma, we can give another proof that is particularly short: Since is a prime, then whenever divides a product, it divides one of the factors. We are told that divides , so it divides or it divides . 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.

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

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 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 numbers from , 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.

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:

- Welcome to the Cambridge Mathematical Tripos.
- Basic logic — connectives — AND and OR.
- Basic logic — connectives — NOT.
- Basic logic — connectives — IMPLIES.
- Basic logic — quantifiers.
- Basic logic — relationships between statements — negation.
- Basic logic — relationships between statements — converses and contrapositives.
- Basic logic — tips for handling variables.
- Basic logic — summary.
- Definitions.
- Alternative definitions.

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:

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.

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

I have mentioned a few times the website http://math.stackexchange.com/ and suggested that you take a look at it and use it as a resource. I believe it is a really useful site when used appropriately. Some of you have asked for additional references, and I think this site may help supply some of them.

Here is a short list of questions posted on the site that may give you an idea of its value:

**Kevin Byrne** will give a short presentation on **Wednesday, October 26**, on *Alan Turing and Turing machines. *Here is a link to the official page of the Alan Turing Year.