¿Existe siempre un número impar de elementos?

Question

Dado un número entero no nulo $k$ ¿existe siempre un número entero positivo $n$ tal que hay exactamente un número impar de elementos $i\in\{0,1,...,n-1\}$ con $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < \frac{3(2^n-1)}4$ ? Aquí $a\mod b\in\{0,1,...,b-1\}$ .

Answer 1

Tomando $k = 2$ parece ser una excepción. Para $n \geq 3$ tenemos lo siguiente:

• Para $0 \leq i < n-3$ tenemos $2^i k = 2^{i+1} < 2^{n-3} < \frac{1}{4}(2^n - 1)$ y por lo tanto $2^i k$ no está en el rango deseado.
• Para $i = n-3$ tenemos $2^i k = 2^{n-2} = \frac{1}{4}2^n > \frac{1}{4}(2^n - 1)$ que está justo en el rango deseado.
• Para $i = n-2$ tenemos $2^i k = 2^{n-1} = \frac{1}{2}2^n$ que también está en el rango deseado.
• Para $i = n-1$ tenemos $2^i k = 2^n \equiv 1$ que no está en el rango deseado.

Así que para cualquier $n \geq 3$ el número de elementos $i \in \{0, \ldots, n-1\}$ satisfaciendo $$\frac 14 (2^n-1) < \left(2^ik \mod{2^n-1}\right) < \frac 34 (2^n-1)$$ es exactamente $2$ que es par.

Para $n = 2$ tenemos un límite inferior de $3/4 < 1$ y el límite superior de $9/4 > 2$ , en cuyo caso ambos $i = 0$ y $i = 1$ satisfacen la ecuación. De nuevo, el número de elementos es par.

Por último, para $n = 1$ tenemos un límite inferior de $1/4$ y el límite superior de $3/4$ y ningún número entero está en este rango. Así que, de nuevo, el número de elementos que satisfacen el requisito es par.

Concluyendo, $k = 2$ parece ser un contraejemplo.

Answer 2

No. De hecho, demostraré que para cualquier entero positivo $n$ y enteros $k$ hay un número par de elementos $i \in \{0, 1, \ldots , n-1\}$ satisfaciendo $\frac{2^n-1}{4}<2^ik \pmod{2^n-1}<\frac{3(2^n-1)}{4}$ . Para ello, consideraremos los siguientes elementos fijos $n$ y variando $k$ .

Si $n=1$ entonces $\frac{2^n-1}{4}=\frac{1}{4}$ y $\frac{3(2^n-1)}{4}=\frac{3}{4}$ . Está claro que no hay números enteros entre $\frac{1}{4}$ y $\frac{3}{4}$ por lo que el número de $i$ que satisface la condición es $0$ que es par.

Si $n=2$ entonces $\frac{2^n-1}{4}=\frac{3}{4}$ y $\frac{3(2^n-1)}{4}=\frac{9}{4}$ Así que $\frac{3}{4}<2^ik \pmod{3}<\frac{9}{4} \Leftrightarrow 2^ik \pmod{3}=1, 2 \Leftrightarrow 3 \nmid 2^ik \Leftrightarrow 3 \nmid k$ . Por lo tanto, si $3 \mid k$ entonces no $i$ satisface la condición, por lo que tenemos un número par ( $0$ ) de los elementos. Si $3 \nmid k$ entonces todos $i \in \{0, 1\}$ satisfacen la condición, por lo que tenemos un número par ( $2$ ) de los elementos.

Considere $n \geq 3$ . Observe que $\lceil \frac{2^n-1}{4} \rceil =2^{n-2}>\frac{2^n-1}{4}, \lfloor \frac{3(2^n-1)}{4} \rfloor =3(2^{n-2})-1<\frac{3(2^n-1)}{4}$ . Por lo tanto, $$\frac{2^n-1}{4}<2^ik \pmod{2^n-1}<\frac{3(2^n-1)}{4} \Leftrightarrow 2^{n-2} \leq 2^ik \pmod{2^n-1} \leq 3(2^{n-2})-1$$

Si $k \equiv 0 \pmod{2^n-1}$ entonces $2^ik \equiv 0 \pmod{2^n-1}$ y $0 \not \in [2^{n-2}, 3(2^{n-2})-1]$ , por lo que tenemos un número par ( $0$ ) de los elementos.

Considere $k \not \equiv 0 \pmod{2^n-1}$ . Sea $$A=\{2^{n-2}, 2^{n-2}+1, \ldots, 2^{n-1}-1\}, B=\{2^{n-1}, 2^{n-1}+1, \ldots, 3(2^{n-2})-1\}$$

Por lo tanto, nos interesa el número de $i \in \{0, 1, \ldots , n-1\}$ tal que $2^ik \pmod{2^n-1} \in A \cup B$ .

