Difference between revisions of "2021 USAJMO Problems/Problem 5"

Latest revision as of 17:39, 12 May 2021

A finite set $S$ of positive integers has the property that, for each $s \in S,$ and each positive integer divisor $d$ of $s$ , there exists a unique element $t \in S$ satisfying $\text{gcd}(s, t) = d$ . (The elements $s$ and $t$ could be equal.)

Given this information, find all possible values for the number of elements of $S$ .

Solution

The answer is $0$ (left out by problem author) or $2^n$ for any non-negative integer $n$ .

To construct $|S|=2^n$ , take $2n$ distinct primes $p_1, q_1, p_2, q_2, \dots p_n, q_n$ and construct $2^n$ elements for $S$ by taking the product over all $n$ indices $i$ of either $p_i$ or $q_i$ for every $i$ .

Note that (from the problem statement) each element of $S$ has $|S|$ divisors.

Now it suffices to show that there is no element $x \in S$ such that $x$ is divisible by more than one power of any prime.

Suppose there does exist an element $x$ and a prime $p$ such that $p^2 \mid x$ .

This implies that there exists an element $c \in S$ that is divisible by $p$ but not $p^2$ by $\gcd (x,c)=p$ .

Exactly half of $c$ 's divisors are not divisible by $p$ , so it follows that exactly half of the elements in $S$ are not divisible by $p$ .

However, if $p^0 , p^1 , \dots p^k$ are the powers of $p$ dividing $x$ for some $k \ge 2$ , only $\frac{1}{k+1}$ of the divisors of $x$ are not divisible by $p$ .

But this means that $\frac{1}{k+1}$ of the elements of $S$ are not divisible by $p$ , contradiction.

Therefore, $|S|$ must be some power of $2$ .

@@ Line 4: / Line 4: @@
 ==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=3|num-a=5}}
+{{USAJMO newbox|year=2021|num-b=4|num-a=6}}
 [[Category:Olympiad Number Theory Problems]]
 {{MAA Notice}}

2021 USAJMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2021 USAJMO Problems/Problem 5"

Latest revision as of 17:39, 12 May 2021

Solution

See Also