AoPS Academy
be a positive integer, and let 
be nonnegative integers such that 
Prove that![\[
\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}.
\]](http://latex.artofproblemsolving.com/c/4/9/c49d0ccfef69402d05dc44d721172498c605cf7e.png)
Note: 
for all nonnegative integers 
.
+2 w
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 
.
+2 w
be the set of integers, and let 
be a function. Prove that there are infinitely many integers 
such that the function 
defined by 
is not bijective. is bijective if for every integer 
, there exists exactly one integer 
such that 
.
lie on a circle 
and point lies outside the circle. The given points are such that (i) lines 
and 
are tangent to , (ii) 
are collinear, and (iii) 
. Prove that 
bisects 
.
and 
are chosen uniformly and independently at random on sides 
and 
respectively, of equilateral triangle 
Which of the following intervals contains the probability that the area of 
is less than half the area of 
![$\textbf{(A) } \left[\frac 38, \frac 12\right] \qquad \textbf{(B) } \left(\frac 12, \frac 23\right] \qquad \textbf{(C) } \left(\frac 23, \frac 34\right] \qquad \textbf{(D) } \left(\frac 34, \frac 78\right] \qquad \textbf{(E) } \left(\frac 78, 1\right]$](http://latex.artofproblemsolving.com/5/8/7/5874157b23f9d385f707b696eee3d0780fd8a45b.png)
such that 
is an integer for every positive integer 
be a set of integers with the following properties:
.
and 
, then 
.
, 
is composite, then all positive divisors of are in . contains all positive integers.
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 
, tet 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?
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:Note that the numerator is a positive multiple of , since 1) and 2) is odd) . Thus,which is true since and . for each would still show that exists even tho the sol was already sufficient assuming that anyway? (for this one, in other words, do the graders actually care about an unnecessary/slightly off sentence I wrote after a solution that would've probably gotten a 7?)
. Define 
and 
to be the remainder when 
is divided by 
. Notice that 
and 
is odd for 
. Then, we claim that ![\[n^k = \sum_{i=1}^k \left(\frac{r_i n - r_{i-1}}{2^{i-1}}\right) \cdot (2n)^{i-1}.\]](http://latex.artofproblemsolving.com/f/0/c/f0c355fcbb56f4618d249ed1bd891de5f69b4064.png)
Indeed, notice that this sum equals 
since it telescopes. Now notice by definition of 
, each coefficient of 
is an integer. Also, since 
, each coefficient is between 
and 
. Thus, the above sum is simply a base- representation of .
, we have ![\[\frac{r_i n - r_{i-1}}{2^{i-1}} > \frac{r_i n}{2^{i-1}} - 1 \geq \frac{n}{2^{i-1}} - 1.\]](http://latex.artofproblemsolving.com/9/b/9/9b958a38b460bfbbe7a02ecf54b9f0d909adb9e6.png)
Clearly, as becomes arbitrarily large, the lower bound of each digit becomes arbitrarily large as well.
We start with the following:
we have 
The base case 
is because 
Now for the inductive step, we have
Plugging this into the inductive hypothesis completes the induction.
in the above claim gives 
Every term to the left of the rightmost term is an integer, so the rightmost term is also an integer. However, since 
for all 
it must be 
This gives us 
We have 
since 
for all 
Thus the boxed equation gives the unique base representation of 
is an odd integer, for all 
The base case 
is trivial as is odd. For the inductive step, we have 
for some odd integer 
so 
This is 
The last term is even for 
and the first term is odd since and 
are odd. This completes the induction.
we have 
so assume 
Then we have
since any odd positive integer is at least 
Therefore, the th digit from the left in the base representation of is at least 
Taking 
finishes.
be the number of digits in when expressed in base 
Note that
Note that 
but 
so for sufficiently large we have that 
Thus, we can just assume that going forward.
be the unique sequence of integers between and 
inclusive such that
Then, let 
be defined as
Note that 
This is obviously true for 
and for 
we have
so
for some integer 
However, we have that 
is odd, 
is even, and 
is nonnegative (would i get pts off for saying positive in contest?), so we have 
(might've accidentally said greater than here) and is an digit base number, we have that 
Then, we have for 
that
so
For sufficiently large we have
If 
we have for sufficiently large 
so the desired result is true for sufficiently large Thus, such an exists, and we are done.
works
has exactly digits.
Also note that 
from the bound This finishes.
where the last equality is since that sum is obviously an integer and the other sum is obviously less than 1.
Now, we can finish.
where the first inequality follows from being odd, and the second follows from 
From the first claim, we have:
representation of has at most digits. had at least 
digits. Then the least value of would be 
( s) 
, which would imply 
which is absurd since is positive.th digit of from the right in base is greater than 
.
. Since we are working in base , the th digit from the right will be equal to 
, where 
is the unique positive integer 
for which 
. 
is defined analogously. Since 
, we have 
so by Chinese Remainder Theorem (note that CRT is applicable since is odd so 
), 
for some 
(
is impossible since then would be even). We are given by definition that 
so: 
as desired.
is sufficient \newline
be the nth digit from the right. Since we have 
and , it follows that 
, so letting 
, we get that 
, as desired.
: We have that 
by telescoping. \newline 
since 
and 
. \newline 
since 
and 
. Therefore, our formula produces the right value as desired. Since there is a unique way to write in base , it remains to prove that each term of this formula is an integer. Since and 
, we have that 
. 
by definition, so 
and 
is an integer, as desired.
, and look at the rightmost 
digits of ; that is, the remainder upon division by 
. We compute it exactly:
be an odd integer, and 
integers. Then ![\[ n^k \bmod{(2n)^i} = c(k,\ell) \cdot n^i \]](http://latex.artofproblemsolving.com/a/b/2/ab2eba15757c8fc8ed876ce5527ab35f356de12b.png)
for some odd integer 
.
being the residue class of 
(which makes sense because was odd). 
th digit from the right to be greater than , it would be enough that ![\[ c(k,\ell) \cdot n^\ell \ge (d+1) \cdot (2n)^{\ell-1}. \]](http://latex.artofproblemsolving.com/b/3/6/b36a942d44a2ab6006740d410cce8b267d13164c.png)
But this inequality holds whenever 
., we find that for all odd ![\[ n \ge (d+1) \cdot 2^{k-1} \]](http://latex.artofproblemsolving.com/a/3/4/a34f34277b69603eca78a4f01801657d0e230f2c.png)
we have that
has digits in base-; and
, the \textsuperscript{th} digit from the right is at least 
is odd per se; we only need that 
.
. by 
shifts it digits right, leaving us with 
It suffices to show that the first digits after the decimal point are all greater than .
, consider a digit in its base representation. When we halve , the digit is replaced by either 
or 
. as 
, and carrying out the column multiplication. In particular, note that since 
, 
is also at most .
for iterations, each of the first digits after the decimal point, while initially , will become in one of the iterations. For each digit, after 
, there are at most 
iterations remaining. Any digit is at least (the floor of) half of its previous value in one iteration, as established in the claim, so after all the iterations, the value of the digit is at least![\[\left \lfloor \frac{n}{2^{k-1}} \right \rfloor \geq \left \lfloor \frac{N}{2^{k-1}} \right \rfloor > d.\]](http://latex.artofproblemsolving.com/e/d/c/edc7830a8c8d9d1c344f561a08a39aa44dceadfe.png)
, 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?
as mod 
(not exactly, but i proved that for my definition of that this is true) and i accidentally said that is positive instead of nonnegative. This does not impact the other steps in my solution.
and it is clear that is odd and is even, so I concluded that since is "positive" (nonnegative), that 
Unfortunately, I may have said greater than instead of greater than or equal to. However, this also does not impact my claim since I had intended to do 
is in fact positive, and my solution kind of made it clear why by doing 
It should be obvious from this... right?
, so 
. Then, the base representation of is in the form 
. Assume FTSOC that 
. Then, 
Taking both sides mod 
, we have 
. However, 
This means, 
Thus, we must have 
. Then, 
. Taking both sides mod gives a contradiction as desired.
is at least 
. We do this by induction on . by . The amount that carries over 
while the amount that stays is or . Note that 
Therefore, the digits after multiplying 
with are less than and at least 
as desired.
suffices.
(for all ). When 
, 
so for all 
there exists sufficiently large such that for all the digits of are greater than . in base are,![\[n^k_{2n} = \overline{a_1a_2\dots a_r}\]](http://latex.artofproblemsolving.com/2/2/a/22a02328957cf19b06acfcefc37ba7c13b37879e.png)
Then,![\[2n^{k+1}_{2n} = \overline{a_1a_2\dots a_r0}\]](http://latex.artofproblemsolving.com/6/7/d/67dc36da18501e5787798236b9ec16341ea92335.png)
are greater than 
then all digits of 
(excluding possibly the last digit) are at least . by . If a digit is even, its halve will be written which must be greater than . If a digit is odd, its halve is written and a carry over of 1 is taken to the next place. Then, the halve of 
will be written in the next place where is the number in this place which is clearly at least if 
. This process continues until the division is complete and it follows that all digits (except possibly the last if the final digit of is odd) will be at least .
, if we pick sufficiently large such that all digits of 
are greater than 
and 
, then all the digits of 
will be greater than (the final digit must be since is odd (as is odd)). Thus, the induction is complete and the result follows.
(for all ). When , so for all there exists sufficiently large such that for all the digits of are greater than . in base are,Then, are greater than then all digits of (excluding possibly the last digit) are at least . by . If a digit is even, its halve will be written which must be greater than . If a digit is odd, its halve is written and a carry over of 1 is taken to the next place. Then, the halve of will be written in the next place where is the number in this place which is clearly at least if . This process continues until the division is complete and it follows that all digits (except possibly the last if the final digit of is odd) will be at least ., if we pick sufficiently large such that all digits of are greater than and , then all the digits of will be greater than (the final digit must be since is odd (as is odd)). Thus, the induction is complete and the result follows.
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.
works. Suppose the 
t
,
.![\[\frac{d+1}{2n}>\left\{\frac{n^k}{(2n)^r}\right\}=\left\{\frac{n^{k-r}}{2^r}\right\}\ge\frac1{2^r}\ge\frac1{2^k},\]](http://latex.artofproblemsolving.com/b/2/b/b2bccf78e0587e7079c171ad41b5bcc0ea415e56.png)
failing at 
does this still work or not
,![\[
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 
happend to be ![\[ \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 
.