Freshman Seminar 24i applicants' Essay 2 problems (Fall 2008)
(in the order received):

• The unreasonably ubiquitous Golden Ratio φ = (1+sqrt(5))/2 = 1.61803..., arising everywhere from the regular pentagon (ratio of diagonal to side length, a.k.a. 2*sin(54°)) to the Fibonacci numbers (as the limit ratio of consecutive terms). Here's a related but less familiar instance: if A,B,C,D are points in the plane such that the distances AB=BC=CD=1 and CA=AD=DB=x, what are the possible values of x? [Added later:] See also the quartics problem below.
• Ford circles: circles of radius 1/(2q²) tangent from the same side to a line at each rational point p/q (in lowest terms) are often tangent but never intersect. (The blue semicircles in the picture are orthogonal to each pair of tangent Ford circles at their point of tangency.)
• The Tijdeman-Zagier (a.k.a. Beal) conjecture: x^r + y^s = z^t has no solution in positive integers with x,y,z pairwise coprime and r,s,t all >2. (Probably very hard: “Fermat's Last Theorem” is the special case r=s=t. See also my article The ABC's of Number Theory in the inaugural issue of the Harvard College Math Review, where this conjecture is mentioned on page 65, which is the 9th page of text in the article.)
• The “Monty Hall problem/paradox” (recently spotted also in the movie 21).
• How many 0-1 strings of length 15 have no 00 or 111 substrings? (For instance, at length 4 there are five: 0101, 0110, 1010, 1011, 1101. Be careful about generalizing from the first few cases...) I might add: of those strings, how many have (say) six 0's and nine 1's?
• A “linear Diophantine equation” expressed as a dollars-and-cents puzzle: Bank teller mistakenly gives you Y dollars and X cents for depositing an X-dollar-Y-cent check (X,Y less than 100); after losing 20 cents you still have with twice as much money as you should have had. What was the check amount (i.e. what are X and Y)?
• The distribution of primes -- that is, the natural but tantalizingly difficult quest for patterns in the sequence 2, 3, 5, 7, 11, 13, ... of prime numbers. [A measure of its difficulty is the problem's intimate connection with the Riemann Hypothesis, one of the mathematical problems on which the Clay Math Institute has placed a million-dollar bounty.]
• An inequality in solid geometry from an International Math Olympiad problem: tetrahedron ABCD has BC perpendicular to DC and the altitude from D meeting ABC in its orthocenter [the point where its three altitudes intersect]; prove that (AB + BC + CA)² ≤ 6 (AD² + BD² + CD²) . [Also: when if ever does equality hold -- that is, for which tetrahedra is (AB + BC + CA)² = 6 (AD² + BD² + CD²) ?]
• The Fibonacci numbers (see above), as the solution of Fibonacci's original rabbit puzzle
• Fermat's Last Theorem, finally solved centuries later by Wiles and Taylor
• A classic geometric optimization problem: enclose the largest possible rectangular area with a 100-meter fence along an existing long wall. This can be solved as a calculus exercise, but we'll see that calculus is not necessary and there's even a nice geometrical explanation of the answer.
• The problem of the Bridges of Königsberg, which led Euler to inaugurate combinatorial graph theory. (Note that this first example of a graph has multiple edges, which many modern treatments of graph theory regard as unorthodox.)
• A curious property of quartic graphs: if Q(x) is a quartic polynomial whose graph G: y=Q(x) has two inflection points, call them P₁ and P₂, then the line through P₁ and P₂ meets G again in two other points, say P₀ and P₃, with the ratio P₀P₁:P₁P₂:P₂P₃ always equal 1:φ:1 (where φ is the Golden Ratio (1+sqrt(5))/2 = 1.61803... as above). Bonus problem: each of the tangents to G at P₁ and P₂ meets G again in another point, call it R₁ and R₂ respectively; then the x-coordinates of R₂, P₁, P₂, R₁ (in that order) are in arithmetic progression, and the lines P₁R₁ and P₂R₂ divide each other in a 1:3 ratio.
• The classic dissection proof of the Pythagorean Theorem; the link is to a clip from the 1973 BBC documentary series The Ascent of Man where I think I first saw this dissection. Some justification is needed to complete the proof, which may be why this beautiful dissection is not the standard schoolbook argument. Likewise for the generalization of the dissection that illustrates the Law of Cosines (see the “cos1, cos2” item in my Mathematical Miscellany page).
• The “boy or girl paradox”, reminiscent of the Monty Hall problem: here too 1/2 is a popular intuitive guess for the probability, and 2/3 is the “correct” answer (for a different reason), though one must be even more careful to state the puzzle so that 2/3 is indeed correct.
• The P vs. NP problem (the link goes to the official description of the problem in the Clay Mathematics Institute's list of 7 math problems with million-dollar prizes).
• Age problems such as: dad is 10 times as old as his daugther; in six years he'll be four times as old as the same daughter; how old are they now? (Easy with simultaneous linear equations, not so easy when the puzzle is first encountered in third grade...)
• From a physics contest: weigh a meter stick using only a 100-gram weight. Put the weight on one end of the stick, and find the spot where the weighted stick balances; since it's a meter stick we can read off the distance in centimeters, call it d, to the heavy end, and then we have a balance with 100 grams at distance d from the fulcrum and the unknown weight in effect concentrated at distance 50-d, so it's 100d/(50-d). Note that this assumes that the meter stick's weight is distributed uniformly along its length, or at least that its center of mass is at the stick's midpoint. Can you modify this technique to find the weight regardless of its distribution?
• A pair of geometry problems involving the cube:
  i) Find the side-length of a cube located in space so that its shadow (i.e., its projection from (x,y,z) to (x,y)) is a regular hexagon of area 147*sqrt(3)/2.
  ii) Find the side-length of a cube that can be cut by a plane so that the cross-section is a regular hexagon of area 147*sqrt(3)/2.
  The surprise is that the cube will even accommodate regular hexagons with their 120-degree angles. This is a manifestation of the threefold symmetry of the cube that cyclically permutes its coordinates. Can you visualize the 3-dimensional shapes arising as the analogous shadow and cross-section of the 4-dimensional hypercube? (For example, the cross-section is the intersection of the cube [-1,1]⁴ with the hyperplane x₁+x₂+x₃+x₄=0; what does that look like?)
  
