putnam exam problems 
EXPECTED PROJECTION LENGTH 
8/26/2002: A column vector x is distributed randomly and uniformly over the surface of the unit sphere in an Ndimensional Euclidean space. What is the expected (mean) value of the squared length of x's projection onto a Kdimensional plane through the sphere's center?

COMPLEX PRINCIPAL SQUARE ROOTS 
8/26/2002: The complex Principal Square Root sqrt(z) of a complex number z is the square root (one of two if z != 0) whose Real Part is nonnegative. If z<0 (so Re(sqrt(z)) = 0) then assign the same sign to Im(sqrt(z)) as to Im(z). (Yes, zero has a sign.)
Now let:
f(z) := sqrt(1  z^2), g(z) := sqrt(1z) * sqrt(1+z)
F(z) := sqrt(z^2  1), G(z) := sqrt(z1) * sqrt(z+1)
Over what region in the complex plane does f(z) = g(z)?
Over what region in the complex plane does F(z) = G(z)?

SUM OF DYADS 
9/3/2002: A matrix of rank 1 is called a dyad. Every matrix can be expressed as a sum of dyads. In one such expression for a matrix Z the number of dyads in its sum is just the number of nonzero elements in Z. Most matrices Z can be expressed as a sum of dyads in many different ways. Show that the minimum number of dyads in such a sum equals the rank of Z.

SUM OF MATRICES 
9/3/2002: Suppose a set of m real nbyn matrices has a nonsingular (invertible) sum. Show that some subset of at most n of those matrices also has a nonsingular sum. (Not an easy problem.)

INTERSECTING CONVEX HULLS 
9/3/2002: The Convex Hull of a set P of points is the smallest convex set containing P. Show that any set of at least N+2 distinct points in an Ndimensional real vector space can be partitioned into two disjoint subsets whose two convex hulls have a nonempty intersection. For example, in the plane (N=2) any four distinct points are either three vertices of a triangle plus a point inside it, or else four vertices of a quadrilateral whose diagonals intersect. (Problem suggested by George Bergman. A Convex Set in a linear space is one that includes, with any two points in the set, also the line segment joining them. Consequently included too is every positively weighted average of any subset of points in the convex set; can you see why?)

PARTITION 
Given a natural number n, a partition P of n is a nondecreasing sequence (a_1, ... , a_k) of strictly positive integers such that the sum of its terms is n. For instance, the partitions of 4 are:
(1,1,1,1), (1,1,2), (1,3), (2,2), (4)
Given a particular partition P of n, let A(P) be the number of 1's to appear in P, and let B(P) be the number of distinct elements of P. So A(1,1,1,1) = 4 and B(1,1,1,1) = 1. Prove that, for all n,
sum A(P) = sum B(P)
where the sum extends over all partitions of n. (For n = 4, both sums are equal to 7, for example)

SUM THE DIVISORS 
9/13/2002: A Perfect Number is a positive integer equal to half the sum of all its divisors. Two examples are 6 = (1+2+3+6)/2 and 28 = (1+2+4+7+14+28)/2. All Perfect Numbers found over the past two and a half millenia are even; nobody knows whether odd Perfect Numbers exist.
If either n = 1 mod 6 or n = 1 mod 4, show why n cannot be a Perfect Number.
Note: In the modular arithmetic equations of the 2nd paragraph shown above, the "=" symbol in this context means congruent to. The congruence symbol is drawn with three horizontal bars instead of two.

SUM THE NUMBER OF DIVISORS 
9/13/2002: Let c(n) be a function that counts how many positive divisors the positive integer n has, and let
S(n) := summation over d/n { c(d) }
be the sum of the counts c(d) taken over all divisors d of n. Example: 18 is divisible by 1, 2, 3, 6, 9, and 18, so c(18) = 6. Since c(1) = 1, c(2) = c(3) = 2, c(6) = 4 and c(9) = 3, we find that S(18) = 1+2+2+4+3+6 = 18. Find all roots n of the equation S(n) = n.

ARITHMETIC PROGRESSIONS 
9/13/2002: For which integers n>1 does the set of positive integers less than and relatively prime to n constitute an arithmetic progression?

WINE AND WATER 
Suppose a 1liter bottle of wine is hanging from the ceiling, and from it hangs a 1liter bottle of water. On the bottom of both bottles there is a small hole, through which a constant amount of fluid pours out (neglecting pressure differences). So the wine bottle is becoming empty and the water bottle remains full, though the concentration of wine is increasing.
Assuming that wine and water mix instantly and completely, find out the concentration of wine in the water bottle after the top one is empty. Give two different methods of solution.

GAS STATIONS 
Suppose a race track in the shape of a simple closed curve (i.e. it does not intersect itself), and suppose that distributed along it, in any way whatsoever, are N gas stations. Suppose that a race car needs L liters of gas to go completely around the track, and that the sum of the gas available at the N stations is exactly L.
Consider that the car cannot move without gas (independently of its momentum when it runs out ), and that it has constant mileage (consumption of gas is directly proportional to the distance the car moves, and depends on nothing else).
Prove that there exists at least one gas station such that, starting from it, the car can do a full lap.

3 POINTS IN CIRCLE 
Three distinct points with integer coordinates lie in the plane on a circle of radius r > 0. Show that two of these points are separated by a distance of at least r^(1/3).

