Maths Olympiad Prep

Library / /55 of 97

Number theory Difficulty 8.0 Shortlist Find the answer

Let kk be a fixed even positive integer, NN is the product of kk distinct primes p1,...,pkp_1,...,p_k, a,ba,b are two positive integers, a,bNa,b\leq N. Denote
S1={dS_1=\{d| dN,adb,dd|N, a\leq d\leq b, d has even number of prime factors}\},
S2={dS_2=\{d| dN,adb,dd|N, a\leq d\leq b, d has odd number of prime factors}\},
Prove: S1S2Ckk2|S_1|-|S_2|\leq C^{\frac{k}{2}}_k

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let k k be a fixed even positive integer, and let N N be the product of k k distinct primes p1,p2,,pk p_1, p_2, \ldots, p_k . Let a a and b b be two positive integers such that a,bN a, b \leq N . Define the sets:
S1={ddN,adb, and d has an even number of prime factors}, S_1 = \{ d \mid d \mid N, a \leq d \leq b, \text{ and } d \text{ has an even number of prime factors} \},
S2={ddN,adb, and d has an odd number of prime factors}. S_2 = \{ d \mid d \mid N, a \leq d \leq b, \text{ and } d \text{ has an odd number of prime factors} \}.

We aim to prove that:
S1S2(kk/2). |S_1| - |S_2| \leq \binom{k}{k/2}.

Consider the factors of N N as sets of the primes. Each factor d d of N N can be represented by a subset of the set of primes {p1,p2,,pk}\{p_1, p_2, \ldots, p_k\}. Let s1,s2,,s2k s_1, s_2, \ldots, s_{2^k} be these subsets, and let f1,f2,,f2k f_1, f_2, \ldots, f_{2^k} be the corresponding factors.

By Sperner's Theorem and Dilworth's Theorem, we can cover the poset of these subsets with (kk/2)\binom{k}{k/2} chains. For each chain C C , let C1 C_1 and C2 C_2 be the sets of subsets that have even and odd sizes, respectively.

For any chain C C , the difference C1C21 |C_1| - |C_2| \leq 1 . This is because if afib a \leq f_i \leq b and sisksj s_i \subset s_k \subset s_j , then afkb a \leq f_k \leq b , which is a trivial observation.

Summing over all (kk/2)\binom{k}{k/2} chains, we get the desired result:
S1S2(kk/2). |S_1| - |S_2| \leq \binom{k}{k/2}.

The answer is: (kk/2)\boxed{\binom{k}{k/2}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.