Pi Mu Epsilon Undergraduate Math Society at USC
Fall 2002 Semester
Organizers: Sergey Lototsky and Royce Peng.
- 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
Try to use the above to show that, for a prime p, the number 2^p+3^p
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).
- 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
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.
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
office, DRB 258).
- 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?
- 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
number of rolls to get a repeat? (It is somewhere between 2 and n+1).
- 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
- 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).
- 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
- 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.
- 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.
- 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.
Problems B-4 from 1995 Putnam: consider the continued fraction f(n) with
n instead of 2207. Then f^2(n)=f(n^2-2). Together with the observation that
2209=47^2, the solution is then easy.
- 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
- 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
- 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.
- 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.
- 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
- 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