Freshman Seminar 24i applicants' Essay 2 problems (Fall 2010)
(in roughly the order received, with some further comments):
1. 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)=π.] Euler's identity is proved as a special case of Euler's formula eix = cos(x) + i sin(x) [a.k.a. "cis(x)"], by comparing Taylor series or differential equations. 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).
2. Connnect a 3x3 array of 9 dots with an uninterrupted path of 4 straight line segments. [A famous example of literally “thinking outside the box”; I've also seen creative approaches to reducing the count of segments even below 4, by folding the paper, exploiting the thickness of physical dots and pen(cil)-points to make a Z-shaped path of not-quite-parallel line segments, and even using a writing implement with a really thick point to reduce the count to 1! Ignoring such cheats, how few segments does it take for an m-by-n array?]
3. Find a positive integer which doubles when its last digit is moved in front. [For example, if the problem said “quintuples” instead of “doubles” you could use 142857. Can you find more such numbers, whether for doubling, quintupling, or other multiples? Can you describe all the possibilities?]
4. Using the derivative of a function to find extrema, inflection points, etc. [we'll also see in the seminar how to find some extrema without calculus; these include some standard calculus examples as well as some that would be very hard to do with calculus techniques. To be sure there are also many max/min problems for which calculus provides the simplest if not the only solutions.]
5. Surface area integrals in Calculus BC
6. Mathematical problems arising in AP physics
7. 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.]
8. Cauchy's theorem in group theory [this is rather abstract compared with the kind of math we'll usually work with in 24i, but the technique is useful also in many more down-to-earth problem, such as one standard proof of (p-1)!≡1 mod p for all primes p (the harder part of Wilson's theorem in elementary number theory).]
9. An international society has 1978 members from six different countries. The members are numbered 1, 2, 3, …, 1978. Prove that there is at least one member whose number is the sum of the numbers of two (not necessarily distinct) members from his own country. [a tricky IMO problem that turns out to be part of Schur's theorem in Ramsey theory; this we will be able to do in 24i as an example of the “pigeonhole principle” and/or induction.]
10. A Calculus BC project: compute (without resorting to scales, graduated cylinders, and the like) the volume of an irregularly shaped Bundt cake.
11. A lemma on continued fractions: of two consecutive rational approximations pn/qn (n=i, i+1) to any real number x, at least one is within 1/(2(qn)2) of x.
12. A few of the problems that lead to the 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).
13. Evaluate the continued fraction 1+1/(1+1/(1+1/(1+…))). [This yields the unreasonably ubiqutious golden ratio φ = (1+sqrt(5))/2 = 1.61803…; it arises in one explanation of why φ is the “most irrational” number, in the sense of being farthest in a certain precise sense from any rational approximation — cf. the other continued-fraction problem above.]
14. Simplify this scary expression (which turns out to be an example of a “telescoping sum”).
15. The traveling salesman problem [besides modeling a real-world problem, this one is essentially equivalent to one of the million-dollar problems of the Clay Math Institute headquartered just outside Harvard Yard.
16. A memorable puzzler from 7th grade math: a hoop girding the Earth at its Equator expands by 10 feet, so it is now a constant height above the Equator (assumed to be a perfect circle — never mind that Quito is almost 3 kilometers above sea level, etc.). What is this height? [Surprisingly one doesn't need to know the size of the Earth for this. A follow-up that may be even more surprising: pull on a belt around the same idealized equator, again lengthening it by 10 feet, but this time concentrated at some point P on the Equtor, so that the belt now consists of two line segments AP, PB tangent to the Earth at the Equator, together with the long arc BA around the Equator. How far above the Equator is P? Here you will have to know the size of the Earth (the Equator is very nearly 40000 kilometers or 4⋅107 meters long, while 10 feet is about 3 meters), as well as some calculus at the level of Harvard's Math 1b.]
17. The Futurama mind-swapping theorem (about generating arbitrary permutations by certain simple transpositions).
18. Of the repeating decimal periods of the fractions 1/13=.076923…, 2/13=.153846…, 3/13=.230768…, etc. till 12/13=.923076…,, the six cyclic permutations of 1/13 occur precisely for n/13 where n is one of the “quadratic residues” 1, 3, 4, 9, 10, 12 of 13 (that is, one of the numbers that arises as a nonzero remainder mod 13 of a perfect square)! [This is somewhat related with the earlier comment regarding 142857.]
19. Equations like x - ¼ = x that irritatingly have no solutions. [Such equations are a part of the mathematical universe, and it's not usually worth being irritated by them, though on occasion important advances have been made by famously expanding that universe to include solutions of equations like x+5=3, 2x=1, and x2+1=0 that previously had no solution; even for x-¼=x it is sometimes right to say x=∞ is the (unique) solution.]
20. Zeno's “paradox of dichotomy”, which leads to the modern notions of limits and convergence
21. The "Monty Hall problem"; 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?]
22. Systems of simultaneously linear equations [a kind of problem which goes back literally millennia and which leads to the remarkably fruitful ideas of modern linear algebra]
23. Historical and still productive theorems, as of Euler (in calculus and elementary number theory) and Lagrange; the use of L'Hôpital's rule to evaluate limits
24. The “100 blue-eyed islanders” riddle [again an example of mathematical induction; see also the similar puzzle of the lions and the lamb, and this example of the family of “pirates' gold” puzzles]
25. Find two “primitive Pythagorean triples” (solutions of a2+b2=c2 in relatively prime natural numbers a,b,c) beyond the familiar (3,4,5) and the possibly less familiar (5,12,13). [A classical “Diophantine equation” (equation to be solved in integers). Can you generate infinitely many Pythagorean triples? All of them?]
26. Given 12 balls, all but one of the same weight, and an unmarked balance scale, determine in only three weighings which ball is different and whether it is lighter or heavier than the rest. [Can you prove that 12 is the maximal number for which this task can be accomplished with only three weighings? What if you can perform four, five, … n weighings?]
27. A recent problem from the AIME: In a parallelogram ABCD, point M is on AB such that AM/AB = 17/1000 and point N is on AD so that AN/AD = 17/2009. Let P be the point of intersection of AC and MN. Find AC/AP. [A good example of a problem in plane geometry that can be most easily solved with coordinates or vectors]
28. Trigonometry problems, and their reconsideration in calculus as with the limit of sin(x)/x as sin(x)→0 [which in effect goes back to the Greek method of approximating π using areas of inscribed and circumscribed regular polygons]
29. The “missing dollar” riddle