2025 USAMO Problems/Problem 1

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

Solution 2

We first make some notes. Let's figure out how many digits are in the conversion using the formula for number of digits in a different base. $\lfloor \log_{2n}(n^k) \rfloor +1 = \lfloor k\log_{2n}(n)\rfloor +1=\lfloor k(1-\log_{2n}(2)) \rfloor +1$ . Note that for a sufficiently large $n$ , $\log_{2n}(2)$ is a little bigger than $0$ , so $1-\log_{2n}(2)$ is a little less than $1$ , so $k(1-\log_{2n}(2)$ is a little less than $k$ so it's floor is $k-1$ . So the number of digits is $k-1+1=k$ for a sufficiently large $n$ .

Next the last digit is $n^k$ mod $2n$ . Note that $n^k - n\equiv n(n^{k-1}-1)$ . We know that since $n$ is odd, $n^{k-1}-1$ is even. So $n(n^{k-1}-1)\equiv 0$ mod $2n$ since it's even and divisible by $n$ . So $n^k - n \equiv 0$ and $n^k \equiv n$ mod $2n$ , so the last digit will always be $n$ .

We present a proof by induction on $k$ :

Base case $k=1$ : We have $n^1$ in base $2n$ . Clearly this will just be $n_{2n}$ and as $n$ increases, so does each of the digits in the conversion of $n^1$ to base $2n$ . Since the digits increase larger and larger boundlessly as $n$ does, there must exist some $N$ large enough.

Inductive Step: We will assume the digits grow with $n$ for $n^{p-1}$ and we will prove it for $n^p$ We want to convert $n^p$ to base $2n$ . We know the last digit is $n$ and we know it's $p$ digits long. So if $a$ is $p-1$ digits long, our conversion is $\overline{an}$ . We know $a=\frac{n^p-n}{2n}=\frac{n^{p-1}-1}{2}$ . Thus, $a$ is the previous number of $n$ for $k=p-1$ but subtracting $1$ and halving. We take our previous for $k=p-1$ and we know it ends in $n$ . When we subtract $1$ it ends in $n-1$ : an even number since $n$ is odd. Now it ends in an even number and each digit is odd or even, but each digit $\leq 2n-1$ . Now we do the following to convert each digit into an even digit. If we have an odd digit, subtract $1$ from this digit, and add $2n$ to the digit to it's right. There must always be a digit to it's right since the rightmost digit is even. This process turns every odd number into an even number, and keeps every even number as even since adding $2n$ won't change if a number is odd or even. Now we half every digit. Each digit was $\leq 2n-1$ , then we added $2n$ making each digit $\leq 4n-1$ , so after halving, each digit will still be $\leq 2n-1$ , and we will be done. If a digit increases as $n$ increases and we add $2n$ , it'll still increase as $n$ increases. If a digit increases as $n$ increases and we halve it, it'll still increase as $n$ increases. If a digit increases as $n$ increases and we subtract $1$ , it'll still increase as $n$ increases. So all our digits, no matter what we did to them will still increase as $n$ increases.

~Math645

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

Page

Toolbox

Search

2025 USAMO Problems/Problem 1

Contents

Problem

Solution 1

Solution 2

See Also