Find all positive real numbers $r<1$ such that there exists a set $\mathcal{S}$ with the given properties: i) For any real number $t$, exactly one of $t, t+r$ and $t+1$ belongs to $\mathcal{S}$; ii) For any real number $t$, exactly one of $t, t-r$ and $t-1$ belongs to $\mathcal{S}$.
Problem
Source: 14th March 2013
Tags: induction, modular arithmetic, algebra proposed, algebra
04.04.2013 00:51
Hopefully this works ... We'll show such a set exists for $0 < r < 1$ unless $r$ is rational and in lowest terms $r = p/q$ satisfies $3 \nmid p + q$. First, remark that $\mathcal{S}$ is uniquely determined by $\mathcal{S} \cap [0, r + 1)$. Indeed, suppose $s \in \mathcal{S}$. Then $s + r, s + 1 \not \in \mathcal{S}$ from the first statement, so setting $t = r + s + 1$ in the second statement forces $r + s + 1 \in \mathcal{S}$. By induction, $s + (r + 1)k$, $k \in \mathbb{Z}$, is in $\mathcal{S}$. Thus $s \in \mathcal{S}$ iff $s \pmod{r + 1} \in \mathcal{S}$. We'll prove that for $s \in \mathcal{S}$, $s + ar + b \in \mathcal{S}$ iff $3 | a - b$. Since we've established reduction modulo $r + 1$, it is sufficient to prove $s + (a - b)r \in \mathcal{S}$ iff $3 | a - b$. Of course $s + 0r \in \mathcal{S}$. Then setting $t = s$ in the first statement gives $s + r \not \in \mathcal{S}$. Putting $t = s + r$ in the same gives $s + 2r \not \in \mathcal{S}$. Now setting $t = s + 2r$ in the second statement yields \[s + 2r - 1 \in \mathcal{S} \implies s + 2r - 1 + (r + 1) = s + 3r \in \mathcal{S}\] We can continue in this fashion (in both directions), and so it's easy to see $s + (a - b)r \in \mathcal{S}$ iff $3 | a - b$. Now, we decide which rational values of $r$ work. Suppose $r = p/q$ in lowest terms. If $3 \nmid p + q$, we can write \[\mathcal{S} \ni s = s + qr - p \not \in \mathcal{S}\] since $3 \nmid q - (-p) = q + p$, contradiction. Otherwise, $3 | p + q$, in which case we can choose $\mathcal{S} \cap [0, r + 1)$ to be \[ [0, \frac{1}{q}) \cup [\frac{3}{q}, \frac{4}{q}) \cup \dots \cup [\frac{p + q - 3}{q}, \frac{p + q - 2}{q})\] which uniquely determines $\mathcal{S}$ by extension modulo $r + 1$. It is fairly easy to see that this $\mathcal{S}$ satisfies the problem statement. Finally, if $r$ is irrational such a set exists as well. Since $r \not \in \mathbb{Q}$, $1$ and $r$ are linearly independent over $\mathbb{R}$ (that is, no integer linear combination of the two equals zero). Then for every $x \in \mathbb{R}$, define \[S_x = \{x + ir + j | i, j \in \mathbb{Z}\}\] By linear independence, $S_x \cap S_y \ne \emptyset \implies S_x = S_y$. Let $U = \bigcup_{x \in \mathbb{R}}{S_x}$ and from each $u \in U$ choose an arbitrary representative element $e_u \in u$; now set \[\mathcal{S} = \bigcup_{u \in U}{\{e_u + ir + j : i, j \in \mathbb{Z} \; \text{and} \; 3 | i - j\}}\] It is straightforward to check that this choice of $\mathcal{S}$ satisfies the problem statement.
08.08.2021 04:36
$\mathcal{S}$ exists if $r$ is irrational or if in lowest terms, $r = \frac{a}{b}$ for integers $a,b$ where $3 \mid a+b.$ In the latter case, take $$\left[0, \frac{1}{b} \right) \cup \left[\frac{3}{b}, \frac{4}{b} \right) \cup \left[\frac{6}{b}, \frac{7}{b} \right) \dots $$ In the former case, let $Q$ be the set of numbers that can be represented in the form $cr + d$ for integers $c,d.$ Let $Q'$ be the set of numbers that can be represented in the form $cr + d$ for integers $c,d$ such that $3 \mid c-d.$ Choose a subset $R$ of all reals in the interval $[0 , 1)$ such that a real in the interval $[0 , 1)$ is in $R$ if and only if it cannot be represented as the sum of another distinct element in $R$ and an element in $Q.$ Taking $\mathcal{S}$ to be the set of all reals that can be written as a sum of an element in $R$ and an element in $Q'$ works, noting that $cr + d = er + f \implies c=e, d=f$ if $c,d,e,f$ are integers. Suppose $r = \frac{a}{b}$ for integers $a,b$ where $3 \nmid a+b.$ If a real $t$ is in $\mathcal{S},$ then both $t+r$ and $t+1$ are not. Furthermore, exactly one of $t+r+1,$ $t+1,$ $t+r,$ belongs to $\mathcal{S},$ and so $t+r+1,$ is in $\mathcal{S}$ as well. This is reversible, so $t$ is in $\mathcal{S}$ iff $t+r+1$ is in $\mathcal{S}.$ Furthermore, if $t$ is in $\mathcal{S},$ then $t+r$ is not. So either $t+2r,$ $t+r+1,$ is in $\mathcal{S},$ but $t+r+1$ is in $\mathcal{S}$ so $t+2r$ is not. So either $t+3r$ or $t+2r+1$ is in $\mathcal{S},$ but $t+2r+1$ is not in $\mathcal{S}$ so it must be the former. The converse follows symmetrically as well, and we conclude that $t$ is in $\mathcal{S}$ iff $t+cr+d$ is in $\mathcal{S}$ for integers $a,b$ where $3 \mid c - d.$ Then for an element $t$ in $\mathcal{S},$ $t+dr-c$ is not in $\mathcal{S}$ since $3 \nmid a+b,$ but $dr -c = 0$ so $t$ itself is not in $\mathcal{S}$ which is contradiction. $\square$