• A “related rates” problem from differential calculus.
• The so-called “Einstein's Challenge” puzzle, which likely has nothing to do with Einstein but is typical of the kind of logic puzzles that appear on LSAT's (Raymond Smullyan wrote several books full of such conundrums) and akin to Sudoku and its variants.
• Fortune's algorithm for efficiently computing the Voronoi diagram of a finite set of points in the Euclidean plane.
• The 3x+1 problem; utterly elementary to state, but might be hopeless to solve --- and here, unlike the situation for the Riemann Hypothesis and the other Clay-megabuck problems, the difficulty may not be that we do not yet understand the relevant mathematics but that there just isn't any structure from which to mount a successful attack.
• Computation of the derivative of a polynomial starting from the definition of the derivative, with massive cancellation and simplification compared with the fearsome-looking (f(x+h)-f(x))/h.
• Integration by parts, particularly cases like the integral of e^ax cos(bx) dx where after two steps we come back where we started but can still recover the integral by solving simultaneous linear equations.
• Buffon's needle (where 2/π arises naturally as a geometrical probability), and generalizations.
• A bijection between the natural numbers and the integers (1,2,3,4,5,6,7,... go to 0,1,-1,2,-2,3,-3,...), despite our intuition that the whole should be greater than its part (based on experience with finite sets). This is usually associated with Cantor's investigation of infinite cardinals, but was already observed by Galileo!
• “Two bikers, twenty miles apart, are playing chicken, both moving towards each other at a constant speed of 10 mph. A fly, zooming along at 15 mph, flies continuously from handlebar to handlebar. How far will the fly have flown when it gets squashed?” There's a routine though somewhat unpleasant solution via geometric series, but also an alternative approach that yields a nice and more elementary derivation. (This problem, or one with the same structure but a different story and parameters, also figures in a famous von Neumann anecdote.)
• The “Birthday Paradox”: it takes only a few dozen randomly chosen people, much less than most of us first expect, for the probability to be more than 50% that two of them will have the same birthday. A follow-up: the standard analysis assumes that all 365 birthdays (ignoring February 29) are equally likely. This is not true in real life. Show that for each n an unequal distribution of birthdays can only increase the probability that a random collection of n people includes two with the same birthday.
• An AIME problem (1994, #8): Find positive real numbers a,b such that the points (0,0), (a,11), and (b,37) are the vertices of an equilateral triangle. That's a nice illustration of the use of complex numbers or geometric transformations to solve problems in plane geometry. Another such example can be found in the light-blue background pattern for this page...
• The enumeration of derangements, permutations with no fixed points (i.e. permutations that send no object to itself); for large n, the probability that a random permutation of n objects is a derangement rapidly approaches 1/e = 36.787944...%. The Wikipedia article mentions various generalizations and variations; here is another: what is the probability that there is neither a fixed object nor a 2-cycle (a pair of objects switched with each other)?
• The “conditionally convergent” alternating sum 1 - 1/2 + 1/3 - 1/4 + - ..., which can easily be rearranged to have various other sums, and thus warns about arbitrary manipulation of infinite series. Indeed a conditionally convergent sum of real numbers can be rearranged to have any desired real sum!
• The Taylor series of an arbitrary (infinitely-differentiable) function [with some necessary provisos and warnings, as should be noted in any text that proves a precise statement on Taylor's theorem with remainder].
• The indefinite integral of sqrt(1+x²) dx, which has a solution in “closed form” but an unexpectedly complicated one.
• The “Pigeonhole Principle” (a.k.a. the Dirichlet box principle), which is not so much a problem or solution as a problem-solving technique that will surely figure in our seminar.
• The remarkable Catalan numbers (2n)! / (n!(n+1)!) = 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ... --- see for instance Richard Stanley's list of lots of “Exercises on Catalan and Related Numbers” from his magnum opus Enumerative Combinatorics (that page also links to the solutions of these exercises, and a “Catalan addendum” that as of July brings the number of combinatorial interpretations to 166).
• “Handshake problems” in graph theory, presumably including this classic one.
• What is the sum of the areas of all the rectangles in an m-by-n grid? This is not too hard to solve directly, but the nice form of the answer (the product of the binomial coefficients C(m+2,3) and C(n+2,3) ) suggests that there might also be an elegant combinatorial interpretation; can you find it?
• Euler's evaluation of 1 + 1/4 + 1/9 + 1/16 + 1/25 + ... = 1/1² + 1/2² + 1/3² + 1/4² + 1/5² + ... (a.k.a. ζ(2) or the “Basel problem”) as π²/6. (Euler also showed that for all even k>0 the value of ζ(k) is a rational multiple of π^k; the rational multiplier is closely related to the k-th Bernoulli number. For odd k>1 it is not expected that ζ(k)/π^k is rational, and indeed much less is known about the value of these ζ(k) values; for instance ζ(3) was proved irrational only in 1979 by Apéry, and none of the other odd zeta values has been proved irrational yet.)