Freshman Seminar 24i applicants' Essay 2 problems (Fall 2009)
(in roughly the order received):
  1. Boss will pay employee 7 days' wages with a 7-unit bar of gold. Make only two cuts such that the employee can be paid one unit at the end of each day. [Never mind rule about extra pay for weekend work, nor the possibility that the worker might actually deposit or spend some of each day's payment before the next day comes around.] How many cuts for a 31-day month?
  2. The Fundamental Theorem of Calculus (the key link between differential and integral calculus, and a paradigm for many further developments, via Green's and Stokes' Theorem to modern differential geometry and beyond)
  3. Which is bigger: eπ or πe? (The answer turns out not to depend on the value of π provided it is a positive number other than e itself; the fact that π is reasonably close to e explains why eπ and πe are close enough that the answer is not immediately obvious.
  4. Euler's evaluation of 1 + 1/4 + 1/9 + 1/16 + 1/25 + ... = 1/12 + 1/22 + 1/32 + 1/42 + 1/52 + ... (a.k.a. ζ(2) or the “Basel problem”) as π2/6. Chosen by five applicants, one of whom also noted the connection with the probability 1/ζ(2)=6/π2 that two large random numbers be relatively prime (see also the first item on my collection of mathematical puzzles). [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.]
  5. Let ABCD be a regular tetrahedron and M, N points in the planes ABC, respectively ABD. Then CN, DM, MN are the lengths of the sides of a (possibly degenerate) triangle. Solution: Let E be such that ABCDE is a regular simplex in 4-space! By symmetry, CN=EN and DM=EM, so CN, DM, MN are the side-lengths of EMN. (Suggested by the analogous problem for a regular triangle and its solution via a regular tetrahedron)
  6. Find the optimal strategy for Stacks: two players alternately remove 1, 2, or 3 counters from a single stack; the player forced to remove the last counter loses. (Variations and generalizations: What if the last player wins instead or losing? What if you can remove anywhere from 1 to n counters at each turn? Suppose there are 2 stacks, and each player must play in that player's choice of stack. Try three or more stacks, perhaps allowing each player to take an unrestricted (but still positive) number of counters from a single stack. This last is the game of Nim, and all these games are important special cases of the combinatorial game theory systematized by Berlekamp, Conway, and Guy in Winning Ways.
  7. The intriguing and infinitely complicated Mandelbrot set in the complex plane
  8. The trick for squaring numbers near 50 (between 41 and 59, in fact), explained by the formula (50+n)2 = 2500 + 100n + n2. For example, if n=-3 we find that 472 is 2209, with the first two digits being 25-3 and the last two being 32; similarly if n=6 then write 25+6=31 followed by 62=36 to get 562=3136. (There's a similar rule for squaring numbers near 100, or numbers whose last digit is 5.)
  9. The rule for divisibility by 3 or 9: a number is divisible by 3 or 9 if and only if the sum of its digits is. (For instance 2+4=6 is a multiple of 3 but not of 9, so 24 and 42 are divisible by 3 but not by 9.) This is the basis of the old technique of casting out nines to (partly) check one's arithmetic, as well as more recent puzzles and arithmetical magic tricks such as guessing a missing digit in a multiple of 872.
  10. Heron's formula for the area of a triangle as a function of its sides, and the proof via the Law of Cosines; see also this Wikipage for more information and some remarkable generalizations and variations.
  11. The liar paradox, "This statement is false" (not originally mathematical, but related with some important mathematical ideas such as Cantor's proof of the uncountability of the real numbers (see below) and Gödel's incompleteness theorems)
  12. Euler's formula eix = cos(x) + i sin(x) [a.k.a. "cis(x)"], and its proof via Taylor series. This link between the exponential and trigonometric functions is a key building block of the mathematical universe, and we shall see that it also gives some very useful problem-solving tools -- for starters it encapsulates most of the important trig identities (e.g. compare real and imaginary parts in eix eiy = eix+iy = ei(x+y) [a.k.a. cis(x) cis(y) = cis(x+y)] to recover the formulas for cos(x+y) and sin(x+y) respectively).
    Another student chose the special case x=π, which gives rise to Euler's celebrated identity eiπ+1=0; this is the key to De Morgan's quote
    Imagine a person with a gift of ridicule ... [He might say] First that a negative quantity has no logarithm; secondly that a negative quantity has no square root; thirdly that the first non-existent is to the second as the circumference of a circle is to the diameter. (A Budget of Paradoxes, 319--320)
    which unwraps to log(sqrt(-1))/sqrt(-1)=π.
  13. An inequality problem: if a,b,c are positive real numbers such that a2 + b2 + c2 + 2abc = 1, prove that 2(ab+bc+ca) ≤ 1 + 4abc. (We'll develop some techniques for proving inequalities in 24i, but probably none as tricky as this olympiad problem.)
  14. Related rates problems in differential calculus
  15. Pascal's triangle (actually discovered in Europe some time before Pascal, several centuries earlier in China and Iran -- the latter in time to be studied by Omar Khayyam! -- and possibly more than 1000 years before that in India). We shall surely study and make use of it at several points in the seminar.
  16. The Four-color theorem, whose proof in 1976 by Appel and Haken (over a century after the problem was posed) was the first major theorem whose proof required (and still requires) computer assistance.
  17. The Hadwiger-Nelson problem; the bounds "between 4 and 7 inclusive" were noticed almost as soon as Martin Gardner published and popularized the question almost 50 years ago, and no progress has been made since then!
  18. Goldbach's conjecture, which though easy to state (every even number other than 2 is the sum of two primes) remains intractable 250+ years later.
  19. Noether's Theorem in mathematical physics, a fundamental and unexpected connetion between continuous symmetries and conservation laws
  20. The route inspection problem (a.k.a. "Chinese Postman Problem") in computational graph theory (cf. also the Bridges of Königsberg problem below)
  21. An inequality problem from the 2009 USA Math Olympiad: if a1, a2, ..., an (some n>1) are positive real numbers such that (a1 + a2 + ... + an) (1/a1 + 1/a2 + ... + 1/an) = (n+(1/2))2, prove that the ratio between the largest and the smallest of a1, a2, ..., an is at most 4. [This we will be able to do -- and without calculus -- using techniques we'll learn in the seminar. Can you find a1, a2, ..., an satisfying the above condition for which the largest is exactly 4 times the smallest?]
  22. A practical physics problem that leads to integral and differential calculus: where in a simply supported beam is the bending moment maximized?
  23. A plane geometry problem from the AIME II exam in 2009: If ABCD is a rectangle whose diagonal AC is perpendicular to the line joining B to the midpoint of AD, find the rectangle's aspect ratio AD/AB. [The actual AIME problem specified AB=100 and asked for the greatest integer less than AD, because AIME answers must be 3-digit numbers.] The solution using similar triangles recalls the ISO 216 system of international paper sizes A4, A5, etc., which have the same aspect ratio so that each can be made from two of the next-smallest size.
  24. Euclid's proof that there are infinitely many prime numbers (chosen by three applicants; a veritable classic, and one I'm particularly fond of because I was fortunate to find a new use of the idea as one ingredient of the main result of my own doctoral thesis)
  25. Zeno's paradox of Achilles and the tortoise, and its resolution via the structure of real numbers, functions, limits and convergence, etc. as explored in modern calculus
  26. 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.
  27. The "Monty Hall problem", chosen by three applicants; curiously it seems that Monty Hall himself was not aware either of the controversy or of the fact that switching offered a clear advantage, until a statistician asked him about it only a few years ago! (I also just learned that he shares my birthday, albeit 45 years earlier; NB that's not an example of the "birthday paradox" -- do you see why? How long a list of random birthdays must I go through before I have a better than 50% chance of finding somebody else with the same birthday as me?)
  28. The "butterfly theorem" in plane geometry
  29. "Soddy spheres": the spheres S tangent to each of three fixed pairwise tangent spheres A, B, C, and in particular the locus of the center of S. This is a nice application of three-dimensional inversive geometry; see also the remarkable "Soddy's hexlet", a ring of six such spheres S each also tangent to the next and previous sphere in the ring (which is possible for any initial choice of A, B, C, and S!).
  30. The "Tower of Hanoi", a classic example of recursion (or induction) and exponential growth, and also still a rich source of new connections and of interesting and sometimes very hard further problems. The puzzle is not quite as old (or as exotic) as the name suggests; indeed the booklet that introduced the problem in 1889 still survives. Note that "Claus" is an anagram of Lucas -- yes, the same mathematician for whom the Lucas numbers are named, and who obtained the Lucas test for primality of Mersenne numbers 2p-1. The Wikipedia page for Lucas notes that indeed the entire name "N.Claus de Siam" anagrams to "Lucas d'Amiens", so it would seem that the association of the puzzle with that part of the world, and the fanciful mythical elaborations suggested by that exotic setting, are an accident of wordplay.
  31. The proof that 0.999999...=1 by computing that if x is the value of the repeating decimal 0.999999... then 10x - x simplifies to 9. This is a special case of the general procedure for evaluating infinite repeating decimals, and in turn generalizes to the formula for the sum of a convergent geometric series, which as noted above is also at the root of "Zeno's paradox".
  32. If each point of a circle is colored red or green then there is a monochromatic isosceles triangle (that is, three points on the circle form an isosceles triangle and are either all red or all green). This is an introductory case of geometric Ramsey theory; more generally, for any finite m and n, and any positive θ however small, it is true that if each point of a θ-degree arc is assigned one of m colors then there is an evenly spaced monochromatic sequence of n spaced points. (The original problem is the case (m,n)=(2,3) and θ=360.) Can you show that it is not true that for any red/green coloring there must be a monochromatic acute triangle? [NB a "circle" is always the set of points at fixed distance from the center, not the disc enclosed by that circle.]
  33. A collection of humans and horses has 74 heads and 196 legs (and no amputees, let alone multiple-headed mutants). How many creatures of each type are there? [A familiar kind of puzzle that can be found as early as ancient Chinese manuscripts, and is now recognized as a system of simultaneous linear equations and a precursor of linear algebra.]
  34. Stewart's theorem in triangle geometry, a staple of high-school math contests usually proved using the Law of Cosines and often remembered with the mnemonic recited at that artofproblemsolving.com page.
  35. An AHSME problem (1996 #29): if n is a positive integer such that 2n has 28 positive divisors and 3n has 30 positive divisors, how many divisors does 6n have? [And can you determine n itself? Note that 1 is considered a divisor of any integer x, as is x itself.]
  36. How many squares are there in an n-by-n grid? Note that this includes not just the n2 unit squares in the grid but also (n-1)2 2x2 squares, (n-2)2 3x3's, and so forth until we reach the single n-by-n square itself. The proof of the "closed form" for the resulting sum 12 + 22 + 32 + ... + n2 is a classic example of Mathematical induction, and the specific polynomial of n that arises is in essence the third Bernoulli polynomial (in general p-th powers yield the Bernoulli polynomial of degree p+1).
  37. The solution of Rubik's cube. The Cube is a remarkably fertile source of illustrations of key concepts in group theory and combinatorics, and there are actually numerous solution methods, some of which rely on aspects of this theory. This is reminiscent of the late 19th century craze for the Fifteen puzzle; years ago I had a plastic 15-puzzle, but the puzzle is nowadays much better known as an onscreen game or screen saver than a physical device.
  38. The numerical computation of π, which is the topic of another Freshman seminar this term, and whose history traces some important developments in theoretical and computational mathematics through the ages.
  39. A tricky calculus problem: A unicorn is tethered to a magician's tower by a silver chain. The radius of the tower is 10 feet, and the chain has a length of 10 feet. The chain is attached to the tower at the same height as the neck of the unicorn such that the chain is level. What is the area that the unicorn can walk around? (The shape is an example of an involute, namely the involute of a circle, and the area can be obtained using an integral formula for the area enclosed by a parametric curve.)
  40. The proof, using field theory, of the impossibility of trisecting a general angle using the classical Euclidean tools of straightedge and compass. This both settled one of the great open problems of antiquity and pointed the way to Galois theory and beyond. In particular there is no Euclidean construction of a regular 9-gon, but if we augment the Euclidean arsenal with an angle-trisecting device then we can construct not just a regular 9-gon but also (much less obviously) the regular heptagon, 13- and 19-gon, and probably infinitely others of prime order; see the article "Angle trisection, the heptagon, and the triskaidecagon" by my late colleague Andrew Gleason (Amer. Math. Monthly 95 (1988) #3, 185-194), cited in the Wikipedia page on Euclidean constructions.
  41. Cantor's argument for the uncountability of the real numbers; the result is not just important in itself, but also introduced a proof technique (prefigured by the "Liar paradox", see above) that has found much use since, from the recreational (the "barber paradox" etc.) to Gödel's theorem and contemporary mathematical research. [The uncountability was apparently surprising even to Cantor himself, who had set out to prove that all infinite sets are countable and proved it for sets like the points in space each of whose three coordinates is rational; this is itself surprising at first, because the set looks much bigger than the integers, which are a discrete subset of a 1-dimensional line, and the observation that an infinite set can be put in bijection with a "much smaller" one, and thus has the same cardinality, can be found already in Galileo's Dialogues -- yes, the same Galileo.]
  42. The game of chess, considered as a source of mathematical problems (which was the topic of the Freshman seminar I taught from 2003 to 2006)
  43. The Coupon collector's problem, in a Harry Potter guise: if there are 20 different Chocolate Frog cards, and each card is equally likely to appear in a Chocolate Frog package (one card per package), how many packages, on average, will a collector have to purchase to collect all the cards?
  44. What is the value of sqrt(6 + sqrt(6 + sqrt(6 + sqrt( ... )))) -- and why is it 3 rather than the other solution -2 of x2 - x = 6 ? (This second part again draws us to matters of sequences, convergence, limits, etc.)
  45. Fermat's Last Theorem, finally solved centuries later by Wiles and Taylor
  46. How many possible knots in a camp counselor's ice-breaker game ("Close your eyes. Reach your hands in. Grab someone else's. Now untangle yourselves!") A probably intractable (or should I write, too knotty...) problem in knot theory, which however is suggestive of some recent constructions of knot invariants.
  47. The Riemann Hypothesis, one of the mathematical problems on which the Clay Math Institute has placed a million-dollar bounty, and a problem known to be intimately related with 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.
  48. 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.)
  49. A calculus optimization problem (somewhat akin to the kind of inequality problems we'll learn to solve without calculus): Determine the dimensions of the box of the largest volume that can be constructed from a rectangular sheet of cardboard of length 48" and width 36", according to one of the figures at this site of mathematical demos
  50. How many points in the plane does it take to uniquely define a second-degree equation (geometrically, a conic section or union of two lines)? 5, by linear algebra; not 4, proved visually by intersecting two ellipses in four points. This is a prototype of several important problems techniques in modern algebraic geometry; many similar problems with more points and higher dimensions or degrees remain tantalizingly unsolved.
  51. Finding the sum of the areas of the circles in the Pappus chain (related with two topics already mentioned: inversive geometry, and the value of ζ(4))
  52. A combinatorial enumeration problem: How many ways are there to color the twelve sides of a dodecahedron one of five colors such that no two adjacent faces are painted the same color? (An example of evaluating chromatic polynomials, and also of "Burnside's lemma" if symmetries are to be taken into account)
  53. The mathematics of repeated perfect shuffles of n cards (which correspond to doubling modulo n+1 or n-1 depending on whether one shuffles "in" or "out")
  54. The dangerous crossing puzzle, an example of a problem that can also be regarded as part of operations research or combinatorial optimization, and has a solution often felt to be counterintuitive
  55. Another combinatorial game problem, said to be a common question at job interviews for finance companies. 50 coins are arranged in a row; the coins have arbitrary values. Two players (who know these arbitrary values) alternate play, at each turn taking either the first or the last of the remaining coins, each player aiming to end up with 25 coins whose total value is larger than the opponent's total. Which player has a winning (or at least non-losing) strategy?