|
|
| (One intermediate revision by the same user not shown) |
| Line 71: |
Line 71: |
| | This completes the proof. | | This completes the proof. |
| | ~Rex | | ~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>. If the digits increase as <math>n</math> does, then if we pick a large enough <math>N=2x+1</math>, such that the digits of <math>2x+3</math> in base <math>4x+6</math> are bigger than <math>d</math> we are done. 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== | | ==See Also== |
Latest revision as of 16:28, 19 August 2025
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 
to be the remainder when 
is divided by 
.
Also, let 
be the usual floor function.
Representation:
![\[n^k \;=\; a_{k-1}\,(2n)^{k-1} \;+\; a_{k-2}\,(2n)^{k-2} \;+\;\dots\;+\;a_1\,(2n)\;+\;a_0,\]](http://latex.artofproblemsolving.com/7/9/4/79418ecf275ab03231a42da3a05fc978c4c48fb5.png)
where each 
satisfies 
Hence, the base-
![\[a_{k-1} \;=\; \left\lfloor \dfrac{n^k}{(2n)^{k-1}} \right\rfloor \;=\; \left\lfloor \dfrac{n}{2^{k-1}} \right\rfloor.\]](http://latex.artofproblemsolving.com/2/c/a/2cacdbe674787eac6e683b68e4a8611bd0ecb39d.png)
![\[a_i \;=\; \left\lfloor \dfrac{\,n^k \bmod (2n)^{\,i+1}}{(2n)^i} \right\rfloor.\]](http://latex.artofproblemsolving.com/a/f/e/afe3bfe3ee70842b0f93d87d221568e0e175e22d.png)
is odd, one can show
![\[n^k \bmod (2n)^{\,i+1} \;\ge\; n^{\,i+1},\]](http://latex.artofproblemsolving.com/9/3/d/93dc192a9d2b0cc4c4f12dcab963392cd9b1cb63.png)
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.\]](http://latex.artofproblemsolving.com/2/7/8/27849ba410056c26ae3687e20b9b88a75e4c35cd.png)
becomes arbitrarily big, so each digit 
Hence there exists an integer 
the digits 
This completes the proof.
~Rex