MAX OCTAGON AREA 
The octagon P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}P_{7}P_{8} is inscribed in a circle, with the vertices around the circumference in the given order. Given that the polygon P_{1}P_{3}P_{5}P_{7} is a square of area
5 and the polygon P_{2}P_{4}P_{6}P_{8} is a rectangle of area 4, nd the maximum possible area of
the octagon.

CHAIN OF SUBSETS 
10/16/2001: A Chain of subsets of a set W is a collection S of nested subsets of W ; this means that,
of any two members of S , one subset must contain the other. Must every chain of subsets of the
positive integers be countable? Why?

BRIGHT AND DARK STARS 
10/23/2001: A Bright Star is a sphere, not just a point, that emits light in all directions from every point
on its surface. A Dark Star is an opaque sphere whose dull black surface reflects no light. Dark
Stars come in all sizes. Your assignment is to get and position a few of them around a given
Bright Star in such a way as will absorb all its light, thus rendering it invisible from afar in every
direction. What is the minimum number of Dark Stars required to carry out this task, and why?
Note 1: Brought to Math H90 at UC Berkeley by Jason Behrstock in 1995.
Note 2: I've decided to crosslist this riddle in the hard section. The accessibility of the beautiful premise makes it suitable there, but the solution may seem more appropriate for a mathematical audience (putnam section). Couldn't make up my mind.

DERIVATIVE GOES TO ZERO 
10/1/2001: Suppose f(t) is a continuously oncedifferentiable strictly decreasing positive function for all t >= 0 . Must the derivative f'(t) = 0 as t approaches infinity? Why?

PIZZA SLICING 
11/20/2001: Here is a way to cut a perfectly circular pizza into sectorshaped slices for N people some of
whom demand small slices, some large, and the rest will accept any size: First choose any
irrational number s . Cut the pizza from its center east to its edge; then turn the pizza through an
angle s*pi clockwise and cut it again from its center east to its edge; repeat this turnandcut until
the pizza has been cut into N sectors. Prove that they have just two or three different sizes.
Much harder problem: how do you choose s?

NINE POINTS ON SPHERE 
10/03/2001: Show how to distribute nine points around the surface of a sphere in such a way that each
point is equidistant from its four nearest neighbors.

FOURTH DEGREE POLYNOMIALS 
9/25/2001: Someone has claimed to have discovered an algorithm that determines which polynomial equations of total degree 4 in arbitrarily many variables with integer coefficients have integer solutions. Show how it could be used to determine which polynomial equations of arbitrary degree in arbitrarily many variables with integer coefficients have integer solutions.

RECTANGLE INTO SQUARE 
You are given a rectangular sheet of paper, and asked to transform it into a square by cutting off and discarding parts of the sheet repeatedly. The style of your cuts is restricted by the following rules:
 Each cut must be parallel to one or other of a rectangle’s edges.
 A cut may halve a rectangle, or it may separate one third of a rectangle from the rest, and then either piece may be discarded.
Show that a sequence of cuts under these restrictions can reduce the rectangle to a square in the limiting case. (Technically speaking, show that the ratio of the edgelengths will differ from 1 by less than epsilon, where epsilon is any positive constant.)

CLOSED CONVEX CURVE 
11/17/2000
(a) Prove that each closed convex curve C in the plane can be circumscribed by at least one
triangle T that touches C at the midpoints of T’s sides. (A “closed convex curve” is the
boundary of a convex region that lies inside some circle. A parabola is convex but not closed.)
(b) Show why “at least one” may be replaced by “at least two” in (a). To simplify the proof
you may assume C is smooth (continuously twice differentiable) and rotund (no flat spots).

CHECKERBOARD SOLITAIRE 
Checkerboard Solitaire is a game played on an infinite checkerboard with pieces confined to
the board’s squares. A legal move jumps one piece vertically or horizontally over another
immediately neighboring piece provided the square after that, where the jumper lands, was
empty; and then the jumped piece is removed. For instance, if the configuration _XYZ_ is
isolated then neither piece X nor Z can move but Y can jump over and remove either piece to
produce either Y_ _Z_ or _X_ _Y . (A legal move resembles a single jump in Checkers except
that checkers come in two colors, move diagonally instead of vertically or horizontally, and can
move without jumping.) Determine (with proof) the set of integers N for which an initial Nby
N square array of pieces can be reduced by legal moves to a 1by1 array.
Note: Taken from 1993 Math Olympiad.

TRIANGULAR NUMBERS 
Prove that there is an infinite number of distinct ordered pairs (m, n) of integers such that, for every positive integer t, the number mt + n is a triangular number if and only if t is one as well. For instance, the pair (1, 0) trivially satisfies the requirement, because 1*t + 0 = t is a triangular number if and only if t is.

PENTAGON PUZZLE 
Joining every vertex of a convex pentagon to every other vertex forms three nested figures:
 the original outer pentagon
 an inner pentagon
 a fivepointed star between them
Suppose the perimeters of these three figures are all primes; show that the three primes’ sum is at least 20.

INVERTIBILITY OF IAB 
Let A and B be square matrices. Now suppose I  BA is invertible, where I is the identity matrix. Prove that this implies I  AB is also invertible.
