AoPS Academy
to 
can be split into 
pairs such that for each pair, the greater number is at least 
times the smaller number?
![\[ \dots, \; P_{-3}, \; P_{-2},\; P_{-1},\; P_0,\; P_1,\; P_2,\; P_3,\; \dots \]](http://latex.artofproblemsolving.com/a/c/c/acc097f524dc9fe9bd85e8eb659ea4a75aec475d.png)
in the plane with the following property: For any three distinct integers 
and 
, points 
, 
, and 
are collinear if and only if 
.
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 .
is 
. Begin by letting 
be the digit at the 
th position from the right (0-indexed) of in base ; i.e., 
is the units digit. Obviously, 
for all 
, since 
. We WTS 
for each 
, and observe the following:![\[ a_i=\left\lfloor\frac{n^k}{(2n)^i}\right\rfloor\text{ mod }2n=\left\lfloor\frac{n^{k-i}}{2^i}\right\rfloor\text{ mod }2n=\left\lfloor\frac{n^{k-i}\text{ mod }2^{i+1}n}{2^i}\right\rfloor. \]](http://latex.artofproblemsolving.com/8/e/e/8eee4210547c4be6b66528e10094e1967e0025a2.png)
Note that the numerator is a positive multiple of 
, since 1) 
and 2) is odd) 
. Thus,![\[ a_i=\left\lfloor\frac{n^{k-i}\text{ mod }2^{i+1}n}{2^i}\right\rfloor>d \quad\iff\quad n^{k-i}\text{ mod }2^{i+1}n\ge n\ge2^i(d+1), \]](http://latex.artofproblemsolving.com/b/0/0/b0054af59102b038afc55f886fb6ed3b81faed15.png)
which is true since 
and 
. 
works. be an odd integer and let 
be the number of digits of when written in base . Clearly we have 
. For 
, let integer 
be such that 
. Let 
for 
and let 
. Note that 
is an integer because 
. Also, is the 
th digit (counting from the right) of when written in base , because 
and![\[
\sum_{i=0}^{m-1}s_i(2n)^i=r_1+\sum_{i=1}^{m-1}(r_{i+1}-r_i)=r_m=n^k.
\]](http://latex.artofproblemsolving.com/e/9/7/e9711b83d9f885bbdf641d3bb411d6fdfc660ce4.png)
It suffices to prove that 
for all .
since is odd. Hence 
for all . Fix 
. Since 
it follows that![\[
s_i\equiv\frac{r_{i+1}-r_i}{(2n)^i}+\frac{n^k-r_{i+1}}{(2n)^i}\equiv\frac{n^k-r_i}{(2n)^i}\pmod{2n}.
\]](http://latex.artofproblemsolving.com/f/a/a/faa14e97eae8b8d2e1dce4541a6dae93b78e27a9.png)
Then 
so 
since 
is positive. Thus 
, as desired. 
, but annoyingly I said that 
, which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
, but annoyingly I said that , which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
in my solution
, but annoyingly I said that , which is incorrect, and that probably messed up the rest of my proof that used floors and whatever. How many points would that be?
,![\[
n^k = \frac{f_{k-1}}{2^{k-1}} (2n)^{k-1} + \dots + \frac{f_1}{2} \cdot (2n) + f_0
\]](http://latex.artofproblemsolving.com/4/9/b/49b0a5749adf798fa3df4da0b3544fa7b330535f.png)
where 
are nonconstant linear integer polynomials such that 
with 
for large 
)
where 
,
,
.
)
wins.
and 
just works because if the rightmost digit 
happend to be 
then:![\[ \frac{d+1}{2n}> \left\{ \frac{n^k}{(2n)^r} \right\}=\left\{\frac{n^{k-r}}{2^r} \right\}>\frac{1}{2^r} \ge \frac{1}{2^k} \]](http://latex.artofproblemsolving.com/5/5/7/5572eb11d74cf3ce8cf4bc066983a26bf0b8ce2f.png)
Which happens only when 
and thus we are done 
.
as the first 
digits of 
t
.
,
as 
.
,
,
.
.
![\[n^k=d_{k-1}(2n)^{k-1}+d_{k-2}(2n)^{k-2}+\ldots+d_1(2n)+d_0\]](http://latex.artofproblemsolving.com/1/5/7/157a1a1f2fa26cf40e766a5260561333287d0743.png)
where 
for all 
,
for all 
.
,
denote the integer in 
such that 
.
of 
.
,
.
.![\[n^{i+1}\le d_i(2n)^i+d_{i-1}(2n)^{i-1}+\dots+d_1(2n)+d_0<(d_i+1)(2n)^i=(d_i+1)2^in^i\]](http://latex.artofproblemsolving.com/b/1/4/b1441e60379275ac19c29315421e3451cbb854e6.png)
which rearranges to 
.
,
implies that 
is of the form 
,
doesn't have an inverse mod 
.
,
thing, or anything else really, but I'm not sure if this will get 0-2 or 5/6 now.
(if it exists) to be the minimum positive integer such that for every odd integer 
,
,
,
exists for any positive integer 
.
,
for 
,
exists for all 
is odd, then 
eventually has digits all greater than 
be odd such that 
.![\[ cn^k = (2n)^{k-1} \cdot \frac{cn - r}{2^{k-1}} + rn^{k-1}. \]](http://latex.artofproblemsolving.com/0/b/3/0b31e8abbba984be43ad74bcd106e141978cd98a.png)
Clearly 
is eventually greater than 
(and also hence positive), so as the set of possible 
is finite we are done by induction.
;
and we are done
For the sake of a contradiction, assume that there is an 
Then 
since 
a contradiction for all arbitrarily large 
QED
for all positive 
.
.
.
in base 
by multiplying 
in base 
,
base 
.
.
when ![\[n^{k+1} = \overline{c_m r_m} + \overline{c_{m-1} r_{m-1} 0} + \overline{c_{m-2} r_ {m-2} 00} + \dots\]](http://latex.artofproblemsolving.com/8/2/d/82dc6d83eb9a13536fb12e83a5b61ce6ea61ba4b.png)
,![\[n^{k+1} = \overline{c_1 (c_2 + r_1) (c_3 + r_2) (c_4 + r_3) \dots (c_m + r_{m-1}) r_m}\]](http://latex.artofproblemsolving.com/c/c/c/ccc5a6e3f24d33e6736b8d7cab5720aa2ae6cdde.png)
since 
.
for some 
by the inductive hypothesis so we are done.
ensures each digit is at least 
as desired.
suffices.
.
,![\[ d_i = \frac{a_{i + 1} - a_i}{(2n)^i} \]](http://latex.artofproblemsolving.com/7/2/1/7211cd13783b761459d6301aa9165d194e8db88d.png)
Now as 
,
,
.
,
.
,
,
.![\[ d_i = \frac{a_{i + 1} - a_i}{(2n)^i} = \frac{n^{i + 1}b_{i + 1} - n^ib_i}{2^in^i} = \frac{nb_{i + 1} - b_i}{2^i} \ge \frac{n(1) - 2^i}{2^i} \]](http://latex.artofproblemsolving.com/6/6/2/6623cdac4a0bbb344c5bc1fb6176721fdf53a403.png)
However, for 
:![\[ d_i \ge \frac{n(1) - 2^i}{2^i} \ge \frac{(d + 1)2^{k - 1} - 2^i}{2^i} \ge \frac{d2^{k - 1}}{2^i} \ge d \]](http://latex.artofproblemsolving.com/9/2/a/92ae0cf0b068e52baf68f4db4e5937b750c60302.png)
because 
.
as it could have atmost 
terms then automatically it would exceed 
,![\[
a_i = \left\lfloor \frac{n}{2^{i-1}} \right\rfloor \quad \text{for } i = 1, 2, \dots, k.
\]](http://latex.artofproblemsolving.com/b/7/7/b775d74b02ba46830f4cd92b53bafe8e0b1a048b.png)
![\[
a_2 > a_3 > \dots > a_k > d.
\]](http://latex.artofproblemsolving.com/b/1/5/b15ee7bead67c2be07c4b61a4413444218cc2ed4.png)
![\[
\left\lfloor \frac{n}{2^{k-1}} \right\rfloor > d.
\]](http://latex.artofproblemsolving.com/f/c/0/fc0d82a30c110c2fd9d2a03725455dde00e7582b.png)
![\[
\frac{n}{2^{k-1}} > d \quad \Rightarrow \quad n > 2^{k-1} \cdot d.
\]](http://latex.artofproblemsolving.com/e/b/1/eb1d94f5ca464f714a63553b9577274b0c15ef34.png)
![\[
n \geq 2^{k-1} \cdot (d + 1).
\]](http://latex.artofproblemsolving.com/5/3/7/537d503598a55d86a8ee35fadebd3092899f86d9.png)
is:![\[
n = 2^{k-1} \cdot (d + 1),
\]](http://latex.artofproblemsolving.com/0/e/a/0ea9afcdca180ff2d82507ee97191422dbb307b0.png)
which guarantees:![\[
\left\lfloor \frac{n}{2^{k-1}} \right\rfloor \geq d + 1 > d.
\]](http://latex.artofproblemsolving.com/c/1/d/c1dd4f3d372ecc40d933e836ee51603f2a5504ca.png)