Difference between revisions of "2025 USAMO Problems/Problem 1"
m |
|||
| Line 7: | Line 7: | ||
== Solution == | == Solution == | ||
{{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:36, 23 March 2025
- The following problem is from both the 2025 USAMO #1 and 2025 USAJMO #2, so both problems redirect to this page.
Contents
Problem
Let 
and 
be positive integers. Prove that there exists a positive integer 
such that for every odd integer 
, the digits in the base-
representation of 
are all greater than .
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
[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
| 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. 
