Hey everyone,

The question I'm working on is Question A4 from the 2015 Putnam Exam. I've written up my solution below—while I did end up getting the right answer ($L = \frac{4}{7}$), my proof is pretty long-winded and some parts are a bit messy.

I'm trying to figure out what score this would get on the actual Putnam, but I haven't been able to find any specific grading rubrics or resources that break down how Putnam solutions are scored. Would anyone happen to have access to such resources, or be willing to look through my somewhat convoluted proof to give me an idea of what score it might earn? Thanks so much in advance!

(Also sorry for the rough formatting—I'm still new to LaTeX!)

Solution: #

We conclude $L = \frac{4}{7}$.

First, consider comparing the sums:
$$\sum_{n\in A}\frac{1}{2^{n}} \quad \text{vs} \quad \sum_{n\in B}\frac{1}{2^{n}}$$
where $A, B \subset \mathbb{Z}^{+}$. To compare these sums, it suffices to check elements starting from $n=1$ and find the first element $m$ that is included in exactly one of the sets. Assume without loss of generality (WLOG) that $m$ is only in $B$. For all $n < m$, $A$ and $B$ either both include or exclude $n$, so we only need to compare:
$$\sum_{n\in A, n \geq m}\frac{1}{2^{n}} \quad \text{vs} \quad \sum_{n\in B, n \geq m}\frac{1}{2^{n}}$$
Rewriting this, we get:
$$\sum_{n\in A, n \geq m + 1}\frac{1}{2^{n}} \quad \text{vs} \quad \frac{1}{2^{m}} + \sum_{n\in B, n \geq m + 1}\frac{1}{2^{n}}$$
Even in the extreme case where $B$ includes no elements greater than $m+1$ and $A$ includes all of them, we can compare:
$$\sum_{n = m+1}^{{\infty}\frac{1}{2}{n}} \quad \text{vs} \quad \frac{1}{2^{m}}$$
Calculating the left-hand sum:
$$\sum_{n = m+1}^{{\infty}\frac{1}{2}{n}} = \frac{1}{2^{m}} \sum_{n = 0}^{{\infty}\frac{1}{2}{n}} = \frac{1}{2^{m}} \cdot \frac{1}{1-\frac{1}{2}} = \frac{1}{2^{m}}$$
This means the sum for $B$ is at least as large as the sum for $A$, so:
$$\sum_{n\in A}\frac{1}{2^{n}} \leq \sum_{n\in B}\frac{1}{2^{n}}$$

Next, we show that for all $0 \leq x < 1$, $\sum_{n\in S_{x}}\frac{1}{2^{n}} \geq \sum_{n\in C}\frac{1}{2^{n}} = \frac{4}{7}$, where $C = {1, 4, 7, ...}$ (all integers congruent to 1 mod 3), proving $\frac{4}{7}$ is a lower bound.

Note that for all $x$ in $[0,1)$, $\lfloor 1 \cdot x \rfloor = \lfloor x \rfloor = 0$, so every sum $S_x$ must include the term for $n=1$. For $S_x$ to produce a smaller sum than $C$, it would have to exclude $n=2$ and $n=3$. The values of $x$ that exclude $n=2$ are $\frac{1}{2} \leq x < 1$, and within that range, the values that exclude $n=3$ are $\frac{1}{2} \leq x < \frac{2}{3}$.

Additionally, for $S_x$ to have a smaller sum than $C$, there must exist some $n$ such that $n \in S_x$ but $n+1, n+2, n+3 \notin S_x$—in other words, the parity of $\lfloor n \cdot x \rfloor$ doesn't change for 3 consecutive values of $n$. Since $0 \leq x < 1$, $\lfloor n \cdot x \rfloor$ can increase by at most 1 when $n$ increases by 1. For the parity to stay the same for 3 consecutive terms, we need $2x < 1$, or $x < \frac{1}{2}$.

But this creates a contradiction: we need $x < \frac{1}{2}$ (for the parity condition) and $\frac{1}{2} \leq x < \frac{2}{3}$ (to exclude $n=2$ and $n=3$), which is impossible. Thus, the sum from $C$ is indeed a lower bound.

We calculate the sum for $C$ as follows:
$$\sum_{n\in C}\frac{1}{2^{n}} = \sum_{k=0}^{{\infty}\frac{1}{2}{3k+1}} = \frac{1}{2} \sum_{k=0}^{{\infty}\left(\frac{1}{8}\right)}k = \frac{1}{2} \cdot \frac{1}{1-\frac{1}{8}} = \frac{4}{7}$$

Finally, to show $\frac{4}{7}$ is the greatest lower bound, let $\epsilon > 0$. We need to show there exists an $x$ such that $\sum_{n\in S_{x}}\frac{1}{2^{n}} < \frac{4}{7} + \epsilon$.

First, we prove that for any positive integer $m$, if $\frac{2m+1}{3m+2} \leq x < \frac{2}{3}$, then for all $n < 3m + 2$, $\lfloor n \cdot x \rfloor$ is odd if and only if $n \not\equiv 1 \pmod{3}$.

To see this, note that for $n < 3m+2$, $\frac{2}{3}n - \frac{2m+1}{3m+2}n < \frac{1}{3}$. When $n=3m+2$, $\frac{2}{3}n = 2m + \frac{4}{3}$ and $\frac{2m+1}{3m+2}n = 2m + 1$, so their difference is $\frac{1}{3}$. The function $\left(\frac{2}{3} - \frac{2m+1}{3m+2}\right)n$ is linear in $n$ with a positive coefficient, so it increases with $n$.

Since $\frac{2m+1}{3m+2} \leq x < \frac{2}{3}$, we have $\frac{2m+1}{3m+2}n \leq n \cdot x < \frac{2}{3}n$, which implies $\frac{2}{3}n - \frac{1}{3} < n \cdot x < \frac{2}{3}n$ for all $n < 3m+2$. If we write $n = 3i + j$ where $i$ is a positive integer and $j \in {0,1,2}$, then:
$$2i + \frac{2j - 1}{3} < n \cdot x < 2i + \frac{2j}{3}$$
Thus, $\lfloor n \cdot x \rfloor = 2i + j - 1$, which confirms our earlier statement about the parity of $\lfloor n \cdot x \rfloor$.

Therefore, for $\frac{2m+1}{3m+2} \leq x < \frac{2}{3}$, the sum becomes:
$$\sum_{n\in S_{x}}\frac{1}{2^{n}} = \sum_{i = 1}^{{m}\frac{1}{2}{3i+1}} + \sum_{n\in S_{x}, n\geq 3m+2}\frac{1}{2^{n}}$$
This sum is less than:
$$\sum_{i = 1}^{{\infty}\frac{1}{2}{3i+1}} + \sum_{n = 3m+2}^{{\infty}\frac{1}{2}{n}} = \frac{4}{7} + \frac{1}{2^{3m+1}}$$
Choosing $m > \frac{-\log_{2}(\epsilon) - 1}{3}$, we get:
$$\frac{1}{2^{3m+1}} < \frac{1}{2^{-\log_{2}(\epsilon)}} = \epsilon$$
Thus:
$$\sum_{n\in S_{x}}\frac{1}{2^{n}} < \frac{4}{7} + \epsilon$$
Which completes the proof.

备注：内容来源于stack exchange，提问作者Very Interesting