Putnam problems by Richard Stanley
With my original solutions :)
By Vamshi Jandhyala in mathematics problem solving
April 13, 2020
Problem 1
Given that
$$ \begin{align*} \int_0^1 \frac{log(1+x)}{x} dx &= \frac{\pi^2}{12} \end{align*} $$
Evaluate
$$ \begin{align*} \int_0^1 \int_0^y \frac{log(1+x)}{x} dx dy \end{align*} $$
Solution
We note that
$$ \begin{align*} \frac{1}{1+x} = 1-x+x^2-x^3+ \dots \end{align*} $$
Integrating both sides we get
$$ \begin{align} log(1+x) &= x-\frac{x^2}{2}+\frac{x^3}{3} + \dots \label{eq:ser_exp1} \end{align} $$
From the above, we also have
$$
\begin{align}
\int_0^y \frac{log(1+x)}{x} dx &= y - \frac{y^2}{2^2}+\frac{y^3}{3^2} + \dots \label{eq:ser_exp2} \\
\implies \int_0^1 \frac{log(1+x)}{x} dx &= 1 - \frac{1}{2^2}+\frac{1}{3^2} + \dots = \frac{\pi^2}{12} \label{eq:intval}
\end{align}
$$
Integrating \ref{eq:ser_exp2} we get
$$
\begin{align}
\int_0^1 \int_0^y \frac{log(1+x)}{x} dx dy &= \frac{1}{2 \cdot 1^2} - \frac{1}{3 \cdot 2^2}+\frac{1}{4 \cdot 3^2} + \dots \nonumber \\
&= 1 - \frac{1}{2} - \frac{1}{2}\left(\frac{1}{2} - \frac{1}{3} \right) + \frac{1}{3}\left(\frac{1}{3} - \frac{1}{4} \right) + \dots \nonumber\\
& = 1 - \frac{1}{2^2}+\frac{1}{3^2} - \dots - \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} - \frac{1}{3 \cdot 4} \dots \label{eq:req_exp}
\end{align}
$$
Integrating \ref{eq:ser_exp1} we get
$$ \begin{align} \label{eq:log1+x_exp} \int_0^1 log(1+x) dx = log(4) -1 = \frac{1}{1 \cdot 2} -\frac{1}{2 \cdot 3 }+\frac{1}{3 \cdot 4} + \dots \end{align} $$
From \ref{eq:intval},\ref{eq:req_exp} and \ref{eq:log1+x_exp}, we have
$$ \begin{align*} \int_0^1 \int_0^y \frac{log(1+x)}{x} dx dy = \frac{\pi^2}{12} - log(4) + 1 \end{align*} $$
Problem 2
Let $C$ be a circle of radius $1$, and let $D$ be a diameter of $C$. Let $P$ be the set of all points inside or on $C$ such that $p$ is closer to $D$ than it is to the circumference of $C$. Find a rational number $r$ such that the area of $P$ is $r$.
Solution
Let $U(x,y)$ be a point inside the circle.
In the diagram, 
we can see that $E$ is the point on $C$ nearest to $U$ as $OU + UH > OU + UE = 1$.
The distance of $U$ from the diameter $D$ is give by $y$.
The minimum distance of $U$ from $C$ is given by $1 - \sqrt{x^2+y^2}$.
For $U$ to be closer to $D$ than $C$, we have
$$
\begin{align*}
1 - \sqrt{x^2+y^2} > y \\
\implies y^2 + 1 - 2y > x^2+y^2 \\
\implies y < \frac{1-x^2}{2}
\end{align*}
$$
The area $r$ is given by
$$ \begin{align*} r = 2 \int_{-1}^1 \frac{1-x^2}{2} dx = 2 - \frac{2}{3} = \frac{4}{3} \end{align*} $$
Problem 3
Let
$$ \begin{align*} S = \sum \frac{1}{m^2n^2} \end{align*} $$
where the sum ranges over all pairs $(m, n)$ of positive integers such that the largest power of $2$ dividing $m$ is different from the largest power of $2$ dividing $n$. Express $S$ in the form $\alpha \pi^k$, where $k$ is an integer and $\alpha$ is rational. You may assume the formula
$$ \begin{align} \sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6} \label{eq:basel} \end{align} $$
Solution
We have
$$ \begin{align} S = \sum \frac{1}{m^2n^2} = \sum_{\text{$u,v$ are odd}} \frac{1}{u^2v^2} \left( \sum_{i,j=0;i \neq j}^{\infty} \frac{1}{2^{2i}2^{2j}} \right) \end{align} $$
From \ref{eq:basel}, we have
$$
\begin{align}
\sum_{n=1}^{\infty} \frac{1}{n^2} &= \sum_{n=1}^{\infty} \frac{1}{(2n)^2} + \sum_{n=1}^{\infty} \frac{1}{(2n-1)^2} \nonumber\
\implies \sum_{n=1}^{\infty} \frac{1}{(2n-1)^2} &= \sum_{n=1}^{\infty} \frac{1}{n^2} - \frac{1}{4} \sum_{n=1}^{\infty} \frac{1}{n^2} \nonumber \ &= \frac{3}{4} \cdot \frac{\pi^2}{6} = \frac{\pi^2}{8}
\end{align}
$$
We now have,
$$ \begin{align} \sum_{\text{$u,v$ are odd}} \frac{1}{u^2v^2} = \left(\sum_{\text{$u$ is odd}} \frac{1}{u^2} \right) \left( \sum_{\text{$v$ is odd}} \frac{1}{v^2} \right) = \left( \frac{\pi^2}{8} \right)^2 = \frac{\pi^4}{64} \end{align} $$
We also have
$$ \begin{align} \sum_{i,j=0;i\neq j} \frac{1}{2^{2i}2^{2j}} = \left( \sum_{i=0}^{\infty} \frac{1}{4^i} \right)^2 - \sum_{i=0}^{\infty} \frac{1}{(4^i)^2}= \left( \frac{1}{1 - \frac{1}{4}} \right)^2 - \frac{1}{1- \frac{1}{16}} = \frac{16}{9} - \frac{16}{15} = \frac{32}{45} \end{align} $$
Therefore,
$$ \begin{align} S = \sum \frac{1}{m^2n^2} = \frac{\pi^4}{64} \cdot \frac{32}{45} = \frac{\pi^4}{90} \end{align} $$
Computational Verification
from math import pi
def highestPowerOf2(n):
return (n & (~(n - 1)))
s = 0
for m in range(1, 100000):
for n in range(1, 100000):
if highestPowerOf2(m) != highestPowerOf2(n):
s += 1/(m**2*n**2)
print(s, pi**4/90)
1.082304413401373 1.082323233711138
Problem 4
$$ \newcommand\EE{\mathbb E} \newcommand\PP{\mathbb P} $$
Choose two points $p$ and $q$ independently and uniformly from the square $0 \leq x \leq 1, 0 \leq y \leq 1$ in the $(x, y)$-plane. What is the probability that there exists a circle $C$ contained entirely within the first quadrant $x \geq 0, y \geq 0$ such that $C$ contains $x$ and $y$ in its interior? Express your answer in the form $1 - (a + b\pi)(c + d \sqrt{e})$ for rational numbers $a, b, c,d, e$.
Solution (Credit: Vaibhav Mehrotra)
First Observation
We observe that for any circle within the first quadrant with center $(s,t)$, we can find a second circle with center $(max(s,t), max(s,t))$ on the line $x=y$ with radius $max(s,t)$ that is tangent to the $x$ and $y$ axes and contains the first circle in its interior. So we only need to consider circles in the first quadrant which are tangent to the $x$ and $y$ axes.
Second Observation
Every point $(x_1,y_1)$ in the unit square $0 \leq x \leq 1, 0 \leq y \leq 1$ lies inside a number of circles tangent to both the axes. The union of the areas of all the circles determines the region where the second point $(x_2,y_2)$ can lie so that the line segment $(x_1, y_1), (x_2,y_2)$ is within a circle tangent to both the axes.
Let $C(x_1,y_1)$ be the set of all circles which are tangent to both the axes that contain the point $(x_1,y_1)$. Let $R(x_1,y_1)$ be the set of the radii of all the circles in $C(x_1,y_1)$.
Any circle in $C$ is given by $(x-c)^2+(y-c)^2= c^2$.
As $(x_1, y_1)$ lies inside all the circles of $C$, we have
$$
\begin{align*}
(x_1-c)^2+(y_1-c)^2 & \leq c^2 \\
\implies c^2 - 2(x_1+y_1) + x_1^2 + y_1^2 &\leq 0 \\
\implies x_1+y_1-\sqrt{2x_1y_1} \leq c & \leq x_1+y_1+\sqrt{2x_1y_1}
\end{align*}
$$
This gives us the radius of the smallest circle and largest circle in $C$ that contains point $(x_1,y_1)$ as
$$
\begin{align*}
r_S(x_1,y_1) &= x_1+y_1-\sqrt{2x_1y_1} \\
r_L(x_1,y_1) &= x_1+y_1+\sqrt{2x_1y_1}
\end{align*}
$$
Third Observation
For two points $(x_1,y_1)$ and $(x_2,y_2)$, we have a circle fully in the first quadrant with radius $r>0$ tangent to both the axes if
$$
\begin{align*}
r_S(x_1,y_1) & \leq r \leq r_L(x_1,y_1) \\
r_S(x_2,y_2) & \leq r \leq r_L(x_2,y_2)
\end{align*}
$$
This is possible only when
$$
\begin{align*}
r_S(x_1,y_1) & \leq r_L(x_2,y_2) \\
r_S(x_2,y_2) & \leq r_L(x_1,y_1)
\end{align*}
$$
The above conditions can be compactly written as
$$ \begin{align*} |x_1 + y_1 - x_2 - y_2| \leq \sqrt{2x_1y_1} + \sqrt{2x_2y_2} \end{align*} $$
This gives us an easy way to run a simulation to estimate the probability.
Probability calculation
The probability of the event $A$ where given $(x_1, y_1)$ there is another random point $(x,y)$ in the square that lies inside a circle fully in the first quadrant is given by
$$
\begin{align*}
\PP[A \vert (x_1,y_1)] &= \frac{\lvert{(x,y) \vert r_s(x_1,y_1) \leq r_L(x,y) \wedge r_S(x,y) \leq r_L(x_1,y_1), \text{$(x,y) \in S$}}\rvert}{\lvert S \rvert} \\
&= 1 - \frac{\lvert {(x,y) \vert r_L(x_1,y_1) < r_S(x,y) \lor r_S(x_1,y_1) > r_L(x,y) , \text{$(x,y) \in S$}} \rvert}{\lvert S \rvert}
\end{align*}
$$
where $S={(x,y)\vert 0 \leq x \leq 1, 0 \leq y \leq 1}$.
The area of $S$, $\vert S \vert=1$. The joint density function $f(x_1, y_1) = \frac{1}{\vert S \vert} = 1$.
We have
$$
\begin{align*}
\PP[A] &= \int_0^1 \int_0^1 \PP[A|(x_1,y_1)]\cdot f(x_1,y_1) dx_1dy_1 \\
&= \int_0^1 \int_0^1 \left(1 - 2 \cdot (1- \frac{\pi}{4}) r_S(x_1,y_1)^2 \right) dx_1dy_1 \\
&= 1 - 2\cdot(1- \frac{\pi}{4}) \int_0^1 \int_0^1 x_1^2 + y_1^2 + 4x_1y_1 - 2(x_1+y_1)\sqrt{2x_1y_1} dx_1dy_1 \\
&= 1 - 2\cdot(1- \frac{\pi}{4}) \int_0^1 \frac{1}{3} + y_1^2 + 2y_1 - 2\sqrt{2y_1}\left(\frac{2}{5} + \frac{2y_1}{3}\right) dy_1 \\
& = 1 - 2\cdot(1- \frac{\pi}{4}) \left( \frac{1}{3} + \frac{1}{3} + 1 - 2\sqrt{2} \left(\frac{4}{15} + \frac{4}{15}\right) \right) \\
& = 1 - 2\cdot(1- \frac{\pi}{4}) \frac{(25-16\sqrt{2})}{15} = 0.9321
\end{align*}
$$
Explanation of probability calculation
To calculate the area of the region ${(x,y) \vert r_S(x_1,y_1) > r_L(x,y) , \text{(x,y) in S}}$, we need to look at the area between the $x$ and $y$ axes and the circle $(x_1 - r_S(x_1,y_1))^2 + (y_1 - r_S(x_1,y_1))^2 = r_S(x_1,y_1)^2$. This is given by
$$ \begin{align*} r_S(x_1,y_1)^2 - \frac{\pi}{4}r_S(x_1,y_1)^2 = (1- \frac{\pi}{4})r_S(x_1,y_1)^2 \end{align*} $$
When $(x_1,y_1)$ varies over $S$ in the integral, the area in the bottom left corner outside of the circle with center at $(r_S(x,y), r_S(x,y))$ and radius $r_S(x,y)$ is counted twice, so we have
$$ \begin{align*} \lvert {(x,y) \vert r_L(x_1,y_1) < r_S(x,y) \lor r_S(x_1,y_1) > r_L(x,y) , \text{$(x,y)\in S$}} \rvert = 2 \lvert {(x,y) \vert r_S(x_1,y_1) > r_L(x,y) , \text{$(x,y) \in S$}} \rvert \end{align*} $$
Simulation
Algorithm
- Generate $4$ random numbers $x_1,y_1,x_2,y_2$ between $0$ and $1$, $n$ times.
- Count the number of times the condition $\lvert x_1 + y_1 - x_2 - y_2 \rvert \leq \sqrt{2x_1y_1} + \sqrt{2x_2y_2}$ is satisfied.
Code and Results
from random import random
from math import sqrt
runs = 1000000
s = 0
for _ in range(runs):
x1, y1, x2, y2 = random(), random(), random(), random()
if abs(x1 + y1 - x2 - y2) <= sqrt(2)*(sqrt(x1*y1) + sqrt(x2*y2)):
s += 1
print(s/runs)
This gives us a probability of 0.93225.
Problem 5
$$ \nonumber \newcommand\EE{\mathbb E} \newcommand\PP{\mathbb P} $$
Let $0 \leq x \leq 1$. Let the binary expansion of $x$ be
$$ \begin{align*} x = a_12^{-1} + a_22^{-2} + \dots \end{align*} $$
(where, say, we never choose the expansion ending in infinitely many 1’s). Define
$$ \begin{align*} f(x) = a_13^{-1} + a_23^{-2} + \dots \end{align*} $$
In other words, write $x$ in binary and read $x$ in ternary. Evaluate $\int_0^1 f(x)dx$.
Solution
Each $a_i$ can be treated as a random variable which takes the values ${0,1}$ with a probability $0.5$.
Therefore,
$$ \begin{align*} \int_0^1 f(x) dx = \EE[f(x)] = \EE[a] \left( \frac{1}{3} + \frac{1}{3^2} + \dots \right) = \frac{1}{2} \cdot \frac{\frac{1}{3}}{1-\frac{1}{3}} = \frac{1}{4} \end{align*} $$
Computational verification
from random import choices
runs = 1000000
s = 0
for _ in range(runs):
coeffs = choices([0, 1], weights=[0.5, 0.5], k=50)
s += sum([a/3**(i+1) for i, a in enumerate(coeffs)])
print(s/runs)
Problem 6
A $2×3$ rectangle has vertices at $(0, 0), (2, 0), (0, 3)$, and $(2, 3)$. It rotates $90 °$ clockwise about the point $(2, 0)$. It then rotates 90◦ clockwise about the point $(5, 0)$, then $90 °$ clockwise about the point $(7, 0)$, and finally, $90 °$ clockwise about the point $(10, 0)$. (The side originally on the x-axis is now back on the x-axis.) Find the area of the region above the x-axis and below the curve traced out by the point whose initial position is $(1, 1)$.
Solution
Here is the diagram showing how the Point $E(1,1)$ moves as the rectangle rotates 
It is easy to see that the required area is
$$ 2 \left(\frac{\pi}{4} \left((1^2 + 1^2) + (2^2 + 1^2)\right) + 2 (\frac{1}{2} \cdot 1 \cdot 1 + \frac{1}{2} \cdot 1 \cdot 2)\right) = 3.5 \pi + 6. $$
Problem 7
Two real numbers $x$ and $y$ are chosen at random in the interval $(0,1)$ with respect to the uniform distribution. What is the probability that the closest integer to $x/y$ is even? Express the answer in the form $r + s \pi$, where $r$ and $s$ are rational numbers.
Solution
I am proud of this solution to a Putnam problem which is compeletely original :-).
We are given that $$X,Y \sim \mathcal{U}[0,1]$$
Let $Z = X/Y$.
When $0 \leq z \leq 1$, $\mathbb{P}[Z \leq z]$ is the area of the green region in the figure below: 
When $1 \leq z$, $\mathbb{P}[Z \leq z]$ is the area of the green region in the figure below: 
We have
$$
\begin{align}
\mathbb{P}[Z \leq z] &=& \frac{z}{2} \text{ for } 0 \leq z \leq 1 \\
\mathbb{P}[Z \leq z] &=& 1 - \frac{1}{2z} \text{ for } 1 \leq z < ∞
\end{align}
$$
Therefore the required probability is given by,
$$
\begin{align*}
& \mathbb{P}[Z \leq 0.5] + \sum_{k=1}^\infty \mathbb{P}[2k - \frac{1}{2} \leq Z \leq 2k + \frac{1}{2}] \\
&= \frac{1}{4} + \sum_{k=1}^\infty \frac{2}{16 k^2-1} \\
&= \frac{1}{4} + \frac{1}{3} - \frac{1}{5} + \frac{1}{7} - \frac{1}{9} + \dots\\
&= \frac{1}{4} + 1 - \frac{\pi}{4} = \frac{5-\pi}{4}
\end{align*}
$$
Sum of the series $\frac{1}{3} - \frac{1}{5} + \frac{1}{7} - \frac{1}{9} + \dots$
Let $S(x) = \frac{x^3}{3} - \frac{x^5}{5} + \frac{x^7}{7} - \frac{x^9}{9} + \dots$.
We have $\frac{1}{3} - \frac{1}{5} + \frac{1}{7} - \frac{1}{9} + \dots = S(1)$.
We can see that
$$
\begin{align*}
S(x) &= \int_0^1 x^2 - x^4 + x^6 - x^8 + \cdots dx = \int_0^1 \frac{x^2}{1 + x^2} dx \\
&= \int_0^1 1 - \frac{1}{1 + x^2} dx = 1- {\tan}^{-1}(1) = 1 - \frac{\pi}{4}
\end{align*}
$$
Computational Verification
from random import random
from math import pi
runs = 1000000
tot_succ = 0
for _ in range(runs):
x, y = uniform(0, 1), uniform(0, 1)
if round(x/y) % 2 == 0:
tot_succ += 1
print(tot_succ/runs, (5-pi)/4)