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, circle

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

  1. Generate $4$ random numbers $x_1,y_1,x_2,y_2$ between $0$ and $1$, $n$ times.
  2. 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)

References

Richard Stanley’s Putnam Problems