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
During AMC testing, the AoPS Wiki is in read-only mode and no edits can be made.

Difference between revisions of "2025 USAMO Problems/Problem 1"

(→‎Solution 1)
m (→‎See Also)
 
(6 intermediate revisions by 2 users not shown)
Line 45: Line 45:
 
n^k \bmod (2n)^{\,i+1}
 
n^k \bmod (2n)^{\,i+1}
 
\;\ge\;
 
\;\ge\;
−
n^{\,k-i-1},
+
n^{\,i+1},
 
</cmath>
 
</cmath>
 
which implies
 
which implies
Line 51: Line 51:
 
a_i  
 
a_i  
 
\;\ge\;
 
\;\ge\;
 +
\left\lfloor
 +
\dfrac{n^{\,i+1}}{(2n)^i}
 +
\right\rfloor
 +
\;=\;
 
\left\lfloor
 
\left\lfloor
 
\dfrac{n}{2^i}
 
\dfrac{n}{2^i}
Line 72: Line 76:
 
{{USAJMO newbox|year=2025|num-b=1|num-a=3}}
 
{{USAJMO newbox|year=2025|num-b=1|num-a=3}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
Senor Akash Tuff in the Hood!

Latest revision as of 22:21, 29 September 2025

The following problem is from both the 2025 USAMO #1 and 2025 USAJMO #2, so both problems redirect to this page.


Problem

Let $k$ and $d$ be positive integers. Prove that there exists a positive integer $N$ such that for every odd integer $n>N$, the digits in the base-$2n$ representation of $n^k$ are all greater than $d$.

Solution 1

We define a remainder operation $\,a \bmod b\,$ to be the remainder when $a$ is divided by $b$. Also, let $\lfloor x\rfloor$ be the usual floor function.

Base-$(2n)$ Representation: \[n^k \;=\; a_{k-1}\,(2n)^{k-1} \;+\; a_{k-2}\,(2n)^{k-2} \;+\;\dots\;+\;a_1\,(2n)\;+\;a_0,\] where each $a_i$ satisfies $0 \le a_i < 2n.$ Hence, the base-$(2n)$ representation of $n^k$ is $a_{k-1}\,a_{k-2}\,\dots\,a_1\,a_0.$

Leading Digit: \[a_{k-1} \;=\; \left\lfloor \dfrac{n^k}{(2n)^{k-1}} \right\rfloor \;=\; \left\lfloor \dfrac{n}{2^{k-1}} \right\rfloor.\]

General Digit Formula: For $0 \le i < k,$ \[a_i \;=\; \left\lfloor \dfrac{\,n^k \bmod (2n)^{\,i+1}}{(2n)^i} \right\rfloor.\]

Because $n$ is odd, one can show \[n^k \bmod (2n)^{\,i+1} \;\ge\; n^{\,i+1},\] which implies \[a_i \;\ge\; \left\lfloor \dfrac{n^{\,i+1}}{(2n)^i} \right\rfloor \;=\; \left\lfloor \dfrac{n}{2^i} \right\rfloor \;\ge\; 2^{\,k-1-i} \left\lfloor \dfrac{n}{2^{\,k-1}} \right\rfloor.\]

As $n$ grows large, $\bigl\lfloor n / 2^{\,k-1}\bigr\rfloor$ becomes arbitrarily big, so each digit $a_i$ eventually exceeds any fixed $d.$ Hence there exists an integer $N$ such that for all odd $n > N,$ the digits $a_i$ in the base-$(2n)$ representation of $n^k$ are all $> d.$ This completes the proof. ~Rex

See Also

2025 USAMO (Problems • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
2025 USAJMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
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

Senor Akash Tuff in the Hood!

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_USAMO_Problems/Problem_1&oldid=261850"