The answer is $r=1-\frac1{4n},n\in\mathbb{N}$. 1) We first show $r=1-\frac1{4n}$ actually implies the property. We consider complex plane and let $a=r+\sqrt{1-r^2}i$. We use $P(x,y,a)$ to represent $ax+(1-a)y$. $x,y\in S$ imply $P(x,y,a),P(x,y,\frac1a)\in S$. Assume $-1,1\in S$. It suffices to show $0\in S$. $-1+2(1-a)=P(-1,1,a)\in S$. Suppose $x_0=-1+2k(1-a)\in S$ for $k\in\mathbb{N}$, $x_1=P(x_0,-1,\frac1a)=-1+2k(\frac1a-1)\in S$, $x_2=P(x_1,1,a)=-1+(2k+2)(1-a)\in S$. So $x_3=-1+2n(1-a)\in S$ by induction. $x_4=P(-1,x_3,\frac1a)=-1+2n(1-a)(1-\frac1a)=-1+2n(2-2r)=0\in S$. 2) Let $\cos(\theta)=\frac p{2q}$ with $q$ odd and $(p,q)=1$. Let $\cos(k\theta)=\frac{p'}{q'}$ with $(p',q')=1$. Then $4\not |q'$. We will prove it by induction. Assume $\cos((k-1)\theta)=\frac bc$ and $4\not|c,(b,c)=1$. $\cos(k\theta)=\frac{bp}{2qc}-\frac{\sqrt{c^2-b^2}\sqrt{4q^2-p^2}}{2qc}$. Chebyshev polynomial implies the RHS is rational. If $c$ is odd, $4\not|2qc$ and we are done. If $c$ is even and $4\not|c$, then $b,p$ are odd thus $bp-\sqrt{c^2-b^2}\sqrt{4q^2-p^2}$ is even. We see $q'|qc$ implies $4\not|q'$. 3) There exists $S$ without the property when $r\ne1-\frac1{4n}$. For the case $r=0,\pm1$, we can let $S$ be the set of all integer points. Now assume $r$ is not integer. Let $S=\{x|x=\pm1+2(1-a)f(a)\}$, where $f=\sum_{k=-m}^mf_ka^k$ with $f_k\in\mathbb{Z}$. Obviously $S$ is rotation-invariant. Since $-1,1\in S$, we only need to show $0\not\in S$. Suppose $0\in S$. Then there exists $f$ such that $(1-a)f(a)=\frac12$. Equating the real part of both sides, we get $\sum f_k(\cos(k\theta)-\cos((k+1)\theta)=\frac12$. The LHS can be rewritten as polynomial of $r$ by using Chebyshev polynomial $T_k$. Since $1-x|T_k(x)-T_{k+1}(x)$, we have $(1-r)G(r)=\frac12$, where $G$ is some polynomial with integer coefficients and degree $d$. Let $r=\frac pq$, then $G(r)=\frac{p'}{q'}$ with $q'|q^d$. So $(p',q)=(p',q')=1$. Now $(q-p)p'2=qq'$ implies $q-p|qq'$ and $2|q$. Since $q,p$ are coprimes, $q-p=1$ and $2|q$. Since $r\ne1-\frac1{4n}$, $r=1-\frac1{2n}$ with $2\not|n$. Going back equation $(1-a)f(a)=\frac12$, we have $f(a)=\frac1{2-2a}$. Equating the real part of both sides, $\sum f_k T_k(r)=\frac14$. If we write LHS as $\frac PQ$ with $(P,Q)=1$, $4P=Q$. But 2) implies $4\not|Q$. Absurd! Q.E.D.

The answer is that $r$ has this property if and only if $r = \frac{4n-1}{4n}$ for some integer $n$. Throughout the solution, we will let $r = \frac ab$ with $b > 0$ and $\gcd(a,b) = 1$. We also let \[ \omega = e^{i\theta} = \frac ab \pm \frac{\sqrt{b^2-a^2}}{b} i. \]This means we may work with complex multiplication in the usual way; the rotation of $z$ through center $c$ is given by $z \mapsto \omega(z-c)+c$. For most of our proof, we start by constructing a good set as follows. Start by letting $S_0 = \{0, 1\}$. Let $S_i$ consist of $S_{i-1}$ plus all points that can be obtained by rotating a point of $S_{i-1}$ through a different point of $S_{i-1}$ (with scale factor $\omega$). Let $S_\infty = \bigcup_{i \ge 0} S_i$. The set $S_\infty$ is the (minimal, by inclusion) good set containing $0$ and $1$. We are going to show that for most values of $r$, we have $\frac{1}{2} \notin S_\infty$. Claim: If $b$ is odd, then $\frac{1}{2} \notin S_\infty$. Proof. Idea: denominators that appear are always odd. Consider the ring \[ A = {\mathbb Z}_{\{b\}} = \left\{ \frac{s}{t} \mid s,t \in {\mathbb Z}, t \mid b^\infty \right\} \]which consists of all rational numbers whose denominators divide $b^\infty$. Then, $0, 1, \omega \in A[\sqrt{b^2-a^2}]$ and hence $S_\infty \subseteq A[\sqrt{b^2-a^2}]$ too. (This works even if $\sqrt{b^2-a^2} \in {\mathbb Z}$, in which case $S_\infty \subseteq A = A[\sqrt{b^2-a^2}]$.) But $\frac{1}{2} \notin A[\sqrt{b^2-a^2}]$. $\blacksquare$ Claim: If $b$ is even and $|b-a| \neq 1$, then $\frac{1}{2} \notin S_\infty$. Proof. Idea: take modulo a prime dividing $b-a$. Let $D = b^2-a^2 \equiv 3 \pmod 4$. Let $p$ be a prime divisor of $b-a$. Because $\gcd(a,b) = 1$, we have $p \neq 2$ and $p \nmid b$. Consider the ring \[ A = {\mathbb Z}_{(p)} = \left\{ \frac{s}{t} \mid s,t \in {\mathbb Z}, p \perp t \right\} \]which consists of all rational numbers whose denominators are coprime to $p$. Then, $0, 1, \omega \in A[\sqrt{-D}]$ and hence $S_\infty \subseteq A[\sqrt{-D}]$ too. Now, there is a well-defined ``mod-$p$'' ring homomorphism \[ \Psi \colon A[\sqrt{-D}] \to {\mathbb F}_p \quad\text{by}\quad x+y\sqrt{-D} \mapsto x \bmod p \]which commutes with addition and multiplication (as $p \mid D$). Under this map, \[ \omega \mapsto \frac ab \bmod p = 1. \]Consequently, the rotation $z \mapsto \omega(z-c)+c$ is just the identity map modulo $p$. In other words, the pre-image of any point in $S_\infty$ under $\Psi$ must be either $\Psi(0) = 0$ or $\Psi(1) = 1$. However, $\Psi(1/2) = 1/2$ is neither of these. So this point cannot be achieved. $\blacksquare$ Claim: Suppose $a = 2n-1$ and $b=2n$ for $n$ an odd integer. Then $\frac{1}{2} \notin S_\infty$ Proof. Idea: $\omega$ is ``algebraic integer'' sans odd denominators. This time, we define the ring \[ B = {\mathbb Z}_{(2)} = \left\{ \frac{s}{t} \mid s,t \in {\mathbb Z}, t \text{ odd} \right\} \]of rational numbers with odd denominator. We carefully consider the ring $B[\omega]$ where \[ \omega = \frac{2n-1 \pm \sqrt{1-4n}}{2n}. \]So $S_\infty \subseteq B[\omega]$ as $0, 1, \omega \in B[\omega]$. I claim that $B[\omega]$ is an integral extension of $B$; equivalently that $\omega$ is integral over $B$. Indeed, $\omega$ is the root of the monic polynomial \[ (T-1)^2 + \frac1n (T-1) - \frac 1n = 0 \]where $\frac1n \in B$ makes sense as $n$ is odd. On the other hand, $\frac{1}{2}$ is not integral over $B$ so it is not an element of $B[\omega]$. $\blacksquare$ It remains to show that if $r = \frac{4n-1}{4n}$, then goods sets satisfy the midpoint property. Again starting from the points $z_0 = 0$, $z_1 = 1$ construct the sequence \begin{align*} z_2 &= \omega(z_1-z_0) + z_0 \\ z_3 &= \omega^{-1}(z_0-z_2) + z_2 \\ z_4 &= \omega^{-1}(z_2-z_3) + z_3 \\ z_5 &= \omega(z_3-z_4) + z_4 \end{align*}as shown in the diagram below. [asy][asy] size(8cm); pair z0 = (0,0); pair z1 = (1,0); real theta = 28.96; pair z2 = rotate(theta, z0) * z1; pair z3 = rotate(-theta, z2) * z0; pair z4 = rotate(-theta, z3) * z2; pair z5 = rotate(theta, z4) * z3; draw(arc(z0, z1, z2), lightgreen); draw(arc(z3, z4, z2), lightgreen); draw(arc(z2, z3, z0), lightgreen); draw(arc(z4, z3, z5), lightgreen); draw(z1--z0--z2--z3--z4--z5, deepcyan); dot("$z_0=0$", z0, dir(-45), red); dot("$z_1=1$", z1, dir(-45), red); dot("$z_2$", z2, dir(90)); dot("$z_3$", z3, dir(90)); dot("$z_4=2r-1$", z4, dir(-90)); dot("$z_5=2r-2$", z5, dir(-90)); [/asy][/asy] This construction shows that if we have the length-one segment $\{0,1\}$ then we can construct the length-one segment $\{2r-2, 2r-1\}$. In other words, we can shift the segment to the left by \[ 1-(2r-1) = 2(1-r) = \frac{1}{2n}. \]Repeating this construction $n$ times gives the desired midpoint $\frac{1}{2}$.

Very hard problem. Took me 5 hours with a relatively lucky start. I'm not sure if this is algebra or number theory. We will employ the following construction: Let $S_{min}(0,1)$ be the set of points that include $0,1$ and for any $x\ne y, x,y\in S, e^{\pm it}(x-y)+y\in S$ where $\omega=e^{it}=\frac ab + \frac{\sqrt{b^2-a^2}}{b}i$. Any subset satisfying the conditions in the problem is a superset of $S_{min}$ so we focus on $S_{min}$.

Claim (vibes

): If $b-a>1$ then $\frac ab$ fails. Proof: Let $p\mid a-b$. I claim the real part is always $0$ or $1 mod p$, and the imaginary part can always be written as $c\sqrt{b^2-a^2}b^{-k}$ for integers $c,k$. Call such a fraction GREAT. For $p\nmid (x,y), \frac xy$ mod p is defined as the integer $t$ in $\{0,\cdots, p-1\}$ such that $p\mid x-ty$. If $t$ doesn't exist, then this operation is undefined. Consider the rotation operation $e^{it} (y-z) + z = (\frac{b-a}{b} + \frac{\sqrt{b^2-a^2}}{b}i)z + (\frac{a}{b} + \frac{\sqrt{b^2-a^2}}{b}i)y$ Its real part only depends on $y$ because $z(\frac{b-a}{b} + \frac{\sqrt{b^2-a^2}}{b})$ has real part 0 mod p and imaginary part divisible by $\sqrt{b^2-a^2}b^{-k}$. Furthermore, we can convert mod $p$ to $(1+\frac{\sqrt{b^2-a^2}}{b}i)y$ which makes the real part congruent to $y$'s real part mod $p$ and imaginary part still divisible by $\sqrt{b^2-a^2}b^{-k}$. If $p=2$, then a similar $\nu_2$ argument would suffice. If $b$ is odd, a similar $\nu_2$ argument on the real and imaginary parts of the possible points would suffice. I claim $r=\frac{4n-1}{4n}$ works. We first construct the points $0,1,e^{\pm it}, 1-e^{\pm it}$ Now note $e^{it} (1-(e^{-it})) + e^{-it} = e^{it} - 1 + e^{-it} = 2\frac ab - 1$ $e^{it} ((1-e^{-it})-e^{-it}) + e^{-it} = 2\frac ab - 2$ So we shifted this by $2\frac ab - 2 = \frac{1}{2n}$ units. Doing this $n$ times gives $\frac 12$. Finally, I claim $r=\frac{4n+1}{4n+2}$ fails. Main idea: Polynomial for the win!!! First of all, since $\nu_2(2\cos t)\ge 0$, and there exist $P_n \in \mathbb{Z}[x]$ st $P_n(x+x^{-1})=x^n+x^{-n}$ (which can be easily shown with $P_{n+1}+P_{n-1}=xP_n$), we can see $\nu_2(2\cos (kt))\ge 0$ for all $k\in \mathbb{Z}$. Now, notice we can actually describe all of our points in the set with a polynomial $Q$. If the rotation becomes $x(Q_1(x)-Q_2(x))+Q_2(x)$ then we can see the value of $Q(1)$ doesn't change. Therefore, if I start with $0,1$ and get the points of some form $Q(\omega)$ then $Q(1)\in \{0,1\}$ So we want $Q(\omega)=\frac 12, Q(1)\in \{0,1\}$ Let $R(\omega)=Q(\omega)-Q(1)=(\omega-1)S(\omega)\in \{ \frac 12, -\frac 12\}$. Then note $1-\omega=\frac{1}{4n+2} - \frac{\sqrt{8n+3}}{4n+2}i$. We want $(1-i\sqrt{8n+3})(a+bi) \in \{ 2n+1, -(2n+1)\}$, so we can see $a+bi \in \{ \frac{1+i\sqrt{8n+3}}{4}, -\frac{1+i\sqrt{8n+3}}{4} \}$. Therefore, $0 > \nu_2(2S(\omega)) = \sum a_kP_k(\omega+\omega^{-1})$ but $\nu_2(P_k(\omega+\omega^{-1}))\ge 0$, contradiction!!!

v4913: "are you doing geo?" The answer is $r=1-\tfrac{1}{4n}$ for positive integers $n$. Let $z=\cos \theta+i\sin \theta$. Notice that if points $A,B \in S$ correspond to complex numbers $a$ and $b$ in the complex plane, then a counterclockwise rotation of $A$ around $B$ is given by $a+z(b-a)=(1-z)a+zb$ and a counterclockwise rotation of $A$ around $B$ is given by $a+z^{-1}(b-a)=(1-z^{-1})a+z^{-1}b$. First, we show that $r=1-\tfrac{1}{4n}$ works: we prove that any set $T$ containing $0$ and $1$ must contain $\tfrac{1}{2}$. From $0$ and $1$, we can rotate $1$ counterclockwise around $0$ to get $z$ rotate $0$ clockwise around $z$ to get $z-1$ rotate $z$ clockwise around $z-1$ to get $(1-z^{-1})(z-1)+1=2r-1=1-\tfrac{1}{2n}$ rotate $z-1$ counterclockwise around $1-\tfrac{1}{2n}$ to get $-\tfrac{1}{2n}$ Thus, any set containing $0$ and $1$ also contains $-\tfrac{1}{2n}$ and $1-\tfrac{1}{2n}$. We repeat this argument $n$ times to show that this set contains $-\tfrac{1}{2}$ and $\tfrac{1}{2}$, as desired. To prove that no other values of $r$ work, construct sets of Laurent polynomials as follows: Let $S_0=\{0,1\}$. Let $S_i=\{(1-x)A+xB,(1-x^{-1})A+x^{-1}B \colon A,B \in S_{i-1}\}$ for positive integers $i$. Let $S_\infty=\bigcup\nolimits_{i=0}^\infty S_i$. Notice that applying $z$ to elements of $S_\infty$ results in the minimal set, by inclusion, containing $0$ and $1$. The key claim is the following. Claim: $S_\infty$ is a subset of the set of all integer-coefficient Laurent polynomials with a remainder of $0$ or $1$ when divided by $x-1$. Proof: The map $a,b \mapsto (1-x)a+xb$ taken "modulo $x-1$" is congruent to $a,b \mapsto b$, and the map $a,b \mapsto (1-x^{-1})a+x^{-1}b$ taken "modulo $x-1$" is congruent to $a,b \mapsto b$. Since we start with $S_0=\{0,1\}$, all elements of $S_\infty$ must be congruent to either $0$ or $1$ modulo $x-1$. $\square$ The problem statement implies that there exists an integer-coefficient Laurent polynomial $P$ with a remainder of $0$ or $1$ when divided by $x-1$ such that $P(z)=\tfrac{1}{2}$. If this remainder is $0$, let $P^*=P$, and otherwise, let $P^*=P-1$; we must have $|P^*(z)|=\tfrac{1}{2}$. We will prove the case of $P^*(z)=\tfrac{1}{2} \implies 2P^*(z)-1=0$, as the case of $P^*(z)=-\tfrac{1}{2}$ is analogous. Choose a nonnegative integer $N$ such that $x^NP^*(x)$ is a polynomial. We have $2z^NP^*(z)-z^N=0$, so $2x^NP^*(x)-x^N$ must be divisible by the minimal polynomial of $z$. We can easily show that $r=1$ and $r=-1$ fail, so assume that $z \ne 1,-1$. Then, the minimal polynomial of $z$ is \[(x-z)(x-\overline{z})=x^2-(z+\overline{z})x+1=x^2-\tfrac{2p}{q}x+1,\]where $r=\tfrac{p}{q}$. Let $Q$ satisfy $Q(x)(x^2-\tfrac{2p}{q}x+1)=2x^NP^*(x)-x^N$. Notice that $\tfrac{q}{\gcd(q,2)}(x^2-\tfrac{2p}{q}x+1) \in \mathbb{Z}[x]$, and it is irreducible in $\mathbb{Z}[x]$ because it is a multiple of a minimal polynomial, so \[(2x^NP^*(x)-x^N)/(\tfrac{q}{\gcd(q,2)}(x^2-\tfrac{2p}{q}x+1)) \in \mathbb{Z}[x],\]which means $Q(x) \in \mathbb{Z}[x]$. We plug in $x=1$ to the definition of $Q$ to obtain $Q(1)(2-\tfrac{2p}{q})=-1$, so $\tfrac{1}{2-2p/q}=\tfrac{1/2}{1-r}$ is an integer, which means $r=1-\tfrac{1}{2n}$, $p=2n-1$, and $q=2n$ for some positive $n$. We now prove that $n$ is even. Notice that since $z$ satisfies $z^2-\tfrac{2n-1}{n}z+1=0$, we know that $z'=nz$ must satisfy $\tfrac{z'^2}{n^2}-\tfrac{2n-1}{n^2}z'+1=0$, or $z'^2+(2n-1)z'+n^2=0$, so $z'$ is an algebraic integer. Similarly, $\overline{z'}=n\overline{z}$ is an algebraic integer. Write out the terms of the equation $P^*(z)=\tfrac{1}{2}$, replacing each $z^k$ with $\tfrac{z'^k}{n^k}$ and each $z^{-k}$ with $\tfrac{\overline{z'}^k}{n^k}$. If $n$ is odd, then multiplying the left-hand side by a large power of $n$ results in an algebraic integer, but no odd multiple of the right-hand side is an algebraic integer, a contradiction. Therefore, $n$ must be even, as desired. $\square$

This is a very nice problem! Somehow sunk three hours and was still going strong because I had progress on a nontrivial problem for once (took 2.5 hours or so after that). Luckily I didn't turn to hints too early, the claims are relatively obvious, but the last part i did need a hint from someone who said ``Construct a polynomial P' relating to your given P polynomial in the problem to get P'(w)=1/2 and compare LHS with RHS algebraic integers''. The finish was easy from there. I'm just writing for completeness; below would be the most elementary i can make it (should get to work on that DNY-intpoly unlocked for three months). BTW, the cos thing for motivating the roots of $x^2-2\cos\theta x+1$ are motivated by 17tstst3, which i had done recently. Writeup took an absolutely horrendous amount of time

Attachments: