Foundations of Mathematics
Summer Program for High School Students
Division of Special Programs, Columbia University
Final Exams, July 1999 -- Roger B. Blumberg

Each of the final exams consisted of several sections of problems, from which the students were to choose at least three questions to answer. The students had an hour to complete the exam, and they received extra credit for answering additional questions and/or the bonus question.

• Section I
• Section II
• Section V
• Section VI

Final Exam -- Section #1

1. Prove at least one of the following by mathematical induction:

2. Answer at least one of the following:

a. How many ways are there to divide a group of 28 people into one group of 10 persons and two groups of 9 persons each? Suppose the group of 28 is made up of 16 women and 12 men. How would your answer have changed if there was the additional requirement that each of the three groups had to contain at least 2 men?

b. Suppose eighteen points lie on a plane, no three of which are in a straight line (i.e. no three of them are colinear). How many different straight lines can be formed by joining pairs of points? How many different triangles can be formed by joining triples of points?

c. How many integers between 1 and 1,000,000 contain exactly 4 sevens and 1 three?

3. Answer at least one of the following questions.

a. Suppose a computer generates a 8 digit number at random. What is the probability that the first digit is prime and the last digit is a 5?

b. Is it more likely to get the sum of 10 when rolling two dice or when rolling three dice (assuming the dice are "fair")?

c. What is the probability that four cards dealt from a normal deck of 52 playing cards will contain exactly one card from each of the four suits?

Bonus: Suppose you go to a party at which people who know each other greet each other by shaking hands. Is it true that at such a party, the number of people who have shaken an odd number of hands is even? If so, prove it (by whatever method you like). If not, explain why not.

Final Exam -- Section II

1. Prove at least one of the following by mathematical induction:

2. Answer at least one of the following:

a. Suppose twelve points lie on a plane, no three of which are in a straight line (i.e. no three of them are colinear). How many different straight lines can be formed by joining pairs of points? How many different triangles can be formed by joining triples of points?

b. How many ways are there to divide a group of 24 people into one group of 10 persons and two groups of 7 persons each? Suppose the group of 24 is made up of 12 men and 12 women. How would your answer have changed if there was the additional requirement that each of the three groups had to contain at least 1 man?

c. Show that, for integers n >= r >= k >= 0, C(n,r)*C(r,k) = C(n,k)*C(n-k, r-k). Give an example that illustrates what this equality, known as Newton's Identity, tells us about different ways of choosing subsets of subsets.

3. Answer at least one of the following questions.

a. Suppose a computer generates a 6 digit number at random. What is the probability that the first digit is odd and the last digit is either a 4 or a 7?

b. If ten fair coins are tossed, what is the probability of getting exactly 5 heads? at least 2 heads?

c. Which of the following has the higher probability:

• rolling 4 dice and getting at least one six.
• rolling 2 dice 24 times and getting at least one double-six.

Bonus: Suppose you go to a party at which people who know each other greet each other by shaking hands. Is it true that at such a party, the number of people who have shaken an odd number of hands is even? If so, prove it (by whatever method you like). If not, explain why not.

Final Exam -- Section V

1. Prove at least one of the following by mathematical induction:

2. Answer at least one of the following:

a. How many ways are there to divide a group of 20 people into one group of 10 persons and two groups of 5 persons each? Suppose the group of 20 is made up of 12 men and 8 women. How would your answer have changed if there was the additional requirement that each of the three groups had to contain at least 1 man?

b. Suppose twenty-one points lie on a plane, no three of which are in a straight line (i.e. no three of them are colinear). How many different straight lines can be formed by joining pairs of points? How many different triangles can be formed by joining triples of points?

c. How many integers between 1 and 1,000,000 contain exactly 3 4s and 2 3s?

3. Answer at least one of the following questions.

a. Suppose a computer generates a 7 digit number at random. What is the probability that the first digit is prime and the last digit is a 5?

b. Is it more likely to get the sum of 10 when rolling two dice or three dice (assume the dice are fair)?

c. What is the probability that four cards dealt from a deck of 52 playing cards will contain exactly one card of each of the four suits?

Bonus: Suppose you go to a party at which people who know each other greet each other by shaking hands. Is it true that at such a party, the number of people who have shaken an odd number of hands is even? If so, prove it (by whatever method you like). If not, explain why not.

Final Exam -- Section VI

1. Prove at least one of the following by mathematical induction:

2. Answer at least one of the following:

a. Suppose eighteen points lie on a plane, no three of which are in a straight line (i.e. no three of them are colinear). How many different straight lines can be formed by joining pairs of points? How many different triangles can be formed by joining triples of points?

b. Suppose you have 4 French books, 7 Spanish books and 3 Russian books, and you decide to put them on a single shelf, arranging them at random. How many different arrangements will there be that keep all the books of a given language together (i.e side-by-side) on the shelf?

b. Suppose fifteen points lie on a plane, no three of which are in a straight line (i.e. no three of them are colinear). How many different straight lines can be formed by joining pairs of points? How many different triangles can be formed by joining triples of points?

c. Prove that:

3. Answer at least one of the following questions.

a. Is it more likely to get the sum of 12 when rolling two dice or three dice (assume the dice are fair)?

b. Which of the following has the higher probability:


i. rolling 4 dice and getting at least one 6.
ii. rolling 2 dice 24 times and getting at least one double-six.

c. Suppose a computer generates a 5 digit number at random. What is the probability that the first digit is either a 6 or a 7 and the last digit is odd?

Bonus: Suppose you go to a party at which people who know each other greet each other by shaking hands. Is it true that at such a party, the number of people who have shaken an odd number of hands is even? If so, prove it (by whatever method you like). If not, explain why not.

© 1999 Roger B. Blumberg