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 "2025 USAJMO Problems/Problem 6"

(Created page with "__TOC__ == Problem == Let <math>S</math> be a set of integers with the following properties: <math>\bullet</math> <math>\{ 1, 2, \dots, 2025 \} \subseteq S</math>. <math>\b...")
 
(→‎Solution)
 
Line 12: Line 12:
 
Prove that <math>S</math> contains all positive integers.
 
Prove that <math>S</math> contains all positive integers.
  
−
== Solution ==
+
== Solution 1==
−
{{solution}}
+
 
 +
We will show that if <math>\{1, 2, 3, \dots, n\}\in S</math>, then <math>n+1\in S</math>. Note that if <math>n+1</math> is composite, we are done, so we assume that <math>n+1</math> is an odd prime.
 +
 
 +
Case 1: <math>n+1\ne 2^k\pm 1</math> for some integer <math>k>2</math>.
 +
Since <math>n+2\ne 2^k</math>, we have that <math>2^{v_2 (n+2)}, \frac{n+2}{2^{v_2 (n+2)}}\le n\implies 2^{v_2 (n+2)}, \frac{n+2}{2^{v_2 (n+2)}}\in S\implies n+2\in S</math>. Either <math>v_2(n)=1</math> or <math>v_2(n+2)=1</math>, so <math>2^{v_2(n)+v_2(n+2)}=2^{1+\max(v_2(n), v_2(n+2))}=2\cdot 2^{\max(v_2(n), v_2(n+2))}\le 2\cdot \frac{n+2}{3}\le n\implies 2^{v_2(n)+v_2(n+2)}\in S</math>. Since <math>\gcd(n, n+2)=2</math>, we have that <math>\gcd\left(\frac{n}{2^{v_2(n)}}, \frac{n+2}{2^{v_2(n+2)}}\right)=1</math>, so <cmath>2^{v_2(n)+v_2(n+2)}\cdot \frac{n}{2^{v_2(n)}}\cdot \frac{n+2}{2^{v_2(n+2)}}=n(n+2)\in S\implies n(n+2)+1=(n+1)^2\in S\implies n+1\in S.</cmath>
 +
 
 +
Case 2: <math>n+1=2^k+1</math> for some integer <math>k>2</math>.
 +
Note that <math>k</math> must be even, otherwise <math>2^k+1\equiv 0\pmod 3</math>. Then we have the following:
 +
<cmath>\left(2^{\frac{k}{2}}+1\right)^2-1=2^{\frac{k}{2}}\left(2^{\frac{k}{2}}+2\right)=2^{\frac{k}{2}+1}\left(2^{\frac{k}{2}-1}+1\right)\in S \implies\left(2^{\frac{k}{2}}+1\right)^2\in S</cmath>
 +
<cmath>\implies 2^{\frac{k}{2}-1}\left(2^{\frac{k}{2}}+1\right)^2 = \left(2^{\frac{k}{2}-1}+1\right)\left(2^k+1\right)-1\in S\implies \left(2^{\frac{k}{2}-1}+1\right)\left(2^k+1\right)\in S\implies 2^k+1\in S,</cmath>
 +
as desired.
 +
 
 +
Case 3: <math>n+1=2^k-1</math> for some integer <math>k>2</math>.
 +
Let <math>x<k</math> be a positive integer. Then
 +
<cmath>(2^x-1)(2^k-1)-1=2^x\left(2^k-2^{k-x}-1\right)\in S\implies 2^k-1\in S,</cmath> as desired.
 +
 
 +
Hence, since <math>\{1, 2, 3, \dots, n\}\in S\implies n+1\in S</math>, the set <math>S</math> spans all positive integers.
 +
 
 +
-mop
  
 
==See Also==
 
==See Also==
 
{{USAJMO newbox|year=2025|num-b=5|after=Last Problem}}
 
{{USAJMO newbox|year=2025|num-b=5|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 12:31, 22 March 2025

Problem

Let $S$ be a set of integers with the following properties:

$\bullet$ $\{ 1, 2, \dots, 2025 \} \subseteq S$.

$\bullet$ If $a, b \in S$ and $\gcd(a, b) = 1$, then $ab \in S$.

$\bullet$ If for some $s \in S$, $s + 1$ is composite, then all positive divisors of $s + 1$ are in $S$.

Prove that $S$ contains all positive integers.

Solution 1

We will show that if $\{1, 2, 3, \dots, n\}\in S$, then $n+1\in S$. Note that if $n+1$ is composite, we are done, so we assume that $n+1$ is an odd prime.

Case 1: $n+1\ne 2^k\pm 1$ for some integer $k>2$. Since $n+2\ne 2^k$, we have that $2^{v_2 (n+2)}, \frac{n+2}{2^{v_2 (n+2)}}\le n\implies 2^{v_2 (n+2)}, \frac{n+2}{2^{v_2 (n+2)}}\in S\implies n+2\in S$. Either $v_2(n)=1$ or $v_2(n+2)=1$, so $2^{v_2(n)+v_2(n+2)}=2^{1+\max(v_2(n), v_2(n+2))}=2\cdot 2^{\max(v_2(n), v_2(n+2))}\le 2\cdot \frac{n+2}{3}\le n\implies 2^{v_2(n)+v_2(n+2)}\in S$. Since $\gcd(n, n+2)=2$, we have that $\gcd\left(\frac{n}{2^{v_2(n)}}, \frac{n+2}{2^{v_2(n+2)}}\right)=1$, so \[2^{v_2(n)+v_2(n+2)}\cdot \frac{n}{2^{v_2(n)}}\cdot \frac{n+2}{2^{v_2(n+2)}}=n(n+2)\in S\implies n(n+2)+1=(n+1)^2\in S\implies n+1\in S.\]

Case 2: $n+1=2^k+1$ for some integer $k>2$. Note that $k$ must be even, otherwise $2^k+1\equiv 0\pmod 3$. Then we have the following: \[\left(2^{\frac{k}{2}}+1\right)^2-1=2^{\frac{k}{2}}\left(2^{\frac{k}{2}}+2\right)=2^{\frac{k}{2}+1}\left(2^{\frac{k}{2}-1}+1\right)\in S \implies\left(2^{\frac{k}{2}}+1\right)^2\in S\] \[\implies 2^{\frac{k}{2}-1}\left(2^{\frac{k}{2}}+1\right)^2 = \left(2^{\frac{k}{2}-1}+1\right)\left(2^k+1\right)-1\in S\implies \left(2^{\frac{k}{2}-1}+1\right)\left(2^k+1\right)\in S\implies 2^k+1\in S,\] as desired.

Case 3: $n+1=2^k-1$ for some integer $k>2$. Let $x<k$ be a positive integer. Then \[(2^x-1)(2^k-1)-1=2^x\left(2^k-2^{k-x}-1\right)\in S\implies 2^k-1\in S,\] as desired.

Hence, since $\{1, 2, 3, \dots, n\}\in S\implies n+1\in S$, the set $S$ spans all positive integers.

-mop

See Also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_USAJMO_Problems/Problem_6&oldid=245836"