Chapter 8
Notes for 27 August

8.1 Review

• A special case is quite literally a case set aside as special.
• A representative special case is a special case that accurately represents the general case. with a specific case.
• The specific case must not depend on which case is used\mathop{\mathop{…}}
• We proved that the sum of the i^th row is {2}^{i-1}.
• Will return to proofs next time. Today, two tactics / principles and discussion of general mathematical reasoning.

8.2 Ruling out possibilities

• We’ve already seen this in building tables, guessing, etc.
  • If the result must be even, don’t list odd numbers.
  • In the diagram where we filled in circles along the sides of a triangle to equal integers in the vertices, we never needed to guess larger than the smallest integer.
• Generally, use whatever rules apply to reduce your problem.
• In an extreme case, only one result may be left standing.

8.2.1 Logic puzzles

• Classical problem structure. Provide lists of items along with properties linking the lists. Then derive the only possible matching between the lists.
• Zillions of logic puzzles available on-line or in puzzle magazines.

• General strategy: Form a table to track possibilities.
• Fill in what is known from each rule (noted (1), (2), (3) below).
• Cross out possiblities that cannot occur (similar notation).
• What possibilities remains? Judy and Fred
• That leaves one spot left, John and Gretchen

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

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

• Useful for proving or demonstrating a fact through counting.
• Assume there are 14 black socks and 6 white socks in the drawer. Without looking, how many socks must you retrieve to have two of the same color?
  • How might you consider solving this? Write out all possibilities for each number of socks you retrieve. Yuck.
  • Here there are two “holes”, black and white.
  • You need draw three socks to guarantee two of the same color!
• Frighteningly powerful principle.
  • Ignoring baldness, there are at least two people in the tri-cities area with the same number of hairs on their head.
    • There are about 150 thousand hairs in a typical head of hair.
    • According to the 2000 census, there are 480 091 people in the tri-cities area.
    • If we assume no one has over 480 000 hairs, and each “hair count” is a category / pigeonhole, then there must be two people with the same number of hairs.
  • A “lossless” file compression system must expand some files.
    • Compressed files are pigeonholes.
    • There are fewer possible files of smaller size.
    • Hence if all files can compress to smaller sizes, there will be two files that compress to the same file.

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:

Inductive

Making an ”educated” guess from prior observations.

Deductive

If premises are satisfied, conclusion follows.

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

Typically,

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:

• Old example: Egyptian papyri (1900bc-1800bc)
  • Consisted of arithmetic tables followed by a list of worked problems.
  • Solve “new” problems by imitating previous ones.
  • No pure “symbols”; only count or calculate with “real” items. (Hieroglyphics hurt.)
• Continued through to Greek times
  • Geometry replaced explicit counting.
  • No “variables” but rather geometric figures.
    • Every concept had to be illustrated geometrically.
    • Pythagoras constructed proportions from lengths.
  • However, deductive reasoning began in earnest.
    • Around 600bc, Greek mathematicians began discussing and proving theorems.
    • Euclid’s Elements, 300bc, developed systematic and rigorous proofs.
  • Proofs complicated by the restriction to geometric figures.
• Algebra, the beginning of fully abstract proofs:
  • 500bc for Babylonians!
  • 200ad for Greeks (Diophantus of Alexandria)
  • Spread widely from Persians, Muhammad ibn Mūsā al-khwārizm̄ in 820ad.
    • (transliteration of his book’s title gave “algebra”, his name gives “algorithm”)
• So modern “proof” only became feasible 1200 years ago.
• Wasn’t widely adopted until the nineteenth century, 200 years ago.
• So if proof seems difficult, remember that humanity took a long, long time to develop the idea.
• The concept of proof still is evolving!
• Historical summary from Prof. Steven Krantz at

  http://www.math.wustl.edu/ sk/eolss.pdf

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

• Inductive reasoning generalizes from examples.
• If the examples are not appropriate, the result will be incorrect.
• Say there is a line of women waiting for a rest room. You assume it’s the lady’s room. But if there is only one rest room\mathop{\mathop{…}}

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.

• In problem set 1.4 (p48):
  • For reducing the number of possibilites: problem 7
  • Logic puzzle: problem 9
  • Pigeonholes: Problems 12 (ignoring leap years), 13, 14
    • Note that 12 wants the number that guarantees two people have the same birthday.
• Which of these statements demonstrate inductive reasoning, and which demonstrate deductive reasoning? Justify.
  • It has rained for the past week. It will rain tomorrow.
  • All men are mortal. Socrates is a man. Therefore, Socrates is mortal.
  • Satellite-based network access does not function through heavy rain. It is raining heavily. I cannot upload the notes right now.
  • The next number after 3, 8, 13, 18, and 23 is 28.

Note that you may email homework. However, I don’t use Microsoft^TM 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.