Maths Olympiad Prep

Library / /34 of 34

Algebra Difficulty 7.6 National olympiad, round 2 Find the answer

A finite set SS of positive integers has the property that, for each sS,s \in S, and each positive integer divisor dd of ss , there exists a unique element tSt \in S satisfying gcd(s,t)=d\text{gcd}(s, t) = d . (The elements ss and tt could be equal.)
Given this information, find all possible values for the number of elements of SS .

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The answer is 00 (left out by problem author) or 2n2^n for any non-negative integer nn .
To construct S=2n|S|=2^n , take 2n2n distinct primes p1,q1,p2,q2,pn,qnp_1, q_1, p_2, q_2, \dots p_n, q_n and construct 2n2^n elements for SS by taking the product over all nn indices ii of either pip_i or qiq_i for every ii .
Note that (from the problem statement) each element of SS has S|S| divisors.
Now it suffices to show that there is no element xSx \in S such that xx is divisible by more than one power of any prime.
Suppose there does exist an element xx and a prime pp such that p2xp^2 \mid x .
This implies that there exists an element cSc \in S that is divisible by pp but not p2p^2 by gcd(x,c)=p\gcd (x,c)=p .
Exactly half of cc 's divisors are not divisible by pp , so it follows that exactly half of the elements in SS are not divisible by pp .
However, if p0,p1,pkp^0 , p^1 , \dots p^k are the powers of pp dividing xx for some k2k \ge 2 , only 1k+1\frac{1}{k+1} of the divisors of xx are not divisible by pp .
But this means that 1k+1\frac{1}{k+1} of the elements of SS are not divisible by pp , contradiction.
Therefore, S|S| must be some power of 22 .

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.