AoPS Academy
+1 w
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 .
and be positive integers with 
. Let 
be a polynomial of degree with real coefficients, nonzero constant term, and no repeated roots. Suppose that for any real numbers 
such that the polynomial 
divides , the product 
is zero. Prove that has a nonreal root.
and 
in the plane and a subset 
of the plane, which are announced to Bob. Next, Bob marks infinitely many points in the plane, designating each a city. He may not place two cities within distance at most one unit of each other, and no three cities he places may be collinear. Finally, roads are constructed between the cities as follows: for each pair 
of cities, they are connected with a road along the line segment 
if and only if the following condition holds:
distinct from 
and 
, there exists 
such[/center]
is directly similar to either 
or 
.[/center]
is directly similar to 
if there exists a sequence of rotations, translations, and dilations sending 
to 
, 
to 
, and 
to 
.
be the orthocenter of acute triangle 
, let 
be the foot of the altitude from to , and let be the reflection of across 
. Suppose that the circumcircle of triangle 
intersects line at two distinct points and . Prove that is the midpoint of 
. such that ![\[\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k\]](http://latex.artofproblemsolving.com/3/c/5/3c5984d0003c1ca2df2e68841dd9e93ed6c2d27c.png)
is an integer for every positive integer .
and be positive integers with 
. There are cupcakes of different flavors arranged around a circle and people who like cupcakes. Each person assigns a nonnegative real number score to each cupcake, depending on how much they like the cupcake. Suppose that for each person , it is possible to partition the circle of cupcakes into groups of consecutive cupcakes so that the sum of 's scores of the cupcakes in each group is at least 
. Prove that it is possible to distribute the cupcakes to the people so that each person receives cupcakes of total score at least with respect to .
and first digit is 
) are of the form
where 
, 
, and 
. (
change on the choice of 
)
wins.
and 
as the first 
digits of base . Notice that the 
th digit of base is simply 
.
, which has a minimum value of 
as is odd.
.
, 
, and for our hypothesis to be true, 
. Since the left hand side is integer, it is minimized when it is equal to 
. After some minimal computation, we find this to be true.
have base- representation of![\[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 
. We'll show that there exists a positive integer such that for all 
, 
for all . In short, we are adding possible leading zeroes to the base- representation.
. Let 
, read the reduction of 
denote the integer in 
such that 
. Then the digit 
of will largely decided by 
. Since 
, 
. Since is odd, the reduction is not zero, so it is at least 
.![\[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 
. We are done.
, but in my induction, I said that every digit is one of four forms, and this would mean 
implies that 
is of the form 
, which it obviously isn't, since 
doesn't have an inverse mod 
. However, is much larger than 
, so this doesn't ruin the 
thing, or anything else really, but I'm not sure if this will get 0-2 or 5/6 now.
is odd, then 
eventually has digits all greater than in base . The base case 
is trivial.
be odd such that 
. Notice ![\[ 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.
; then the -th digit of in base is 
and we are done
th digit from the right of in base- is 
For the sake of a contradiction, assume that there is an such that 
Then 
since is odd. Note that as gets arbitrarily large, will have digits in base-
Therefore, 
a contradiction for all arbitrarily large 
QED
suffices. in base be 
. Then let 
be equal to 
, which represents the last digits. Therefore:![\[ d_i = \frac{a_{i + 1} - a_i}{(2n)^i} \]](http://latex.artofproblemsolving.com/7/2/1/7211cd13783b761459d6301aa9165d194e8db88d.png)
Now as 
, is a multiple of 
, so 
. Moreover as is odd, 
, so 
. Define 
, which are all integers by the previous. In particular, we have 
, where the upper bound follows because 
. We have:![\[ 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 has at most digits in base , which means that the only values of we care about are 
.
as it could have atmost digits because the geometric sum of this would led to a term of (2n)^k so if there were 
terms then automatically it would exceed ,but for sufficiently large we can assume it to be atmost digits. ,so every time you would come up :
, so here we want to it to be = because of the perfect power condition at left hand side, hence \documentclass{article}![\[
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)
.
,
.
and 
to be the remainder when 
is divided by 
.
and 
is odd for 
.
or an equivalent formulation. To prove this construction works, we need to show that
and 
inclusive.
is divided by 
.
,
since it telescopes.
,![\[\frac{r_{i+1} n - r_i}{2^i} > \frac{r_{i+1} n}{2^i} - 1 \geq \frac{n}{2^i} - 1 \geq \frac{n}{2^k} - 1.\]](http://latex.artofproblemsolving.com/4/2/0/420d26b6099ca264846885e7eef23b2c9c7b2dd0.png)
Thus, each digit is lower bounded by 
,
fails.
,
such that 
has no nonreal roots. We can also assume 
case is trivial as the constant term must be nonzero, so fix 
.
.
.
which has the 
for all integers 
.
be the coefficient of the 
term of 
for all 
,
for which 
.
and 
.
and 
.
term in 
and 
.
,
.
,
has 
distinct real roots as well, along with two consecutive nonleading coefficients equal to zero, but one degree lower, by the Power Rule. By doing this repeatedly, we eventually end up with a polynomial where the two consecutive coefficients have degree 
,
to be the set of points strictly outside the circle with diameter 
.
is always acute. Suppose two roads 
and 
cross. Then, 
is a convex quadrilateral. Since 
.
is not acute but there does not exist an 
such that 
are connected by some path. This is trivially true for 
,
are also connected.
is obtuse, we have 
.
,
,
is not mentioned. Do not reward points if the induction argument is incomplete or incorrect.
be the center of 
.
be the intersection of 
and the line through 
,
.
be the foot of the altitude from 
and 
,
is a midline and thus 
.
is a midline of 
,
and thus 
.
(by definition), by either HL congruence or the Pythagorean theorem, we must have 
.
.
and 
to attempt to identify 
.
or 
,
.
.
is divisible by 
,
be a prime power dividing 
.
.
,
if 
and 
otherwise, so for each term, either both the numerator are divisible by 
,
,
,
.
has an inverse modulo 
.![\[\binom ni \equiv \pm 1 \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor} \pmod{p^a}.\]](http://latex.artofproblemsolving.com/0/1/c/01c00beb6efc07ed028fd0273f262b8bfb965d33.png)
modulo 
.
,![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (\pm 1)^k \equiv p \equiv 0 \pmod p.\]](http://latex.artofproblemsolving.com/2/e/c/2ececb6afa8a10e116056cdc57a6c948298d0c29.png)
where 
,
satisfies the induction hypothesis for the prime 
.![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (\pm 1)^k \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv p\sum_{i=0}^d \binom di^k \pmod {p^a}\]](http://latex.artofproblemsolving.com/6/c/9/6c9a4b6aac62b1befef1511451c9fa30993d2cf7.png)
By the induction hypothesis, 
divides the inner binomial sum, so since we are multiplying it by 
.
.
is incorrect, reward up to 
points total.
between the set of people except Evan 
if the total score of the cupcakes in that bubble with respect to 
.
denotes the set of neighbors of 
people.
.
from the graph, noting that no person in 
.
is the units digit. Obviously, 
for all 
,
.
for each 
,![\[ 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 
and 2)
.![\[ 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 such that 
.
for 
and let 
.
is an integer because 
.
t
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 
for all 
.
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 
,
,
,
in my solution
,![\[
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 
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 
.
(if it exists) to be the minimum positive integer such that for every odd integer 
,
,
,
exists for any positive integer 
.
,
for 
,
exists for all 
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.