Let $k$ be a fixed even positive integer, $N$ is the product of $k$ distinct primes $p_1,...,p_k$, $a,b$ are two positive integers, $a,b\leq N$. Denote $S_1=\{d|$ $d|N, a\leq d\leq b, d$ has even number of prime factors$\}$, $S_2=\{d|$ $d|N, a\leq d\leq b, d$ has odd number of prime factors$\}$, Prove: $|S_1|-|S_2|\leq C^{\frac{k}{2}}_k$
Problem
Source: 2014 China TST 2 Day 2 Q6
Tags: number theory proposed, number theory, poset
mathocean97
20.03.2014 22:55
This seems too easy for Q3, so I'm probably wrong. We word this with sets/posets. So think of the factors as sets of the primes. (so a prime is in the set of the factor if the prime divides it) So call the sets $s_1, s_2, \ldots, s_{2^k}$, and the corresponding factors are $f_1, f_2, \ldots, f_{2^k}$. Note that if $a \le f_i, f_j \le b$ and $s_i \subset s_k \subset s_j$, then $a \le f_k \le b$ (*) (This is trivial) Now cover the poset $s_1, s_2, \ldots, s_{2^k}$ with chains (specifically $\binom{k}{k/2}$ chains). This is standard and is pretty much Sperner's Theorem and Dilworth's Theorem.
For each chain $C$ let $C_1, C_2$ be the sets of subsets that have even, respectively odd size.
So for each chain, the difference $|C_1| - |C_2| \le 1$, because of (*). Now sum over all $\binom{k}{k/2}$ chains to get the result.
changpotato
25.04.2014 15:13
mathocean97 wrote:
This seems too easy for Q3, so I'm probably wrong. We word this with sets/posets. So think of the factors as sets of the primes. (so a prime is in the set of the factor if the prime divides it) So call the sets $s_1, s_2, \ldots, s_{2^k}$, and the corresponding factors are $f_1, f_2, \ldots, f_{2^k}$. Note that if $a \le f_i, f_j \le b$ and $s_i \subset s_k \subset s_j$, then $a \le f_k \le b$ (*) (This is trivial) Now cover the poset $s_1, s_2, \ldots, s_{2^k}$ with chains (specifically $\binom{k}{k/2}$ chains). This is standard and is pretty much Sperner's Theorem and Dilworth's Theorem.
For each chain $C$ let $C_1, C_2$ be the sets of subsets that have even, respectively odd size.
So for each chain, the difference $|C_1| - |C_2| \le 1$, because of (*). Now sum over all $\binom{k}{k/2}$ chains to get the result.
Why does (*) implie that $|C_1| - |C_2| \le 1$ ? The chain $C$ may only contain subsets that have even size
mathocean97
25.04.2014 17:45
Well, no because when you add an element to the chain, you change the parity.
drkim
09.06.2016 07:08
This is the main theorem in P. Erdos, On a problem in elementary number theory, Math. Student 17 (1949).