Intersección entre subconjuntos de$\mathbb{Z}_n$

Question

Deje $n \in \mathbb{N}$ ser un entero par y $k$ el mayor entero tal que $2^k < n$. Deje $S = \{\pm 2^0, \pm 2^1, \pm 2^2, \ldots, \pm 2^k \}$ considerado como un subconjunto de a $\mathbb{Z}_n$ donde tomamos representantes en $\{0, \ldots, n - 1\}$.

Ejemplo: Para $n = 6$, $S = \{\pm 1, \pm 2, \pm 4 \} = \{1, 5, 2, 4\}$

Denotar $jS = \{js : s \in S\}$$L = \{x \in \mathbb{Z}_n : \lceil n / 4 \rceil \leq x \leq \lfloor 3n / 4 \rfloor \}$. Necesito mostrar que $L \cap jS \neq \emptyset$ todos los $j = 1 \ldots, n - 1$. ¿Alguien tiene una idea? He comprobado con un equipo que es cierto hasta el $10^4$.

Ejemplo (continuación): Tenemos $L = \{ 2, 3, 4\}$ y

$1S = S = \{1, 2, 4, 5\}$, $L \cap 1S = \{ 2, 4 \}$

$2S = \{ 2, 4\}$, $L \cap 2S = \{ 2, 4 \}$

$3S = \{ 0, 3\}$, $L \cap 3S = \{ 3 \}$

$4S = \{ 2, 4\}$, $L \cap 4S = \{ 2, 4 \}$

$5S = S = \{1, 2, 4, 5\}$, $L \cap 5S = \{ 2, 4 \}$

Answer 1

Versión de mordida de sonido: empieza con$j$ y sigue duplicando hasta que caiga en ese intervalo de centro.

Prueba rigurosa: podemos suponer que$1\le j\le n/2$, para si$j>n/2$ entonces podemos considerar$n-j$ en su lugar. Sea$m$ el entero no negativo más pequeño tal que$2^mj \ge n/4$. Tenga en cuenta que$m\le k$, ya que$2^{k+1} \ge n$ por la definición de$k$ y así$2^kj \ge 2^k \ge n/2$. Si$m=0$, entonces$j\in\jS\cap L$. Si$m>0$, tenga en cuenta que$2^{m-1}j < n/4$ por la definición de$m$, y así$2^mj < n/2$. Como$2^mj\ge n/4$ por definición, concluimos que$2^mj \in jS \cap L$.