Foundations of Mathematics
Summer Program for High School Students
Division of Special Programs, Columbia University
Final Exams, July 2000 -- 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 3 sevens and 1 three?

3. Do one (1) of the following:

a. Prove, by any method you like, that if n is a prime number, and r is not equal to 0 or n, then C(n,r) is a multiple of n.

b. Prove, by any method you like, that C(n+1, r) = C(n, r) + C(n, r-1)

c. Prove, by any method you like, that

C(n,4) = [n(n-1)(n-2)(n-3)] / (1*2*3*4)

Bonus: Find a formula for the following series, and then prove it is true for all n by mathematical induction:

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

3. Answer at least one of the following questions.

a. Suppose a computer generates a 6 digit number at random. How many ways are there for the number to have an odd first digit and a last digit that is either a 4 or a 7?

b. Prove, by any method you like, that if r <= k <= n, then:

C(n,k) x C(k,r) = C(n,r) x C(n-r, k-r)

c. Prove, by any method you like, that for every integer n>0:

1(1!) + 2(2!) + 3(3!) + ..... + n(n!) = (n+1)! - 1

Bonus: Find a formula for the following series, and then prove it is true for all n by mathematical induction:

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 a computer generates a 10 digit number at random. How many different ways can the number begin with a prime, end with a 5, and have no even digits?

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. Prove, by any method you like, that for n>0, 1(1!) + 2(2!) + 3(3!) + ..... + n(n!) = (n+1)! - 1

b. Prove, by any method you like, that all integers greater than 1 can be expressed as a finite product of prime numbers.

c. Prove, by any method you like, that if r<=k<=n, then:

C(n,k) x C(k,r) = C(n,r) x C(n-r, k-r)

Bonus: Find a formula for the following sum, for n>0, and prove it using mathematical induction:

Final Exam -- Section VI

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

2. Answer at least one of the following:

a. In a 3-D graph, how many non-decreasing paths are there between the origin (0,0,0) and the point (5,7,5), if the possible directions of movement are fixed by the x, y and z axis'?

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?

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

3. Answer at least one of the following questions.

a. Prove, by any method you like, that:

b. Prove, by any method you like, that in any closed social network of n persons, the number of people with an odd number of friends must be even (with "friendship" defined as a mutual and 1:1 relationship).

c. How many binary messages of length 12 can be generated that begin with 1 and have twice as many 0s as 1s?

Bonus: Find a formula for the following series, and then prove it is true for all n by mathematical induction:

© 2000 Roger B. Blumberg