Posted by: holdenlee | September 19, 2010

B7s 9/18/2010

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 G be a finite group generated by a and b.  Prove that there exists a sequence g_1,\ldots, g_{2n}\in G such that

  1. Every element occurs twice.
  2. g_{i+1}=g_ia or g_ib for i=1,\ldots ,2n. (g_{2n+1}=g_1)

Putnam 1990/B6 Let S be a nonempty, closed, bounded, convex set in the plane. Let K be a line and t be a positive real. Let L_1,L_2 be the support lines for S parallel to K (i.e. they are the closest lines such that the entire figure is contained between them), and let L be the line parallel to K and midway between L_1 and L_2. Let B_S(K,t) be the band of points whose distance from L is at most \frac{tw}{2}, where w is the distance between L_1 and L_2. What is the smallest t such that S\cap \bigcap_K B_S(K,t)\neq 0?

Miklos Schweitzer, ? Suppose f is continuous and

\int_{0}^{\infty} f(x)^2dx<\infty.

Let g(x)=f(x)-2e^{-x}\int_0^x e^t f(t)dt. Prove that

\int_0^{\infty} g(x)^2dx=\int_0^{\infty} f(x)^2dx.


PaB 926. Let N=m+n. Let a_m be the expected length of the game when the players have m and N-m coins. Then a_m=1+\frac{a_{m-1}+a_{m+1}}{2}. Note a_0=a_n=0. Solving this recurrence gives a_m= m(N-m)=mn.

P1990/B4 Consider the graph with group elements the vertices and with a directed edge going from g to h if ga=h or gb=h. Then each vertex has indegree 2 (vertices point to g from ga^{-1},gb^{-1}) and outdegree 2. The graph is connected because a,b generate G. 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 t\geq \frac 13 by considering the equilateral triangle. Take t=\frac 13.

First suppose that every three sets of the form B_S(K,T) 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 S (otherwise, it can be shown that there exists a support line that doesn’t intersect S).

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 ABCD 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 AC at some point. By considering the length of the segment of AC inside the band, both support lines must intersect the main diagonal at the same side of the midpoint M of AC, say MC. But then this support line doesn’t intersect either AB or AD, a contradiction (draw the figure to see why).

MS Notice that g'(x)=f'(x)-g(x)-f(x), so

(1)\,\int_0^{\infty} (f+g)(f-g)dx=\int_0^{\infty} (f+g)(f'+g')dx=\int_{f(0)+g(0)}^{\lim_{x\to \infty} f(x)+g(x)} udu.

The lower bound is 0, \lim_{x\to \infty} f(x)=0 since \int_{0}^{\infty} f(x)^2dx<\infty. We have

\lim_{x\to \infty}g(x)=-\frac{2\int_0^x e^tf(t)dt}{e^x}.

This is 0 if the numerator does not explode. Else using L’Hopital’s rule,

\lim_{x\to \infty}g(x)=-\frac{2e^xf(x)}{e^x}=0.

Hence both bounds in (1) are 0, and the integral equals 0.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: