187 – Arguing by contradiction

[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 knows a person , then also knows .)
2.  Prove that there are no positive integers , , , and such that .
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, , , , ; train, ; airplane, .
   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 be a set of rational numbers with the property that whenever and are (not necessarily distinct) elements of , then also and . Moreover, suppose that for any rational number , exactly one of the following is true: , , .
   1. Prove that 0 does not belong to .
   2. Prove that all positive integers belong to .
   3. Prove that is the set of all positive rational numbers.

Advertisement