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 2)
 
(9 intermediate revisions by 3 users not shown)
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 ==
+
==Solution 1==
−
{{solution}}
 
−
 
 
−
[hide=LaTeX to AoPS Conversion][b]Original Problem Setup:[/b]
 
−
Define [tex]N_k^d[/tex] (if it exists) to be the minimum positive integer such that for every odd integer [tex]n > N_k^d[/tex], the digits in the base-[tex]2n[/tex] representation of [tex]n^k[/tex] are all greater than [tex]d[/tex].
 
−
 
 
−
[b]Inductive Proof:[/b]
 
−
 
 
−
[i]Base Case: [tex]k=1[/tex][/i]
 
−
[tex](n^1) = (n^1)_{2n}[/tex], so the only digit is [tex]n[/tex]. Taking [tex]n > d[/tex], we establish [tex]N_1^d[/tex] exists for any positive integer [tex]d[/tex].
 
  
−
[i]Inductive Step:[/i]
+
We define a remainder operation <math>\,a \bmod b\,</math> to be the remainder when <math>a</math> is divided by <math>b</math>.  
−
Assume [tex]N_k^d[/tex] exists for all positive integers [tex]d[/tex] at fixed [tex]k[/tex]. Let [tex]d[/tex] be arbitrary. Consider odd [tex]n > \max\{N_k^{2d+2},n\}[/tex]. Then:
+
Also, let <math>\lfloor x\rfloor</math> be the usual floor function.
  
−
[tex]
+
Base-<math>(2n)</math> Representation:
−
n^{k} = a_0 + (2n)^1 a_1 + \cdots + (2n)^x a_x,\ \text{where}\ 2n > a_i > 2d+2
+
<cmath>
−
[/tex]
+
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>
  
−
Since [tex]n \equiv 1 \pmod{2}[/tex], [tex]a_0[/tex] is odd. Then:
+
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>
  
−
[tex]
+
General Digit Formula:
−
n^{k+1} = (2n)^1 \frac{a_0}{2} + (2n)^2 \frac{a_1}{2} + \cdots + (2n)^{x+1} \frac{a_x}{2}
+
For <math>0 \le i < k,</math>
−
[/tex]
+
<cmath>
 +
a_i
 +
\;=\;
 +
\left\lfloor
 +
\dfrac{\,n^k \bmod (2n)^{\,i+1}}{(2n)^i}
 +
\right\rfloor.
 +
</cmath>
  
−
Which expands to:
+
Because <math>n</math> is odd, one can show
−
[tex]
+
<cmath>
−
= \sum_{i=0}^{x+1} b_i (2n)^i
+
n^k \bmod (2n)^{\,i+1}
−
[/tex]
+
\;\ge\;
−
where:
+
n^{\,i+1},
−
- [tex]b_0 = n[/tex]
+
</cmath>
−
- [tex]b_{x+1} = \lfloor \frac{a_x}{2} \rfloor[/tex]
+
which implies
−
- [tex]b_i = 2n \{\frac{a_i}{2}\} + \lfloor \frac{a_{i-1}}{2} \rfloor\ \text{for}\ 0 < i < x+1[/tex]
+
<cmath>
 +
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.
 +
</cmath>
  
−
From bounds on [tex]a_i[/tex], we get [tex]2n > b_i > d[/tex], proving [tex]N_{k+1}^d[/tex] exists for all [tex]d[/tex]. [/hide]
+
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==

Latest revision as of 16:28, 19 August 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

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