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

## 187 – Mathematics – Stack Exchange

October 22, 2011

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:

## 187 – Presentation

October 21, 2011

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.

## 187 – Arguing by contradiction

October 10, 2011

[Edit: I have extended the deadline until the day of the final exam.]

Here are some extra credit problems. They are due at the latest by November 1, the day of the second midterm (just turn them in when you come to take the test), but you can of course turn them earlier. You can turn in as many as you want, this is completely voluntary.

All these problems can be solved arguing by contradiction. They tend to require at least one additional idea. The problems come for Loren C. Larson’s book “Problem-solving through problems.

1. In a party with 2000 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. Prove that the other 1997 people know everyone at the party. (Assume that whenever a person $A$ knows a person $B$, then also $B$ knows $A$.)
2.  Prove that there are no positive integers $a$, $b$, $c$, and $n$ such that $a^2+b^2+c^2=2^n abc$.
3. Every pair of communities in a country are linked directly by exactly one mode of transportation: bus, train, or airplane. All three modes of transportation are used in the country; no community is served by all three modes, and no three communities are linked pairwise by the same mode. For example, four communities can be linked according to these stipulations in the following way: bus, $AB$, $BC$, $CD$, $DA$; train, $AC$; airplane, $BD$.
1. Give an argument to show that no community can have a single mode of transportation leading to each of three different communities.
2. Give a proof to show that five communities cannot be linked in the required manner.
4. Let $S$ be a set of rational numbers with the property that whenever $a$ and $b$ are (not necessarily distinct) elements of $S$, then also $a+b\in S$ and $ab\in S$. Moreover, suppose that for any rational number $r$, exactly one of the following is true: $r\in S$, $-r\in S$, $r=0$.
1. Prove that 0 does not belong to $S$.
2. Prove that all positive integers belong to $S$.
3. Prove that $S$ is the set of all positive rational numbers.

## 187 – Presentation

October 8, 2011

Jeremy Elison will give a short presentation on Wednesday, October 12, on Georg Cantor and infinity.

## 187 – Selected solutions from Chapter 2

October 6, 2011

Professor Warren Esty, has made available a list of solutions to some of the problems from Chapter 2. 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.

Solutions (Chapter 2)

## 187 – Selected solutions to problems from Chapter 1

September 19, 2011

Professor Warren Esty, one of the authors of our main textbook, has made available a list of solutions to some of the problems from Chapter 1. They are most of the odd numbered problems. Please let him (or me) know if you find errors or typos, or if you have suggestions for alternative solutions or different approaches.

Solutions (Chapter 1)