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

(Solution)
Line 4: Line 4:
 
== 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}}
 
 
[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]
 
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:
 
 
[tex]
 
n^{k} = a_0 + (2n)^1 a_1 + \cdots + (2n)^x a_x,\ \text{where}\ 2n > a_i > 2d+2
 
[/tex]
 
 
Since [tex]n \equiv 1 \pmod{2}[/tex], [tex]a_0[/tex] is odd. Then:
 
 
[tex]
 
n^{k+1} = (2n)^1 \frac{a_0}{2} + (2n)^2 \frac{a_1}{2} + \cdots + (2n)^{x+1} \frac{a_x}{2}
 
[/tex]
 
 
Which expands to:
 
[tex]
 
= \sum_{i=0}^{x+1} b_i (2n)^i
 
[/tex]
 
where:
 
- [tex]b_0 = n[/tex]
 
- [tex]b_{x+1} = \lfloor \frac{a_x}{2} \rfloor[/tex]
 
- [tex]b_i = 2n \{\frac{a_i}{2}\} + \lfloor \frac{a_{i-1}}{2} \rfloor\ \text{for}\ 0 < i < x+1[/tex]
 
 
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]
 
  
 
==See Also==
 
==See Also==

Revision as of 05:37, 23 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$.

See Also

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