Foundations of Mathematics
Summer Program for High School Students
Division of Special Programs, Columbia University
Final Exams, July 2001 -- 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. 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?

b. How many integers between 1 and 100,000 contain exactly 4 threes and 1 seven? at least 4 threes?.

c. The license plates in a certain state have three letters followed by three numbers. How many different license plates can be made? How many license plates can be made if all of them must start with either RI, BU or FE?

3. Answer at least one of the following questions.

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

b. Prove, using any method you like, that C(n,r) = n/r * C(n-1,r-1).

c. In a 3-dimensional graph, how many non-decreasing paths can be followed between the origin (0,0,0) and the point (7,3,9), if the possible directions of the moves are fixed by the x, y and z axes?

d. Which of the following has the higher probability:

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

Bonus: Suppose a company that sells magazine subscriptions over the phone has 13 magazines to choose from. Any person the company calls might decide to subscribe to none of the magazines, all of them, or some of them. If you are selling these subscriptions over the phone, how many different possible responses might you receive from the people you call?

Final Exam -- Section II

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 choose 5 letters from the word BRAINSTORM? How many different arrangements of 5 letters can be made if the first two letters must be vowels, and the other three consonants?

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.How many integers between 1 and 1,000,000 contain exactly 4 fives and 2 threes? at least 4 fives?

d.Suppose a company that sells magazine subscriptions over the phone has 13 magazines to choose from. Any person the company calls might decide to subscribe to none of the magazines, all of them, or some of them. If you are selling these subscriptions over the phone, how many different possible responses might you receive from the people you call?

3. Answer at least one of the following questions.

a. Find a general formula for the following sum, for n>0, and prove it by direct proof: C(n+1,2) + C(n+2,2) = ??

b. 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 odd?

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

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. 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 7 Spanish books, 5 Turkish books and 4 Chinese 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?

c. How many ways are there to choose 5 letters from the word BRAINSTORM? How many different arrangements of 5 letters can be made if the first two letters must be vowels, and the other three consonants?

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. Prove, by any method you like, that (if r is not 0), C(n,r) = n/r * C(n-1,r-1)

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

Bonus: Suppose a company that sells magazine subscriptions over the phone has 13 magazines to choose from. Any person the company calls might decide to subscribe to none of the magazines, all of them, or some of them. If you are selling these subscriptions over the phone, how many different possible responses might you receive from the people you call?

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 you have 3 French books, 7 Spanish books and 2 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 a company that sells magazine subscriptions over the phone has 13 magazines to choose from. Any person the company calls might decide to subscribe to none of the magazines, all of them, or some of them. If you are selling these subscriptions over the phone, how many different possible responses might you receive from the people you call?

c. Suppose sixteen 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?

3. Answer at least one of the following questions.

a. Prove, by any method you like, that C(n+2,3) - C(n,3) = n^2

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 even and the last digit is prime?

d. How many binary messages of length 16 can be generated that have three times as many 1s as 0s? more than three times as many 1s as 0s?

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.

© 2001 Roger B. Blumberg