Pi Mu Epsilon Undergraduate Math Society at USC
Fall 2002 Semester

Organizers: Sergey Lototsky and Royce Peng.

September 6

When faced with a problem that has a collection of real numbers and no obvious solution, arrange the numbers in increasing or decreasing order. This ordering can help.
A large class of problems is about finding all functions with a given property. When the function is defined only for integer or natural numbers, one way is to come with a recursive relation for the function. This relation often results in a first- or second-order finite difference equation , and such difference equations can often be solved explicitly very much like their differential analogs. By solving the equation, you often solve the problem.

September 13

In many problems you are asked to find integer solutions of certain equations. One useful thing to do is to reduce the equation modulo a certain number, that is, to look at the remainders that both sides of the equation have when divide by that number.
Fermat's Little theorem: if p is prime and does not divide a, then a^p - a is divisible by p. This theorem often helps to perform the reduction modulo a prime.

Try to use the above to show that, for a prime p, the number 2^p+3^p cannot be a power of any number (we started by doing reductions modulo 2,3, 4, and p; for the last, we use Fermat's little theorem).

A problem to think about for the next meeting is number 3 from 42nd IMO. (This and many other problems can be picked up from an envelope outside my office, DRB 258).

September 20

We finally proved that, for a prime p, the number 2^p+3^p cannot be a power of any number. This was dome by reducing modulo 5 only and noticing that 2^p+3^p is divisible by 5 but not by 25. Do you think that, if a+b is a prime, then, similarly, a^p+b^p cannot be a power for any prime p?
A class of problems is to prove or derive a summation formula for a finite sum. One way to go is by induction, especially when the formula is already given.
Problem number 3 from 42nd IMO is still open (and there is no solution available...) Another open problem is about removing points from the plane that are at a rational distance from a given point. Can you remove all points in three steps?

September 27

Royce explained the "boys and girls problem" (number 3 from 42nd IMO) A useful observation is that, with 20 boys and 20 girls, you can have each solving 6 problems, with one problem shared by at least one boy and one girl, while no three boys and three girls solving the same problem.
Another type of "f(n) problems": showing that a certain function is unique or does not exist at all, when you have information about f(f(n)). While the result is usually obvious, a complete solution for such problems often requires careful (and sometimes long) reasoning. One example: show that there are no functions f:N to N so that f(f(n))=n+1987.
An open problem: if you roll an n-sided fair die, what is the expected number of rolls to get a repeat? (It is somewhere between 2 and n+1).

October 4.

We watched a movie about what life is like in the space that is the complement of a knot. There is some deep math behind that, and might watch the movie again after a lecture from an expert in the field.
We watched another movie, demonstrating how a sphere can be turned inside out without cutting or puncturing it. The fact itself is remarkable, and again, there is some deep math behind it and so we might watch the movie again later, this time with an expert in the audience.
The f(f(n)) problem from last time has an easy solution presented by Royce. The key is that, since f(f(n)) misses 1987 numbers, f(n) has to miss half as many, and that is impossible because 1987 is an odd number. Now the challenge is Problem A-4 from the 1993 Putnam exam (the problem is in the handout).

October 11.

The sum (n/n)+n(n-1)/n^2 +...+n!/n^n is expressed as a hypergeometric function. Can you get the asymptotic as n goes to infinity? (Royce conjectured a constant times square root of n).
We discussed Problem A-4 from the 1993 Putnam exam. A corollary: in any collection of n positive integer numbers, a sum of some of them is divisible by n.
We discussed Problem A-4 from the 1990 Putnam exam (the hole-punch problem). There is a nice connection with the Baire category theorem: a plane is not a countable union of circles. Generalizing the problem to n dimensions, you can remove all the points from the R^n in n+1 "hyper-punches".
Royce showed how to compute the expected number of coin tosses to get a particular sequence of heads and tails; for "HTHHHTH" the number is 138.
Now the challenge is Problem A-6 from the 1993 Putnam exam (the problem is in the handout) and its generalization to n+1 points on a hyper-sphere in R^n.

October 18.

We discussed the problem A-6 from the 1992 Putnam exam. The answer is 1/8, and in general, for n+1 points on a hyper-sphere in R^n, the probability that the simplex made out of these points contains the origin is 1/2^n. There is a completely inductive proof suggested by Royce.
It also makes sense to keep in mind the condition for the simplex on n+1 points in R^n to contain the origin (zero is a convex linear combination of the vertex vectors with positive coefficients)
One possible direction for further generalizations is to go back to a circle and choose points at random not from all the points on the circle but from the Nth roots of unity for sufficiently large N. What is the probability that the triangle on such three points will contain the origin strictly inside? What is the probability that the angle between two such randomly selected points will be bigger than 5\pi/6 (or some other number)?
We started problem B-5 from the 1995 Putnam. This is a game problem, and such problems are common on this exam. Royce described the general approach to such problems using ideas of parity. We should definitely get back to that and other similar problems.
We started problem A-4 from the 1995 Putnam. This is another integer-number-sum problem, and we'll discuss it next time.

October 25.

We discussed problem B-5 from the 1995 Putnam. One of the basic ideas is the idea of the sum of two games. If your game is the sum of two games so that the first player to move wins in one of the games and the second player to move wins in the other game, then the first player to move wins in the total game. Apparently, this is what is happening in this problem.
We discussed another "f(n)" problem. The conclusion was that a fully multiplicative function is determined by what is does with the primes; in that particular problem we got the general characterization of the involution on the set of primes: f(mn)=f(m)f(n); f(f(n))=n.
After that we continued, unintentionally, with the 1995 Putnam. We started problems B-4 and B-6 but did not finish them. Problem A-4 remains from October 18.
The general trend on Putnam is to have easy problems first on both "A" and "B" lists ("A" list is before lunch, "B" list is after lunch; some say that problem B_i is usually more difficult than problem A_i). With equal score for each problem, it makes sense to concentrate on the easy ones.

November 1.

Problem B-6 from 1995 Putnam: turns out that you get all the naturals as a disjoint union of two sets like those in the problem; therefore, you cannot do it with three.
Problem A-4 from 1995 Putnam: There is a nice graphical solution suggested by Royce. The idea is to start with any point on the circle and plot the points (k, sum of the first k numbers) for k=1,...,n and on from there as you go around the circle. After that you draw the lines with slopes (n-1)/n through each of the points and then cut the necklace at the point k corresponding to the highest lines. For that point, all the sums will be below that line, which is pretty much what we want.
We discussed problem 2 from the 41st IMO. There is a certain symmetry in the problem that reduces the considerations to only one relation between a,b,c. After that, you multiply two of the terms.
A problem to think about is number 3 from the 41st IMO.
Another suggestion is to look at all A-1 Putnam problems.

November 15.

With a joint effort, we solved B-3 from the 1996 Putnam.
We discussed, but did not complete, problem 4 from IMO 2000.
Problem 3 from IMO 1999 (not in the handout, but is on the web), was suggested by Royce and solved (more or less) by Marc.
We discussed A-3 from the 1994 Putnam (it is supposed to be a right isosceles triangle), but did not finish it.
Burton suggested to think about A-3 from the 1996 Putnam.
Royce suggested to try the first three A and B problems from as many Putnams as possible. Getting those problems right at the actual exam will give you a very very respectable score of 60.

November 22.

We discussed the problems from the previous meeting (IMO 1999, No. 3 and 2000 No. 4; Putnam 1994 A-3, 1996 A-3)
Marc suggested IMO 2000, No. 5. It supposedly uses the generalized Fermat's Little theorem, but we did not finish the problem.
Another problem, Putnam 1993 B-1 is supposed to be easy, and is an example of the problems to try first on the actual exam.
Next Friday is a holiday. On December 6 we might meet shortly to discuss whatever last minute questions you might have. Otherwise, I look forward to seeing you on Saturday, December 7, at about quarter to nine in the morning.

Back to the main page

Pi Mu Epsilon Undergraduate Math Society at USC Fall 2002 Semester