Find the $k$ such that $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$. Find all positive integers $k$ such that for any positive integer $n$, $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$.
From olympiad problem
I'm curious So far no one to solve this problem,Maybe it is very difficult May be other reasons? But I really want to know how to solve this problem more easy?
 A: The number of factors $2$ in a number $a!$ is:
$$
\left\lfloor \frac a 2 \right\rfloor
+
\left\lfloor \frac a 4 \right\rfloor
+
\left\lfloor \frac a 8 \right\rfloor
+ \cdots
$$
So we have to find all $k$ such that for every $n$, we have
$$
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
$$
Now, to save typing, I define $F(a) = \sum_{x=1} \left\lfloor \frac{a}{2^x} \right\rfloor$. So how much is $F(a)$ compared to $a$?
Lemma: $F(2^a) = 2^a-1$
Proof: We have $F(2^a) = 2^{a-1} + 2^{a-2} + \cdots + 1 = 2^a-1$.
$\blacksquare$
Lemma: If $b < 2^a$, then $F(2^a + b) = F(2^a) + F(b)$.
Proof: For every $x < a$, $\frac{2^a}{2^x}$ is an integer and thus
$$
\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
$$
For every $x \geq a$, we have $\left\lfloor \frac{b}{2^x} \right\rfloor = 0$, so the equation holds as well.
$\blacksquare$
A consequence of this is that $a - F(a)$ is the number of ones in the binary representation of $a$.
So $kn - n + 1 > F(kn) - F(n)$ means that $kn - F(kn) \geq n - F(n)$, which means that the binary representation of $kn$ has at least as many ones as the one of $n$.
So it's obvious that $k = 2^a$ always works. I'll think of some reasons why other $k$s don't work shortly. 
A: It holds that for any number n the exponent $e_p(n)$ of a prime p in n! is exactly
$e_p(n) = \frac{n-d_p(n)}{p-1}$
where $d_p(n)$ denotes the sum of digits in base p.
This leads to the following reformulation of the problem:
Find all positive integers $k$ such that for all positive integers 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)$ 
We note for all $k$ not relatively prime to 2:
Let $p_2$ be the exponent of 2 in the prime factorization of $k$. We define $k^*$ as then $k^* = k/(2^{p_2})$ which is relatively prime to 2. Now $d_2(n) \leq d_2(k^*n) \Leftrightarrow d_2(n) \leq d_2(kn)$. Hence we only need to prove or disprove the statement for numbers relatively prime to 2.
As we can easily see, if k = 1 then $d_2(n) = d_2(kn)$ and the above holds.
Let $k$ be relatively prime to 2 and $2^l>k>1$. Consider the number $q := 2^{φ(k)-1}-1$, which is divisible by $k$, and let $s_k := d_2(\frac{q}{k}) \geq 1$.
Now look at $(\sum_{i=0}^{l}2^{i(φ(k)-1)}) \cdot (2^{φ(k)-1} -1) =: M = 2^{l(φ(k)-1)}-1$
We have $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)$ since 
$d_2(1+M/k) = \\
 d_2(1+\sum_{i=0}^{l}(2^{i(φ(k)-1)}\cdot \frac{q}{k}) = \\ 
d_2(1+\frac{q}{k})+d_2(\sum_{i=1}^{l}(2^{i(φ(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$
Using the above inequalities and $n=1+M/k$, we can see that $d_2(kn) < 1+l \leq d_2(n)$, which can be found for all k > 1 relatively prime to 2. But as outlined above, for every number which is not a power of 2 can be reduced to such a $k$. Hence, only power of 2 fulfill the problem.
