This section is reserved for riddles of a highly mathematical nature. Whereas most riddles in the easy, medium, hard, and microsoft sections can theoretically be solved with reasoning and creativity alone, the riddles below may require exposure to particular math concepts. I haven't been entirely consistent with this partitioning rule though ... knowledge of introductory probability theory is an occasional requirement I have deemed suitable for regular riddles sections.

Problems which begin with a MM/DD/YY date were carefully selected by Dr. William Kahan for Math H90 at UC Berkeley.

8/26/2002: A column vector x is distributed randomly and uniformly over the surface of the unit sphere in an N-dimensional Euclidean space. What is the expected (mean) value of the squared length of x's projection onto a K-dimensional plane through the sphere's center?

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(1-z) * sqrt(1+z) 
F(z) := sqrt(z^2 - 1), G(z) := sqrt(z-1) * 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)?

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.

9/3/2002: Suppose a set of m real n-by-n 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.)

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 N-dimensional 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?)

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)

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.

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.

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?

Suppose a 1-liter bottle of wine is hanging from the ceiling, and from it hangs a 1-liter 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.

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.

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

The octagon P₁P₂P₃P₄P₅P₆P₇P₈ is inscribed in a circle, with the vertices around the circumference in the given order. Given that the polygon P₁P₃P₅P₇ is a square of area 5 and the polygon P₂P₄P₆P₈ is a rectangle of area 4, nd the maximum possible area of the octagon.

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?

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 cross-list 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.

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

11/20/2001: Here is a way to cut a perfectly circular pizza into sector-shaped 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 turn-and-cut 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?

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.

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.

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 edge-lengths will differ from 1 by less than epsilon, where epsilon is any positive constant.)

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 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 N-by- N square array of pieces can be reduced by legal moves to a 1-by-1 array.

Note: Taken from 1993 Math Olympiad.

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.

Joining every vertex of a convex pentagon to every other vertex forms three nested figures:

• the original outer pentagon
• an inner pentagon
• a five-pointed star between them

Suppose the perimeters of these three figures are all primes; show that the three primes’ sum is at least 20.

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.