Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎See Also)
(→‎Solution)
 
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==
 
==See Also==

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$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_USAJMO_Problems/Problem_5&oldid=153630"