..:: wu : riddles ::..
[ tech-interview style riddles and mathematical puzzles. daily high-quality forum discussions ]
intro [:: FORUM ::] easy med hard m$ cs putnam cigs FAQ pros cons laff credits about me

Page last modified Sunday, 06-Nov-2011 21:03:27 MST bookmark this page
visit the riddles forum

SYMBOLS

MNeeds math past arithmetic and basic probability.
CRequires knowing how to play chess.
PPhysics knowledge is helpful.
>=PI don't know the solution to this problem myself.
CPURequires calculator/computer power.


FORUM

Stuck? Have compliments or criticisms?
Want to test-drive a new riddle of your own?
Who are we, and what do we do?
Visit the fantabulous riddle forum!
Thousands of posts by really clever people.


RIDDLE INDEX

easy
med
hard
m$
cs
putnam

RECENT ADDITIONS

Check out latest puzzles by perusing the forum and the 10 most recent posts. Latest additions to cover site can be seen by clicking here.

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.


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

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(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)?

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

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

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

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 P1P2P3P4P5P6P7P8 is inscribed in a circle, with the vertices around the circumference in the given order. Given that the polygon P1P3P5P7 is a square of area 5 and the polygon P2P4P6P8 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 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.

DERIVATIVE GOES TO ZERO

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?

PIZZA SLICING

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?

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 edge-lengths 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 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.

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

INVERTIBILITY OF I-AB

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.


Thanks to Contributors David Lau, Siddhartha Doshi, Jiong Shen, Carl Wang, Phoebus Chen, Alan Liu, Hansen Bow, Ernest Zhu, Elaine Lo, Yosen Lin, Don Barkauskas, Katherine Chan, Jasvir Nagra, Tau Beta Pi (TBP), Eta Kappa Nu (HKN), Danny Dulai, His Grace The Duke Of Ankh-Morpork Commander Sir Samuel Vimes, Michael Snyder, Dipan K. Ghosh, Eric Cole, Louis Wainwright, Ben Bardill, Patrick Dreker, Autumn Looijen, Stephen Champailler, Christopher Kings-Lynne, Bart Samwel, Kannan Ramchandran, Nick Yee, Steve Plimpton, Levsen Hendrik, Remco Hartog, [I.M._Smarter_Enyu], Philip Mock, Michael Chang, Jon Meilstrup, Ryan Russell, Matt Young, Jonathan Haas, Geoff Canyon, Peter Surda, Cory Ondrejka, Satish Rao, [gcooper], Ted Powell, Brave Sir Robin, Eric Cole, J. A. H. Hunter, Sean R. Owen, Andrew Glenn, Bruce Preston, Peter Ratiu, Michael Mendelsohn, Rob Mahurin, James Fingas, Bryan Organ, Jeroen Rutten, Stephen Montgomery-Smith, Marko Lukat, Eric Yeh, Nick Hobson, Mike Lawther, [anshil], Richard Feynman, Douglas Hofstaeder, Dacher Keltner, David Mace, [SAS], Matthew Schultheis, John Leen, Andrew Ooi, Folkert Hindriks, Steve Ragle, Daniel Filner, Karl Barrus, Misha Kruk, Keith Lloyd, Dave Minott, Jette Randlov, Eric Winger, Nathan Hellweg, Tom VanCourt, Chris Seaton, Mitchell Morris, Michael Styer, Zameer Andani, Jonathan Blow, Jeff Thompson, Jonathon Duerig, Dan Hanson, Gabriel Sechan, Tom Saxton, [HunterWare], [alsee], James Antill, Tom Barringer, Bart Massey, David Krikorian, Eric Sharkey, [tudorb], Kevin Day, Milan Ramaiya, Robert Merkel, James Jones, Haim Bitner, Adam Barth, Oscar Lazzarino, Damien Fisher, [DrkShadow], Erik Blankendaal, Eric Smith, James Demmel, Jonathan Shewchuk, Alex Harris, Michael Kelley, [Mr._Martingale], Kaisen Lin, Hakan Yilmaz, Freddy Mercury, Justin Rising, Marko Lukat, William Kahan, Jeremy Randolph, Michael Sinatra, David Messerschmitt, Patrick Masterson, Frederik Bonte, Randy Williams, Pietro K.C., Brett Danaher, Derek Abbott, Ralph Boleslavsky, Rui del-Negro, [college math journal], [amer. math monthly], Spyros Potamianos, Gary Hsieh, [rec.puzzles], Steven Rudich, Matt Lahut, Richard Reti, Paul Sinclair, Tim Mann, [ucb engineering news], Luke Percival, Anwis Das, Mike White, Louise Poon, Jeffrey Wilhelm, Anthony Cammon, [BNC], A.Frieze & D.Sleator, [SWF], Ted Stevens, Frank Wang, Danny P, Patrick Sesulka, [towr], Chi Sum Cheung, Ranjit Jhala, Jacob Scott, David McKay, Eamon Warnock (THUDandBLUNDER), Kozo Morimoto, Abhijit Joshi, Devesh Parekh, Amnon Melzer, Mary Lou, Leonid Brouhkis, Allistair Sinclair, Mark Newheiser, Joc Koelman, Paul Jung, Aryabhatta, Thomas Cover, Barukh, Nootch, Eigenray

William Wu © 2002-09: intro | easy | medium | hard | microsoft | cs | putnam | cigs | faq | pros | cons | laff | forum | credits | about me |