596 – Continued fractions

October 10, 2011

This term, Summer Hansen is taking a reading course with me on Pell’s equation. Our basic reference is:

  • Jacobson and Williams, Solving the Pell equation. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2009. xx+495 pp. ISBN: 978-0-387-84922-5.

We are allowing a rather organic approach to the material, taking as many detours as it seems appropriate. The topic of continued fractions naturally came up. What follows is just a short compendium of results I found interesting while reading on the subject.

Read the rest of this entry »

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.