Primero demostramos un lema:

Lema 1: Si $1 \leq x \leq 2^{n-1}-1$ entonces $2^ax \in A$ para algunos $a \in \{0, 1, \ldots , n-1\}$ y $2^lx \not \in A \cup B$ para $0 \leq l<a$ . Si $2^{n-1} \leq x \leq 2^n-2$ entonces $(2^n-1)-2^b[2^n-1-x]=2^bx \pmod{2^n-1} \in B$ para algunos $b \in \{0, 1, \ldots , n-1\}$ y $(2^n-1)-2^l[2^n-1-x] \not \in A \cup B$ para $0 \leq l<b$ .

Prueba: Supongamos que $1 \leq x \leq 2^{n-1}-1$ . Si $x \in A$ hemos terminado. De lo contrario, tenemos $1 \leq x \pmod{2^n-1} \leq 2^{n-2}-1$ . Considere la secuencia $x, 2x, 4x, \ldots , 2^{n-1}x$ . Tenemos $x<2^{n-2}$ y $2^{n-1}x>2^{n-1}-1$ . Considere el más pequeño $a \in \{0, 1, \ldots , n-1\}$ s.t. $2^ax \geq 2^{n-2}$ . Claramente $a>0$ . Desde $a$ es mínima, $2^{a-1}x<2^{n-2}$ Así que $2^{n-2} \leq 2^ax<2^{n-1}$ Así que $2^ax \in A$ . Ahora para $0 \leq l<a$ tenemos $1 \leq x \leq 2^lx \leq 2^{a-1}x<2^{n-2}$ donc $2^lx \not \in A \cup B$ .

Supongamos que $2^{n-1} \leq x \leq 2^n-2$ . Si $x \in B$ entonces $(2^n-1)-[2^n-1-x]=x \in B$ así que hemos terminado. De lo contrario, tenemos $3(2^{n-2}) \leq x \leq 2^n-2$ . Entonces $1 \leq 2^n-1-x \leq 2^{n-2}-1$ Así que por encima de $2^b(2^n-1-x) \in A$ para algunos $b \in \{0, 1, \ldots , n-1\}$ y $2^l(2^n-1-x) \not \in A \cup B$ para $0 \leq l<b$ Así que $2^n-1-2^b(2^n-1-x)=2^bx \pmod{2^n-1} \in B$ y $2^n-1-2^l(2^n-1-x) \not \in A \cup B$ para $0 \leq l<b$ .

Continuación de observamos que por el lema $1$ ya que $k \not \equiv 0 \pmod{2^n-1}$ , $2^l[k \pmod{2^n-1}] \in A \cup B$ para algunos $l \in \{0, 1, \ldots, n-1\}$ . Ahora \begin{align} & \{2^ik \pmod{2^n-1}, i \in \{0, 1, \ldots , n-1\}\} \\ & =\{2^i(2^l[k \pmod{2^n-1}]) \pmod{2^n-1}, i \in \{0, 1, \ldots , n-1\}\} \end{align} (donde aquí estamos considerando conjuntos múltiples), por lo que el número de $i$ que satisface la condición es la misma para $k$ y $2^l[k \pmod{2^n-1}]$ . Esto implica que basta con considerar $k \in A \cup B$ .

Consideremos ahora un grafo dirigido $G$ con $2^{n-1}$ vértices que representan el $2^{n-1}$ números en $A \cup B$ . Denotemos el vértice que representa un número $k \in A \cup B$ como $v_k$ . Hay una arista dirigida desde $v_{k_1}$ a $v_{k_2}$ si y sólo si $2^lk_1 \pmod{2^n-1}=k_2$ para algunos $l \in \{1, 2, \ldots , n-1\}$ y $2^jk_1 \pmod{2^n-1}\not \in A \cup B$ para $0<j<l$ . En otras palabras, $k_2$ es el primer término de la secuencia $2^1k_1 \pmod{2^n-1}, 2^2k_1 \pmod{2^n-1}, \ldots$ que está en $A \cup B$ . (Si $2^lk_1 \not \in A \cup B$ para cualquier $l \in \{1, 2, \ldots , n-1\}$ entonces no hay ninguna arista dirigida que salga de $v_{k_1}$ ) Nota: Permitimos $G$ para ser un multigrafo, por lo que podemos tener una arista dirigida desde $v_{k_1}$ a $v_{k_2}$ y una arista dirigida desde $v_{k_2}$ a $v_{k_1}$ .

