Let and be positive integers with . Set , and is a subset of such that every element in is divisible by at most one element in . Prove that
Solution
For every with , we define set
There are elements in . Since every element in is not divisible by any two distinct elements in , it follows that for . Thus
Note that . It follows that
So the desired result is obtained.
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.