Mathematics 461, Autumn, 2005
Combinatorial Theory

Home Page

Instructor: Warfield
Email: warfield@math.washington.edu

Office: Padelford C-437
Office Hours: Mondays 2:15 - 3:15; Thursdays 3:00 - 4:00
Telephone: 543-7445

Final
I will be having office hours from 2 to 4 on Monday.
Anton will be having office hours from noon to 1:30 on Tuesday.

The final will consist of some problems directly from, or extremely closely modeled on the problems I handed out on Friday (and have just posted) and others directly from R or T assignments or problems worked in class.

Reading assignments, with R problems
for Monday, October 17:

Read Chapter 2, section 1
R problems are 2.1.2, 2.1.8, 2.1.10, 2.1.13

For Friday, October 21:

Read Chapter 2, sections 2 - 5
R problems are 2.2.1, 2.3.1 and 2.4.1

Additional R problems for Friday:

Out of the set of integers 1,...,100 you form a subset A consisting of ten different integers. Prove that you can always find two disjoint non-empty subsets T and S of A such that the sum of the elements of S is equal to the sum of the elements of T.
Note: S union T need not be all of the elements of A.

If each point of the plane is colored either red or blue, prove that there must exist a rectangle whose vertices are all of the same color.

For Wednesday, October 26, Read Chapter 3, sections 1 and 2.
R problems are 3.1.2 and 3.2.1

For Monday, October 31, Read all of Chapter 4.
R problems are 4.1.2, 4.1.3, 4.2.3, 4.2.8, 4.3.3

For Monday, November 14, read Chapter 5, sections 1 - 4
R problems are 5.1.1-5.1.5 and 5.2.1 - 5.2.4


for Wednesday, November 16:

R problems:

1) The closing concert of the Hoople Philharmonic season has an audience of 100 people, of whom 32 are deaf and 55 are asleep. 25 are both deaf and asleep. If Mrs. Murgatroyd on the front row is wide awake, what is the probability that she is deaf?


2) Joe, Fred, Annabelle and Suzy decide to recover from their Math 107 midterm by having dinner at the Maison de la Casa Grande House (specializing in teriyaki), which has nine dinners to choose from. They are too thoroughly wiped out to coordinate their orders, so they all choose randomly.

A) What is the probability that all four will choose different dinners?

B) What is the probability that at least two will choose the same dinner?

C) What is the probability that all four will choose the same dinner?

D) What is the probability that Fred and Joe will choose the same dinner?

3) You are the manager of a high class restaurant with a somewhat temperamental chef named Antoine. Last night he made a list of seven entrees and eight desserts which he would be willing to produce, but added darkly that in such a miniscule kitchen (only five ovens and a dozen burners) he could not possibly do more than five of the entrees and four of the desserts on the same day. Then, noticing that you looked a bit miffed, he conceded that there was an appetizer he would be willing to do if you wanted it. So you have made your choices and printed out a menu. Now Antoine has just stormed in to inform you that he is out of butter, which eliminates two entrees and two desserts. On the other hand, he has found a magnificent supply of the shrimp required for the appetizer he mentioned last night, and he will clearly be badly insulted if you don't offer it to your guests. What is the probability that your menu will not have to be changed?


4A) Baby Jane is playing with alphabet blocks. If she lines them up in random order, what is the probability that she will spell her name?

B) Same question for Baby Otto.


T problems have been transferred to a linked document, where they belonged in the first place.


for Monday, November 21

Read Chapter 7, Section 1
R Problems: 7.1.4

Also

1 Little Red Cinderlocks lives in a candy cottage in an enchanted forest. Her life would be idyllic were it not that the forest is also occupied by dragons. 50 of them are green dragons, and actually rather friendly, but the other 20 are red dragons, whose favorite dinner is Little Girl. The green dragons are rather mellow, so only 10 of them have retained their capacity to breathe flame. The red ones, on the other hand, like Little Girl toasted, so all but 3 of them are able to breathe flame. One afternoon Little Red Cinderlocks hears the unmistakeable appoach of a dragon. Shortly after that the roof of her cottage abruptly melts off under the influence of a shot of dragon flame. What is the probability that her visitor is green?


2 A musicologist is attempting to determine the composer of a Baroque ditty recently found under a beer keg in the home of the brothers Archangelo and Pistachio Spumoni. Both were composers and no other musician would have set foot in the house. Archangelo wrote twice as many compositions as Pistachio. Unfortunately, neither brother ever figured out how to write in any key except F minor and A major. Archangelo wrote in the former 80% of the time, and Pistachio in the latter 60% of the time. Once the dried beer is scraped off, the composition turns out to have been written in F minor. What is the probability that it was written by Archangelo?

3 From the Web (http://canques.seer.cancer.gov): the incidence of prostate cancer in the Puget Sound area is 166.7 per 2000 men.

From the Journal of HMO Practice (Volume 6, #4): PSA (Prostatic Specific Antigen) screening results in 72% false positives. There is no alternative non-invasive test available, so anyone with a positive PSA result must have a biopsy done. Assume that there are no false negatives.

If a man has a positive result from a PSA test, what is the probability that he has a cancer that needs treatment? What is the probability that he will have an unnecessary biopsy?


For Wednesday, November 30

Read Chapter 7, sections 2 and 3.

R-problems: 7.2.2, 7.2.3, 7.2.6, 7.3.1 and 7.3.3

For Monday, December 5

Read Chapter 8, sections 1 and 2
and Chapter 9, sections 1 and 2

R problems: 8.1.2; 8.1.3; 8.2.3; 9.1.1; 9.2.2

For Wednesday, December 7

Read Chapter 12, sections 1 - 3

R problems: 12.1.1; 12.2.1
Last modified: 12/12/2005 10:01 AM