Podemos ver fácilmente que dado el $k_1$ hay a lo sumo 1 valor de $k_2$ por definición. Del mismo modo, dado el $k_2$ hay a lo sumo 1 valor de $k_1$ . (Desde $k_1$ es el primer término de la secuencia $2^{-1}k_1 \pmod{2^n-1}, 2^{-2}k_2 \pmod{2^n-1}, \ldots$ que está en $A \cup B$ ) Por lo tanto, cada vértice tiene un grado $\leq 1$ y el grado de fuera $\leq 1$ . Desde $2^nk \equiv k \pmod{2^n-1}$ , es evidente que cada vértice pertenece a un ciclo o está aislado.

Ahora considere algunos $k \in A \cup B$ . Supongamos que $d$ es el menor número entero positivo s.t $2^dk \equiv k \pmod{2^n-1}$ . Entonces $d=ord_{\frac{2^n-1}{\gcd(k, 2^n-1)}}(2)$ y $2^n \equiv 1 \pmod{\frac{2^n-1}{\gcd(k, 2^n-1)}}$ Así que $d \mid n$ . Así, entre $k \pmod{2^n-1}, 2k \pmod{2^n-1}, \ldots , 2^{n-1}k \pmod{2^n-1}$ cada uno de los números $k \pmod{2^n-1}, 2k \pmod{2^n-1}, \ldots , 2^{d-1}k \pmod{2^n-1}$ aparece exactamente $\frac{n}{d}$ tiempos. Dejemos que $c$ sea la longitud del ciclo que contiene $v_k$ . (Si $v_k$ está aislado, entonces dejemos que $c=1$ .) Entonces hay $c$ elementos $i \in \{0, 1, \ldots , d-1\}$ s.t. $2^ik \pmod{2^n-1} \in A \cup B$ , por lo que hay $c(\frac{n}{d})$ elementos $i \in \{0, 1, \ldots , n-1\}$ s.t. $2^ik \pmod{2^n-1} \in A \cup B$ . Por lo tanto, queremos demostrar que $c(\frac{n}{d})$ siempre es par. Para ello, basta con demostrar que $c$ es siempre par, o, de forma equivalente, que $G$ no tiene ciclos impar. Por lo tanto, basta con demostrar que $G$ es bipartita.

Considere $A_1=\{2^{n-2}, 2^{n-2}+1, \ldots , 3(2^{n-3})-1\}, A_2=\{3(2^{n-3}), 3(2^{n-3})+1, \ldots , 2^{n-1}-1\}$ donc $A=A_1 \cup A_2$ .

Para cada $k \in A_1$ tenemos $2k \in B$ por lo que hay una arista dirigida desde cada vértice $v_k, k \in A_1$ a $v_{2k}, 2k \in B$ . Evidentemente, si $k, k' \in A_1, k \not =k'$ entonces $2k \not =2k'$ .

Considere $k \in A_2$ . Entonces $3(2^{n-2})-1<2k\leq 2^n-2$ , $2k \not \in B$ . Por el lema $1$ tenemos $(2^n-1)-2^b[2^n-1-2k]=2^{b+1}k \pmod{2^n-1} \in B$ para algunos $b \in \{0, 1, \ldots , n-1\}$ , donde $b$ es único. Tenemos $(2^n-1)-2^l[2^n-1-2k] \not \in A \cup B$ para $0 \leq l<b$ . También $b\not =n-1$ Si no es así $k=2^nk \pmod{2^n-1} \in B$ una contradicción. Por lo tanto, $b+1 \in\{1, 2, \ldots , n-1\}$ . Por lo tanto, hay una arista dirigida desde cada vértice $v_k, k \in A_2$ a $v_z, z=(2^n-1)-2^b[2^n-1-2k] \in B$ . Tenga en cuenta que $z=(2^n-1)-2^b[2^n-1-2k]$ es impar. También la parte impar de $2^n-1-z$ es $2^n-1-2k$ que es diferente para diferentes $k$ . Por lo tanto, cada $k$ da un valor distinto para $z=(2^n-1)-2^b[2^n-1-2k]$ .

Así, hemos demostrado que existe una arista dirigida desde cada vértice en $A_G$ a un único vértice en $B_G$ , donde $A_G=\{v_k, k \in A \}, B_G=\{v_k, k \in B \}$ . (así que no $2$ de estas aristas dirigidas comparten un vértice) Considere cualquier otra arista dirigida en $G$ Si es que lo hay. No puede partir de ningún vértice en $A_G$ ya que cada vértice tiene grado exterior $\leq 1$ y ya tenemos una arista dirigida que sale de cada vértice en $A_G$ . Del mismo modo, no puede terminar en ningún vértice de $B_G$ ya que cada vértice tiene un grado $\leq 1$ y ya tenemos una arista dirigida que termina en cada vértice de $B_G$ .

Por lo tanto, no hay aristas dirigidas entre los vértices de $A_G$ y ninguna arista dirigida entre los vértices de $B_G$ Así que $G$ es bipartita, y hemos terminado.