Encontrar el $k$ tal que $2^{(k-1)n+1}$ no divide $\frac{(kn)!}{n!}$.

Question

Encontrar todos los enteros positivos $k$ tal que para cualquier entero positivo $n$, $2^{(k-1)n+1}$ no divide $\frac{(kn)!}{n!}$.

De olimpiada problema

Tengo curiosidad hasta ahora nadie para resolver este problema,tal vez es muy difícil que Puede haber otros motivos? Pero realmente quiero saber cómo resolver este problema de manera más fácil?

Answer 1

El número de factores de $2$ en un número $a!$ es: $$ \left\lfloor \frac 2 \right\rfloor + \left\lfloor \frac 4 \right\rfloor + \left\lfloor \frac un 8 \right\rfloor + \cdots $$

Así que tenemos que encontrar todos los $k$ tal que para cada a $n$, tenemos $$ kn - n + 1 > \sum_{x=1} \left\lfloor \frac{kn}{2^x} \right\rfloor - \sum_{x=1} \left\lfloor \frac{n}{2^x} \right\rfloor $$

Ahora, para salvar a escribir, yo defino $F(a) = \sum_{x=1} \left\lfloor \frac{a}{2^x} \right\rfloor$. Entonces, ¿cuánto es $F(a)$ en comparación con $a$?

Lema: $F(2^a) = 2^a-1$

Prueba: Tenemos $F(2^a) = 2^{a-1} + 2^{a-2} + \cdots + 1 = 2^a-1$. $\blacksquare$

Lema: Si $b < 2^a$,$F(2^a + b) = F(2^a) + F(b)$.

Prueba: Por cada $x < a$, $\frac{2^a}{2^x}$ es un número entero y por lo tanto $$ \left\lfloor \frac{2^a + b}{2^x} \right\rfloor = \left\lfloor \frac{2^a}{2^x} \right\rfloor + \left\lfloor \frac{b}{2^x} \right\rfloor $$ Para cada $x \geq a$,$\left\lfloor \frac{b}{2^x} \right\rfloor = 0$, de manera que la ecuación tiene así. $\blacksquare$

Una consecuencia de esto es que el $a - F(a)$ es el número de unos en la representación binaria de $a$.

Por lo $kn - n + 1 > F(kn) - F(n)$ significa que $kn - F(kn) \geq n - F(n)$, lo que significa que la representación binaria de $kn$ tiene al menos tantas como la de $n$.

Así que es obvio que $k = 2^a$ siempre funciona. Voy a pensar en algunas razones por las que otros $k$s no trabajan poco.

Answer 2

Se sostiene que para cualquier número n el exponente $e_p(n)$ de un primo p en n! es exactamente

$e_p(n) = \frac{n-d_p(n)}{p-1}$

donde $d_p(n)$ denota la suma de los dígitos en base p. Esto nos lleva a la siguiente reformulación del problema:

Encontrar todos los enteros positivos $k$ tal que para todos los enteros positivos n

$\frac{(k-1)n-d_2(kn)+d_2(n)}{1}<(k-1)n+1 \\ d_2(n)-d_2(kn) < 1 \\ d_2(n) \leq d_2(kn)$

Tomamos nota de todos los $k$ no relativamente prime 2:

Deje $p_2$ ser el exponente de 2 en la factorización prima de $k$. Definimos $k^*$ entonces $k^* = k/(2^{p_2})$, que es relativamente privilegiada a 2. Ahora $d_2(n) \leq d_2(k^*n) \Leftrightarrow d_2(n) \leq d_2(kn)$. Por lo tanto sólo tenemos que probar o refutar la declaración de los números primos relativos con 2.

Como podemos ver fácilmente, si k = 1, a continuación, $d_2(n) = d_2(kn)$ y la de arriba tiene.

Deje $k$ ser relativamente primos 2 y $2^l>k>1$. Considerar el número de $q := 2^{φ(k)-1}-1$, el cual es divisible por $k$, y deje $s_k := d_2(\frac{q}{k}) \geq 1$.

Ahora mira a $(\sum_{i=0}^{l}2^{i(φ(k)-1)}) \cdot (2^{φ(k)-1} -1) =: M = 2^{l(φ(k)-1)}-1$

Tenemos $d_2(M+k) = d_2(2^{l(φ(k)-1)} + k-1)= 1+d_s(k-1)\lt 1+l \leq d_2(M/k+1)$ desde

$d_2(1+M/k) = \\ d_2(1+\sum_{i=0}^{l}(2^{i(f(k)-1)}\cdot \frac{q}{k}) = \\ d_2(1+\frac{q}{k})+d_2(\sum_{i=1}^{l}(2^{i(f(k)-1)}\cdot \frac{q}{k})) =\\ d_2(1+\frac{q}{k}) + \sum_{i=1}^{l}d_2(2^{i(k-1)}\cdot \frac{q}{k}) = \\ d_2(1+\frac{q}{k}) + \sum_{i=1}^{l}d_2(\frac{q}{k}) \geq\\ 1+l \cdot s_k \geq 1+l$

Utilizando las anteriores desigualdades y $n=1+M/k$, podemos ver que $d_2(kn) < 1+l \leq d_2(n)$, que se puede encontrar para todo k > 1 relativamente privilegiada a 2. Pero como se mencionó anteriormente, para cada número que no es una potencia de 2 se puede reducir a un $k$. Por lo tanto, sólo el poder de 2 cumplir con el problema.