China Mathematical Olympiad

For each positive integer $n$, we write $n$ in binary representation as $n = 2^{a_1} + 2^{a_2} + \dots + 2^{a_k}$, where $0 \le a_1 < a_2 < \dots < a_k$. Define a set $T(n) = \{2^{a_1}, \dots, 2^{a_k}\}$, $T(0)$ is considered empty set.
By Lucas' theorem, $C_n^i$ is odd if and only if $T(i) \le T(n)$, hence
$$f(n,q) = \sum_{A \subseteq T(n)} q^{\sigma(A)} = \prod_{a \in T(n)} (1+q^a),$$
where $\sigma(A)$ denotes the sum of all elements of $A$.
For $m,n$ and $q$ as given by assumption, we show that if
$$f(m,q) = \prod_{a \in T(m)} (1+q^a) \mid \prod_{a \in T(n)} (1+q^a) = f(n,q),$$
then $T(m) \subseteq T(n)$, and consequently, $f(m,r) \mid f(n,r)$ for every $r$.
For any integers $i, j$, $0 \le i < j$, we have the following factorization:
$$q^{2j} - 1 = (q^{2j-1} + 1) \cdots (q^2 + 1)(q^2 - 1),$$
therefore
$$(q^{2j} + 1, q^{2i} + 1) = (q^{2i} + 1, 2) \mid 2.$$
Let $s(k)$ be the largest odd divisor of a positive integer $k$, then it follows that $s(q^{2i} + 1)$ and $s(q^{2j} + 1)$ are coprime. Clearly $q > 1$. If $i > 0$, $q^{2i} + 1 \equiv 1 \pmod{2}$, and $q^{2j} + 1 > 2$, thus $s(q^{2i} + 1) > 1$. If $i = 0$, since $q + 1$ is not a power of $2$, we have $s(q + 1) > 1$. For any $a \in T(m)$, $s(q^a + 1) \mid \prod_{b \in T(n)} s(q^b + 1)$. Since $s(1 + q^a) > 1$, we have $a \in T(n)$, hence $T(m) \subseteq T(n)$, which completes the proof!