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 USAMO Problems/Problem 1"

(→‎Solution)
Line 1: Line 1:
 
{{duplicate|[[2025 USAMO Problems/Problem 1|2025 USAMO #1]] and [[2025 USAJMO Problems/Problem 2|2025 USAJMO #2]]}}
 
{{duplicate|[[2025 USAMO Problems/Problem 1|2025 USAMO #1]] and [[2025 USAJMO Problems/Problem 2|2025 USAJMO #2]]}}
 
__TOC__
 
__TOC__
 +
  
 
== Problem ==
 
== 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>.
 
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==
 +
 +
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>
 +
where <math>x \bmod y</math> is the remainder of <math>x</math> when divided by <math>y.</math>
 +
 +
Because <math>n</math> is odd, one can show
 +
<cmath>
 +
n^k \bmod (2n)^{\,i+1}
 +
\;\ge\;
 +
n^{\,k-i-1},
 +
</cmath>
 +
which implies
 +
<cmath>
 +
a_i
 +
\;\ge\;
 +
\left\lfloor
 +
\dfrac{n}{2^i}
 +
\right\rfloor
 +
\;\ge\;
 +
2^{\,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
  
 
==See Also==
 
==See Also==

Revision as of 11:59, 29 March 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

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,\] where $x \bmod y$ is the remainder of $x$ when divided by $y.$

Because $n$ is odd, one can show \[n^k \bmod (2n)^{\,i+1} \;\ge\; n^{\,k-i-1},\] which implies \[a_i \;\ge\; \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

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