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

Latest revision as of 23:23, 19 July 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

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

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

Latest revision as of 23:23, 19 July 2025

Contents

Problem

Solution 1

Solution 2

See Also

@@ Line 1: / Line 1: @@
 {{duplicate|[[2025 USAMO Problems/Problem 1|2025 USAMO #1]] and [[2025 USAJMO Problems/Problem 2|2025 USAJMO #2]]}}
 __TOC__
 == Problem ==
 Let <math>k</math> and <math>d</math> be positive integers. Prove that there exists a positive integer <math>N</math> such that for every odd integer <math>n>N</math>, the digits in the base-<math>2n</math> representation of <math>n^k</math> are all greater than <math>d</math>.
-== Solution ==
+==Solution 1==
-{{solution}}
+We define a remainder operation <math>\,a \bmod b\,</math> to be the remainder when <math>a</math> is divided by <math>b</math>.
+Also, let <math>\lfloor x\rfloor</math> be the usual floor function.
+Base-<math>(2n)</math> Representation:
+<cmath>
+n^k \;=\; a_{k-1}\,(2n)^{k-1} \;+\; a_{k-2}\,(2n)^{k-2} \;+\;\dots\;+\;a_1\,(2n)\;+\;a_0,
+</cmath>
+where each <math>a_i</math> satisfies <math>0 \le a_i < 2n.</math>
+Hence, the base-<math>(2n)</math> representation of <math>n^k</math> is <math>a_{k-1}\,a_{k-2}\,\dots\,a_1\,a_0.</math>
+Leading Digit:
+<cmath>
+a_{k-1}
+\;=\;
+\left\lfloor
+\dfrac{n^k}{(2n)^{k-1}}
+\right\rfloor
+\;=\;
+\left\lfloor
+\dfrac{n}{2^{k-1}}
+\right\rfloor.
+</cmath>
+General Digit Formula:
+For <math>0 \le i < k,</math>
+<cmath>
+a_i
+\;=\;
+\left\lfloor
+\dfrac{\,n^k \bmod (2n)^{\,i+1}}{(2n)^i}
+\right\rfloor.
+</cmath>
+Because <math>n</math> is odd, one can show
+<cmath>
+n^k \bmod (2n)^{\,i+1}
+\;\ge\;
+n^{\,i+1},
+</cmath>
+which implies
+<cmath>
+a_i
+\;\ge\;
+\left\lfloor
+\dfrac{n^{\,i+1}}{(2n)^i}
+\right\rfloor
+\;=\;
+\left\lfloor
+\dfrac{n}{2^i}
+\right\rfloor
+\;\ge\;
+^{\,k-1-i}
+\left\lfloor
+\dfrac{n}{2^{\,k-1}}
+\right\rfloor.
+</cmath>
+As <math>n</math> grows large,
+<math>\bigl\lfloor n / 2^{\,k-1}\bigr\rfloor</math>
+becomes arbitrarily big, so each digit <math>a_i</math> eventually exceeds any fixed <math>d.</math>
+Hence there exists an integer <math>N</math> such that for all odd <math>n > N,</math> the digits <math>a_i</math> in the base-<math>(2n)</math> representation of <math>n^k</math> are all <math>> d.</math>
+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. <math>\lfloor \log_{2n}(n^k) \rfloor +1 = \lfloor k\log_{2n}(n)\rfloor +1=\lfloor k(1-\log_{2n}(2)) \rfloor +1</math>. Note that for a sufficiently large <math>n</math>, <math>\log_{2n}(2)</math> is a little bigger than <math>0</math>, so <math>1-\log_{2n}(2)</math> is a little less than <math>1</math>, so <math>k(1-\log_{2n}(2)</math> is a little less than <math>k</math> so it's floor is <math>k-1</math>. So the number of digits is <math>k-1+1=k</math> for a sufficiently large <math>n</math>.
+Next the last digit is <math>n^k</math> mod <math>2n</math>. Note that <math>n^k - n\equiv n(n^{k-1}-1)</math>. We know that since <math>n</math> is odd, <math>n^{k-1}-1</math> is even. So <math>n(n^{k-1}-1)\equiv 0</math> mod <math>2n</math> since it's even and divisible by <math>n</math>. So <math>n^k - n \equiv 0</math> and <math>n^k \equiv n</math> mod <math>2n</math>, so the last digit will always be <math>n</math>.
+We present a proof by induction on <math>k</math>:
+Base case <math>k=1</math>: We have <math>n^1</math> in base <math>2n</math>. Clearly this will just be <math>n_{2n}</math> and as <math>n</math> increases, so does each of the digits in the conversion of <math>n^1</math> to base <math>2n</math>. Since the digits increase larger and larger boundlessly as <math>n</math> does, there must exist some <math>N</math> large enough.
+Inductive Step: We will assume the digits grow with <math>n</math> for <math>n^{p-1}</math> and we will prove it for <math>n^p</math> We want to convert <math>n^p</math> to base <math>2n</math>. We know the last digit is <math>n</math> and we know it's <math>p</math> digits long. So if <math>a</math> is <math>p-1</math> digits long, our conversion is <math>\overline{an}</math>. We know <math>a=\frac{n^p-n}{2n}=\frac{n^{p-1}-1}{2}</math>. Thus, <math>a</math> is the previous number of <math>n</math> for <math>k=p-1</math> but subtracting <math>1</math> and halving. We take our previous for <math>k=p-1</math> and we know it ends in <math>n</math>. When we subtract <math>1</math> it ends in <math>n-1</math>: an even number since <math>n</math> is odd. Now it ends in an even number and each digit is odd or even, but each digit <math>\leq 2n-1</math>. Now we do the following to convert each digit into an even digit. If we have an odd digit, subtract <math>1</math> from this digit, and add <math>2n</math> 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 <math>2n</math> won't change if a number is odd or even. Now we half every digit. Each digit was <math>\leq 2n-1</math>, then we added <math>2n</math> making each digit <math>\leq 4n-1</math>, so after halving, each digit will still be <math>\leq 2n-1</math>, and we will be done. If a digit increases as <math>n</math> increases and we add <math>2n</math>, it'll still increase as <math>n</math> increases. If a digit increases as <math>n</math> increases and we halve it, it'll still increase as <math>n</math> increases. If a digit increases as <math>n</math> increases and we subtract <math>1</math>, it'll still increase as <math>n</math> increases. So all our digits, no matter what we did to them will still increase as <math>n</math> increases.
+~Math645
 ==See Also==