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.$

Solutions

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.