Putnam 2009 A4 : $S$ be a set of rational numbers such that if $x$ in $S$, then $x+1$ in $S$ and $x-1$ in $S$

Question

Question

$ \text{Let } S \text{ be a set of rational numbers such that} $

\begin{align*} (a) &\ 0 \in S; \\ (b) &\ \text{If } x \in S, \text{ then } x+1 \in S \text{ and } x-1 \in S; \text{ and} \\ (c) &\ \text{If } x \in S \text{ and } x \notin \{0, 1\}, \text{ then } \frac{1}{x(x - 1)} \in S. \end{align*}

$ \text{Must } S \text{ contain all rational numbers?} $

My attempt (answer) am I right?

Noww it's clear that $S$ contains $0$ due to property $(a)$.

Let consider property $(b)$. If $S$ contains $0$, then by applying $(b)$ repeatedly

$ 0 \in S \Rightarrow (-1) = 0 - 1 \in S \Rightarrow (-2) = (-1) - 1 \in S \Rightarrow \ldots \Rightarrow 2 = 1 + 1 \in S \Rightarrow \ldots $

Let consider property $(c)$. If $S$ contains an element $x$ which is not $0$ or $1$, then it also contains $\frac{1}{x(x - 1)}$, and by applying this property repeatedly, $S$ will contain a set of rational numbers of the form $\frac{1}{x(x - 1)}$, where $x$ is not $0$ or $1$.

Therefore, $S$ does not necessarily contain all rational numbers. It contains a specific subset of rational numbers based on the properties $(a)$, $(b)$, and $(c)$.

Answer 1

The problem with your proof is that you haven't considered the interaction between rules (b) and (c) properly.

As you have correctly noted, $\mathbb{Z} \subseteq S$ because all integers can be reached by starting at 0 and either adding or subtracting 1 repeatedly, per property (b).

Then by applying property (c) to the integers other than 0 and 1, we get that all of the following rational numbers are in $S$:

• $\frac{1}{2 \times 1}, \frac{1}{3 \times 2}, \frac{1}{4 \times 3}, \ldots$

But then all of these are also in $S$:

• $\frac{1}{2} \pm 1, \frac{1}{2} \pm 2, \frac{1}{2} \pm 3, \ldots$
• $\frac{1}{6} \pm 1, \frac{1}{6} \pm 2, \frac{1}{6} \pm 3, \ldots$
• $\frac{1}{12} \pm 1, \frac{1}{12} \pm 2, \frac{1}{12} \pm 3, \ldots$

Because we can apply rule (b) to all of the values we've confirmed are in $S$. And then we can apply rule (c) to all of those, and so on.

So in order to prove the statement one way or another, you have to do one of the following:

• Show that for any rational number $\frac{p}{q}$, there is a sequence of transformations corresponding to rules (b) and (c) that lets you reach it; or

• Show that there exists at least one rational number that strictly cannot be constructed through such transformations.

As the AoPS thread linked in the comments discusses, the set of reachable values relates to quadratic residues but proving it is not entirely trivial.