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 18: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.