Maths Olympiad Prep

Library / /46 of 169

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it United States

Let kk and dd be positive integers. Prove that there exists a positive integer NN such that for every odd integer n>Nn > N, the digits in the base-2n2n representation of nkn^k are all greater than dd.

Solution

Let kk and dd be given positive integers.

Let nn be an odd integer, and consider the base-2n2n representation of nkn^k.

Recall that in base-bb, the digits of a number xx are the coefficients aia_i in the expansion:
x=a0+a1b+a2b2++ambm, x = a_0 + a_1 b + a_2 b^2 + \cdots + a_m b^m,
where 0ai<b0 \leq a_i < b.

We want all digits aia_i in the base-2n2n representation of nkn^k to be greater than dd.

Let us show that for sufficiently large odd nn, this is possible.

First, note that nk<(2n)2n^k < (2n)^2 for large nn (since kk is fixed and nn grows), so the base-2n2n representation of nkn^k will have at most two digits.

Let us write nkn^k in base 2n2n:

Let nk=q2n+rn^k = q \cdot 2n + r, where 0r<2n0 \leq r < 2n.

So the digits are qq and rr.

We want both q>dq > d and r>dr > d.

Let us estimate qq and rr for large nn.

We have:
nk=q2n+r,0r<2n. n^k = q \cdot 2n + r, \quad 0 \leq r < 2n.
So q=nk2nq = \left\lfloor \frac{n^k}{2n} \right\rfloor, r=nkq2nr = n^k - q \cdot 2n.

For large nn, nkn^k is much larger than 2n2n, so qq is large.

Let us check that q>dq > d for large nn:
q=nk2nnk2n1. q = \left\lfloor \frac{n^k}{2n} \right\rfloor \geq \frac{n^k}{2n} - 1.
For large nn, nk2n\frac{n^k}{2n} grows without bound, so q>dq > d for all sufficiently large nn.

Now, r=nkq2nr = n^k - q \cdot 2n.

But rr is the remainder when nkn^k is divided by 2n2n.

We want r>dr > d.

Let us show that for large nn, rr can be made arbitrarily large.

Note that nkn^k modulo 2n2n can be written as follows:

Let nn be odd. Then nkn^k modulo 2n2n is congruent to nkmod2nn^k \bmod 2n.

But nkn^k modulo 2n2n can take values between 00 and 2n12n-1.

For large nn, nkn^k grows rapidly, so the remainder rr cycles through all possible values as nn increases.

But for nn odd and large, nkn^k modulo 2n2n is also odd (since nn is odd, nkn^k is odd), so rr is odd.

Thus, for large odd nn, rr can be made arbitrarily large, and in particular, r>dr > d for all sufficiently large nn.

Therefore, for all sufficiently large odd nn, both digits qq and rr in the base-2n2n representation of nkn^k are greater than dd.

Thus, there exists a positive integer NN such that for every odd integer n>Nn > N, the digits in the base-2n2n representation of nkn^k are all greater than dd.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.