Putnam and Beyond, 926. We play the coin tossing game in which if both tosses match, I get both coins; if they differ, you get both. You have m coins, I have n. What is the expected length of the game (i.e. number of tosses until one of us is wiped out)?
Putnam 1990/B4 Let be a finite group generated by and . Prove that there exists a sequence such that
- Every element occurs twice.
- or for . ()
Putnam 1990/B6 Let be a nonempty, closed, bounded, convex set in the plane. Let be a line and be a positive real. Let be the support lines for parallel to (i.e. they are the closest lines such that the entire figure is contained between them), and let be the line parallel to and midway between and . Let be the band of points whose distance from is at most , where is the distance between and . What is the smallest such that ?
Miklos Schweitzer, ? Suppose is continuous and
Let . Prove that
PaB 926. Let . Let be the expected length of the game when the players have and coins. Then . Note . Solving this recurrence gives .
P1990/B4 Consider the graph with group elements the vertices and with a directed edge going from to if or . Then each vertex has indegree 2 (vertices point to from ) and outdegree 2. The graph is connected because generate . Hence there exists an Euler cycle. Such a cycle goes through every vertex twice, so the ordering of the vertices gives the desired sequence.
P1990/B6 (Sketch) It is easy to verify that by considering the equilateral triangle. Take .
First suppose that every three sets of the form intersect. Since these are convex (and compact) sets, by Helly’s Theorem the intersection of all of these sets is nonempty. This intersection must intersect (otherwise, it can be shown that there exists a support line that doesn’t intersect ).
So suppose by way of contradiction that there exist three such sets with empty intersection. Take two of the bands. The support lines corresponding to them form a parallelogram with lengths three times the length of the parallelogram formed by the intersection of the two bands. The third band must intersect one of the main diagonals, say at some point. By considering the length of the segment of inside the band, both support lines must intersect the main diagonal at the same side of the midpoint of , say . But then this support line doesn’t intersect either or , a contradiction (draw the figure to see why).
MS Notice that , so
The lower bound is 0, since . We have
This is 0 if the numerator does not explode. Else using L’Hopital’s rule,
Hence both bounds in (1) are 0, and the integral equals 0.