Chapter 8
Notes for 27 August

Notes also available as PDF.

8.1 Review

8.2 Ruling out possibilities

8.2.1 Logic puzzles

Each of Bill, John, Fred, and Jim are married to one of Judy, Gretchen, Margie, and Loretta.

  1. Judy’s husband’s name does not begin with J.
  2. Margie’s husband’s name has the same letter twice.
  3. The name of Loretta’s husband has three letters.

Judy GretchenMargieLoretta
Bill—(2) —(2) Yes(2) —(2)
JohnNo(1) Yes —(2) —(3)
Fred Yes —(2) —(3)
JimNo(1) —(3) —(2) Yes(3)

For an example that does not work, see problem 8 in set 1.4 (page 49). Whoever wrote that has no idea what is in a decent banana split or double-dip cone.

8.3 The pigeonhole principle

If there are more pigeons than pigeonholes, then at least one hole holds more than one pigeon.

Thought to have been presented first by Dirichlet in 1834 as the “shelf principle”.

The pigeonhole principle and its variations are an indispensable tool of mathematics!

There is a wonderful description and exploration of different phrasings from Edgar Dijkstra:

Even more examples through the references at

8.4 Mathematical reasoning

Two key forms of reasoning in mathematics:

Making an ”educated” guess from prior observations.
If premises are satisfied, conclusion follows.

Premises also are known as hypotheses, suppositions, or other similar terms.


problems to find
use inductive reasoning, and
problems to prove
apply deductive reasoning.

But finding a proof is in many ways inductive.

Problem solving so far has been inductive. Take example problems and their solutions. Emulate the solutions on similar problems.

History from the western view:

Remember to take great care with the premises in both forms of reasoning!

8.5 Next time: structures and kinds of proofs

8.6 Homework

Groups are fine, turn in your own work. Homework is due in or before class on Mondays.

Write out (briefly) your approach to each problem.

Note that you may email homework. However, I don’t use MicrosoftTM products (e.g. Word), and software packages are notoriously finicky about translating mathematics.

If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.