Difference between revisions of "2021 USAJMO Problems/Problem 5"
(Created page with "A finite set <math>S</math> of positive integers has the property that, for each <math>s \in S,</math> and each positive integer divisor <math>d</math> of <math>s</math>, ther...") |
(→Solution) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| + | The answer is <math>0</math> (left out by problem author) or <math>2^n</math> for any non-negative integer <math>n</math>. | ||
| + | |||
| + | To construct <math>|S|=2^n</math>, take <math>2n</math> distinct primes <math>p_1, q_1, p_2, q_2, \dots p_n, q_n</math> and construct <math>2^n</math> elements for <math>S</math> by taking the product over all <math>n</math> indices <math>i</math> of either <math>p_i</math> or <math>q_i</math> for every <math>i</math>. | ||
| + | |||
| + | Note that (from the problem statement) each element of <math>S</math> has <math>|S|</math> divisors. | ||
| + | |||
| + | Now it suffices to show that there is no element <math>x \in S</math> such that <math>x</math> is divisible by more than one power of any prime. | ||
| + | |||
| + | Suppose there does exist an element <math>x</math> and a prime <math>p</math> such that <math>p^2 \mid x</math>. | ||
| + | |||
| + | This implies that there exists an element <math>c \in S</math> that is divisible by <math>p</math> but not <math>p^2</math> by <math>\gcd (x,c)=p</math>. | ||
| + | |||
| + | Exactly half of <math>c</math>'s divisors are not divisible by <math>p</math>, so it follows that exactly half of the elements in <math>S</math> are not divisible by <math>p</math>. | ||
| + | |||
| + | However, if <math>p^0 , p^1 , \dots p^k</math> are the powers of <math>p</math> dividing <math>x</math> for some <math>k \ge 2</math>, only <math>\frac{1}{k+1}</math> of the divisors of <math>x</math> are not divisible by <math>p</math>. | ||
| + | |||
| + | But this means that <math>\frac{1}{k+1}</math> of the elements of <math>S</math> are not divisible by <math>p</math>, contradiction. | ||
| + | |||
| + | Therefore, <math>|S|</math> must be some power of <math>2</math>. | ||
| + | |||
| + | ==See Also== | ||
| + | {{USAJMO newbox|year=2021|num-b=4|num-a=6}} | ||
| + | |||
| + | [[Category:Olympiad Number Theory Problems]] | ||
| + | {{MAA Notice}} | ||
Latest revision as of 17:39, 12 May 2021
A finite set 
of positive integers has the property that, for each 
and each positive integer divisor 
of 
, there exists a unique element 
satisfying 
. (The elements and 
could be equal.)
Given this information, find all possible values for the number of elements of .
Solution
The answer is 
(left out by problem author) or 
for any non-negative integer 
.
To construct 
, take 
distinct primes 
and construct elements for by taking the product over all indices 
of either 
or 
for every .
Note that (from the problem statement) each element of has 
divisors.
Now it suffices to show that there is no element 
such that 
is divisible by more than one power of any prime.
Suppose there does exist an element and a prime 
such that 
.
This implies that there exists an element 
that is divisible by but not 
by 
.
Exactly half of 
's divisors are not divisible by , so it follows that exactly half of the elements in are not divisible by .
However, if 
are the powers of dividing for some 
, only 
of the divisors of are not divisible by .
But this means that of the elements of are not divisible by , contradiction.
Therefore, must be some power of 
.
See Also
| 2021 USAJMO (Problems • Resources) | ||
| Preceded by Problem 4 |
Followed by Problem 6 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAJMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
