Para un entero positivo $N$, escribir $N=2^k\left(\prod_ip_i^{l_i}\right)\left( \prod_jq_j^{m_j}\right)$, donde el $p_i$ e $q_j$ son primos con $p_i\equiv1\pmod{4}$ e $q_j\equiv3\pmod{4}$. La proporción de la cuadrícula que un $N$-empresa de mudanzas puede llegar a se
$$f(N)=\left\{\begin{array}{ll}
0&\text{ if } m_j\ \text{ odd for some } j\\
2^{-k}\prod_jq_j^{-m_j}&\text{ otherwise}
\end{array}\right.,$$
por lo que su conjetura es correcta.
La prueba a continuación es por inducción sobre los factores primos de a$N$
En el caso base $N=1$ clara $f(N)=1$ como $N$-empresa de mudanzas puede hacer los movimientos $(1,0)$ e $(0,1)$.
Si el $N$-empresa de mudanzas puede hacer el movimiento de $(u,v)$ claramente la $4N$-empresa de mudanzas puede hacer el movimiento de $(2u,2v)$. Por el contrario, si el $4N$-empresa de mudanzas puede hacer el movimiento de $(r,s)$luego
$$4N=r^2+s^2,$$
y la reducción de mod $4$ muestra que tanto $r$ e $s$ son incluso, decir $r=2u$ e $s=2v$. Entonces
$$u^2+v^2=\frac{r^2+s^2}{4}=N,$$
por lo que el $4N$-empresa de mudanzas puede hacer el movimiento de $(r,s)$ si y sólo si el $N$-empresa de mudanzas puede hacer el movimiento de $(u,v)$, lo que muestra que $f(4N)=\frac{1}{4}f(N)$. Para demostrar que $f(2^kN)=2^{-k}f(N)$ para todos los $N$ e $k\geq0$ ahora es suficiente para comprobar que $f(2N)=\frac{1}{2}f(N)$ por extraño $N$.
Si $N$ es impar y el $N$-empresa de mudanzas puede hacer el movimiento de $(u,v)$luego
$$(u+v)^2+(u-v)^2=2u^2+2v^2=2N,$$
por lo que el $2N$-empresa de mudanzas puede hacer el movimiento de $(u+v,u-v)$. Por el contrario, si el $2N$-empresa de mudanzas puede hacer el movimiento de $(r,s)$, luego
$$2N=r^2+s^2,$$
lo que implica que tanto $r$ e $s$ son impares, por lo que, en particular, $\frac{r+s}{2}$ e $\frac{r-s}{2}$ son enteros. Tenga en cuenta que
$$\left(\frac{r+s}{2}\right)^2+\left(\frac{r-s}{2}\right)^2=\frac{r^2+s^2}{2}=N,$$
por lo que el $N$-empresa de mudanzas puede hacer el movimiento de $\left(\tfrac{r+s}{2},\tfrac{r-s}{2}\right)$. Esto produce un bijection entre los puntos de la $N$-empresa de mudanzas puede alcanzar y los puntos de la $2N$-empresa de mudanzas puede alcanzar. De hecho, es una transformación lineal con determinante $-2$ e lo $f(2N)=\frac{1}{2}f(N)$, como se desee.
Los números primos $q\equiv3\pmod{4}$ permiten un argumento similar. Si el $qN$-empresa de mudanzas puede hacer el movimiento de $(r,s)$luego
$$qN=r^2+s^2,$$
y la reducción de mod $q$ muestra que $r^2+s^2\equiv0\pmod{q}$. Debido a $q\equiv3\pmod{4}$ se sigue que $r\equiv s\equiv0\pmod{q}$, decir $r=qu$ e $s=qv$, y por lo tanto tenemos
$$u^2+v^2=\frac{r^2+s^2}{q^2}=\frac{N}{q},$$
así, en particular, $q\mid N$. Esto demuestra que $f(qN)=0$ si $q\nmid N$. Por supuesto, si el $\frac{N}{q}$-empresa de mudanzas puede hacer el movimiento de $(u,v)$ entonces el $qN$-empresa de mudanzas puede hacer el movimiento de $(qu,qv)=(r,s)$, lo que demuestra que $f(q^2N)=q^{-2}f(N)$, y de ahí también que $f(N)=0$ si el mayor poder de $q$ dividiendo $N$ es impar.
Queda por demostrar que $f(N)=1$ para los números enteros $N$ que son un producto de números primos congruentes a $1\pmod{4}$. Para esto, el siguiente lema es conveniente:
Lema: Vamos a $a,b\in\Bbb{Z}$ con $a$ aun y $b$ impar y deje $d:=\gcd(a,b)$. Si el $N$-empresa de mudanzas puede hacer el movimiento de $(a,b)$, entonces se puede llegar a $(d,0)$.
Prueba. Deje $a':=\frac{a}{2}$ e $b':=\frac{b-1}{2}$. A continuación, el $N$-empresa de mudanzas puede llegar a
\begin{eqnarray*}
a'(a,b)+a'(-a,b)&=&a'(0,2b)=(0,ab)\\
b'(b,a)+b'(-b,a)&=&b'(0,2a)=(0,a(b-1)),
\end{eqnarray*}
y por lo tanto también es $(0,ab)-(0,a(b-1))=(0,a)$. Por simetría también puede llegar a $(a,0)$ , por lo tanto puede llegar a $(a,0)+(-a,b)=(0,b)$ a partir de la cual la conclusión se deduce.$\hspace{10pt}\square$
Deje $N$ ser un producto de números primos congruentes a $1$ mod $4$ y deje $p$ ser una de las primeras con $p\equiv1\pmod{4}$. A continuación, $p=x^2+y^2$ para coprime enteros $x$ e $y$. Si el $N$-empresa de mudanzas puede hacer el movimiento de $(u,v)$ entonces $u^2+v^2=N\equiv1\pmod{4}$. Sin pérdida de generalidad $x$ e $u$ son incluso y $y$ e $v$ son impares. Entonces
$$pN=(x^2+y^2)(u^2+v^2)=(xu\pm yv)^2+(yu\mp xv)^2,$$
para ambas opciones de signos opuestos. Por lo tanto el $pN$-empresa de mudanzas puede hacer los movimientos $(xu\pm yv,yu\mp xv)$, donde $xu\pm yv$ es impar y $yu\mp xv$ es incluso. Entonces, por el lema, el $pN$-empresa de mudanzas puede llegar a $(z_{\pm},0)$ donde $z_{\pm}:=\gcd(xu\pm yv,yu\mp xv)$, y por lo tanto puede llegar a $(z,0)$donde
$$z:=\gcd(z_+,z_-)=\gcd(xu+yv,yu-xv,xu-yv,yu+xv).$$
[Gracias a Ørjan Johansens comentarios:]
Claramente $z$ es impar, y $z\mid2\gcd(u,v)$ porque
$$(xu+yv)+(xu-yv)=2xu
\qquad\text{ y }\qquad
(yu+xv)+(yu-xv)=2yu,$$
$$(xu+yv)-(xu-yv)=2yv
\qquad\text{ y }\qquad
(yu+xv)-(yu-xv)=2xv,$$
donde $\gcd(x,y)=1$. De ello se desprende que $z\mid\gcd(u,v)$ y, por tanto, que el $pN$-empresa de mudanzas puede llegar a $(u,v)$. Esto demuestra que $f(pN)\geq f(N)$, y así por inducción que $f(N)=1$ para cada entero $N$ que es un producto de números primos congruentes a $1$ mod $4$, completando la prueba.
