Let be a fixed even positive integer, is the product of distinct primes , are two positive integers, . Denote
has even number of prime factors,
has odd number of prime factors,
Prove:
Solution
Let be a fixed even positive integer, and let be the product of distinct primes . Let and be two positive integers such that . Define the sets:
We aim to prove that:
Consider the factors of as sets of the primes. Each factor of can be represented by a subset of the set of primes . Let be these subsets, and let be the corresponding factors.
By Sperner's Theorem and Dilworth's Theorem, we can cover the poset of these subsets with chains. For each chain , let and be the sets of subsets that have even and odd sizes, respectively.
For any chain , the difference . This is because if and , then , which is a trivial observation.
Summing over all chains, we get the desired result:
The answer is: .
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.