AoPS Academy
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 .
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 
is an integer for every positive integer 
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 .
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 
.
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 .
be a set of integers with the following properties:
.
and 
, then 
.
, 
is composite, then all positive divisors of are in . contains all positive integers.
such that is an integer for every positive integer
fail: Just take 
and get 
is divisible by 
which implies 
This can only happen if is even. work: Substitute 
in place for in the problem; we then must prove that 
is an integer for all positive integers Call -good if satisfies this condition. Letting 
denote the number of not necessarily distinct prime factors of 
we will prove that all positive integers are -good by induction on 
The base case is trivial since if 
then 
which vacuously works. such that 
Let the prime factorization of be 
where 
are distinct primes and 
such that 
We will show that 
for all 
which finishes the inductive step by CRT.
so 
If 
then 
as well since 
Thus 
has a modular inverse modulo 
so we can say 
because is even. Hence the terms in this product for which 
contribute nothing to the binomial coefficient.
then we have 
Reindexing the product in terms of 
we get 
Therefore, plugging back into our sum gives 
By the inductive hypothesis, the sum on the right-hand side is divisible by 
so the entire sum is divisible by 
This completes our inductive step. are -good, and we are done.
" is 
.
we get 
so clearly is even. is even.
, then 
divides![\[
\sum_{i=0}^n\binom{n}{i}^k.
\]](http://latex.artofproblemsolving.com/2/9/e/29ef574279744f8e99496f7ec1a84b6b2550e5e6.png)
Proof. We proceed by induction on 
with the base case 
trivial.
. Let 
and let us work in 
. Note that if 
is even, 
exists so![\[
\binom{n}{r+1}=\frac{n-r}{r+1}\binom{n}{r}=\frac{2^\alpha m-(r+1)}{r+1}\binom{n}{r}=-\binom{n}{r}.
\]](http://latex.artofproblemsolving.com/a/b/d/abd2cc8dc5612dffb45ca2822f622f487ef31943.png)
We prove that 
for 
by induction on with the base case 
trivial.. We have
completing the induction step.
Since 
, by the induction hypothesis with 
, 
divides![\[
\sum_{r=0}^{n'}\binom{n'}{r}^k.
\]](http://latex.artofproblemsolving.com/5/1/b/51b7c7546b7a7185c3b7be2d20aabc8debbf820f.png)
Thus![\[
\sum_{i=0}^n\binom{n}{i}^k=2\sum_{r=0}^{n'}\binom{n'}{r}^k=0,
\]](http://latex.artofproblemsolving.com/5/7/f/57f07e0144c77a1846ac0753ba534ae4571b3e30.png)
as desired. 
case is the same except there is no 
in the proof. Since all prime powers dividing 
divide 
, divides . case correctly (I wrote a Claim 2 that was basically identical to Claim 1 but modified for odd ). Also by dropping the ^k, I did not induct on in Claim 1 because the last summation (wrongly) becomes 
directly.
? I was in a hurry...
, find all positive integers such that this expression is a positive integer”
is a power of 
and all even positive integers otherwise
doesn't work, and 
works?
. To show that odd doesn't work, just look at . divides ![\[\sum_{i=0}^n \binom ni ^{2k}.\]](http://latex.artofproblemsolving.com/8/4/1/84139da2890840ac8fcb775b99ff1949182e57f8.png)
Pick a prime dividing , and let 
so that 
is the maximal power of dividing . Let 
with 
The key claim is as follows:
, we have that ![\[\sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k} \equiv p\sum_{i=0}^{\left\lfloor \frac{n}{p^{a+1}}\right\rfloor} \binom{n}{ip^{a+1}}^{2k}\bmod{p^{e-a}}\]](http://latex.artofproblemsolving.com/6/4/e/64e09c4d93130ccbac6a28690d36d4998540b31b.png)
![\[\binom{n}{0}^2, \binom{n}{p^a}^2, \dots, \binom{n}{(mp^{e-a}-1)p^a}^2.\]](http://latex.artofproblemsolving.com/e/0/9/e0917119b3286520109182ff9ecadcfb11b0d65b.png)
We claim that these values can be blocked into consecutive groups of such that the values in each block are equal modulo 
. Specifically, for 
, we claim that ![\[\binom{n}{ip^a} \equiv \binom{n}{(i+1)p^a} \pmod p^{e-a}.\]](http://latex.artofproblemsolving.com/c/e/7/ce72cd64480b4e6dc6f526cf6d01ad052720afa8.png)
Indeed, we have that
But for every 
, 
since . Therefore 
, so the entire product is equal to 
; thus the subclaim is true. Therefore we have that
and the claim is proven.![\[p^{e-a} \mid \sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k}\]](http://latex.artofproblemsolving.com/3/e/f/3ef54510be325f6a2cc9e38897d4bdfb0bb283b5.png)
for all 
. Taking 
gives that ![\[p^e \mid \sum_{i=0}^{n} \binom ni^k\]](http://latex.artofproblemsolving.com/2/6/9/2690bac952cb36989e8fa4576042c9e5bfd75a74.png)
for any prime power dividing . This means that ![\[\frac 1{n+1} \sum_{i=0}^n \binom ni^{2k}\]](http://latex.artofproblemsolving.com/9/8/9/989d213c9ec12273fc610b7739378dd28c7876be.png)
is an integer for any 
, so we are done.
(prime exponents are 1)
. Odd fail at .
and set 
. The main idea is that 
Then ![\[\sum_{i=0}^{pm-1}\binom{pm-1}i^k\equiv p\sum_{i=0}^{m-1}\binom{m-1}i^k\pmod{p^{s+1}}\]](http://latex.artofproblemsolving.com/a/8/e/a8ee4173684952aca3735bb1a1bc63a8db2c27a8.png)
so inducting on 
works.
.
for the sum in the problem.
is necessary. Choose . We need 
, which requires to be even.
for prime , since 
. Hence 
, and this also requires to be even. This special case is instructive in figuring out the proof to follow. is sufficient. From now on we treat as fixed, and we let be a prime fully dividing . The basic idea is to reduce from to 
by an induction.
. When 
, we have ![\[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]](http://latex.artofproblemsolving.com/d/4/0/d405c93989cb8c5954041c054416c6e8be3ede52.png)
When 
, the 
terms of 
in order are, modulo , 
The point is that has five copies of 
, modulo . is a prime power which fully divides . Then ![\[ \binom{n}{i} \equiv \pm \binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor} \pmod{p^e}. \]](http://latex.artofproblemsolving.com/5/b/9/5b9bf0fdf09bc4cc62ba09107a7fdfa9f1252d18.png)
Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases 
first.
, since 
, we have ![\[ \binom{n}{i} = \frac{n(n-1) \dots (n-i+1)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \frac{(-1)(-2) \dots (-i)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \pm 1 \pmod{p^e}. \]](http://latex.artofproblemsolving.com/7/2/4/72446f7a23991dbd82dee8b7979f07b4b2efb0aa.png)
we have 
the analogous reasoning gives 
![\[ \binom ni = \prod_{0 \le j \le i} \frac{n-(j-1)}{j} \]](http://latex.artofproblemsolving.com/4/0/2/40265f398831b8703194076e28dccc1a58c1a94f.png)
then the fractions for 
are all 
. So only considers those with 
; in that case one obtains the claimed 
exactly (even without having to take modulo ). 
is a prime power which fully divides , then ![\[ S(n) \equiv p \cdot S\left( \frac{n+1}{p}-1 \right) \pmod{p^e} \]](http://latex.artofproblemsolving.com/2/7/5/2755a27d0a39a5f9cd5bfcafde0e955c5f86f484.png)
by grouping the terms (for 
) into consecutive ranges of length (by the value of 
).
. Realized this with 2 hours left and had to start over. 25AMO5 gave me the exact same feeling as 24JMO4. It took another 1:15 to solve correctly - easily the most stressful hour of my life. I measured my heart rate with roughly an hour left and it was at 50 beats / 20 seconds = 150 BPM.
., odd dies to ., let 
for 
, note that![\[\binom{n}{i}^{2m}=\binom{n}{0}^{2m}+\left(\binom{n}{1}^{2m}-\binom{n}{0}^{2m}\right)+\left(\binom{n}{2}^{2m}-\binom{n}{1}^{2m}\right)+\dots+\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]](http://latex.artofproblemsolving.com/e/5/2/e52aea9ca81731dfbf3248ba89782270fa7606ea.png)
Now, summing this up over all 
, we have![\[\sum_{i=0}^{n}\binom{n}{i}^{2m}=(n+1)\binom{n}{0}^{2m}+\sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]](http://latex.artofproblemsolving.com/4/2/4/424f73676e5567cfa5ad7780b81ae65f72947122.png)
![\[(n+1)\mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]](http://latex.artofproblemsolving.com/a/b/d/abd2716339b8461b603b54a8d005136d98c6ebfa.png)
for all . However, note that since 
is even, we have that![\[(n+1-i)\left(\binom{n}{i}+\binom{n}{i-1}\right) \mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]](http://latex.artofproblemsolving.com/4/d/3/4d3d39f943654cf05ca324b0a0c4bff928f9aafa.png)
But we also have that![\[(n+1-i)\left(\binom{n}{i}+\binom{n}{i-1}\right)=(n+1-i)\binom{n+1}{i}=(n+1-i)\cdot \frac{(n+1)!}{(n+1-i)!i!}=(n+1)\cdot \frac{n!}{(n-i)!i!},\]](http://latex.artofproblemsolving.com/8/5/7/857929600c73ec3912ace293d5641cd2d936b066.png)
which is just 
. This is clearly divisible by , proving thatfor all .
, this means that![\[(n+1)\mid \sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]](http://latex.artofproblemsolving.com/6/0/f/60f1c9ed14f96c9a010c1d74f1b44ac52d72bdff.png)
so![\[(n+1)\mid (n+1)\binom{n}{0}^{2m}+\sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right)=\sum_{i=0}^{n}\binom{n}{i}^{2m},\]](http://latex.artofproblemsolving.com/0/e/3/0e38b432759426919204494110c3382e85f4ad3c.png)
as desired. Therefore all even work, completing our proof.
. for the sum in the problem.
is necessary. Choose . We need , which requires to be even. for prime , since . Hence , and this also requires to be even. This special case is instructive in figuring out the proof to follow. is sufficient. From now on we treat as fixed, and we let be a prime fully dividing . The basic idea is to reduce from to by an induction.. When , we have When , the terms of in order are, modulo , The point is that has five copies of , modulo . is a prime power which fully divides . Then Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases first.
, since , we have we have the analogous reasoning gives then the fractions for are all . So only considers those with ; in that case one obtains the claimed exactly (even without having to take modulo ). is a prime power which fully divides , then by grouping the terms (for ) into consecutive ranges of length (by the value of ).
. When , we have When , the terms of in order are, modulo , The point is that has five copies of , modulo .
, necessity follows from setting . Henceforth assume is even. be a prime power. Then 
.
, 
. Now we induct on 
. Suppose . Then 
where 
is some integer polynomials. Raising both sides to the power of , we have 
, as desired., prime , and nonnegative integer ,![\[p^e\mid\sum_{i=0}^{mp^e-1}\binom{mp^e-1}i^k.\]](http://latex.artofproblemsolving.com/f/9/2/f92881a8c87422cc07fad6a1bb55f4ea8b1ccc00.png)
. If 
, this is trivial. Now suppose it holds for . Working modulo 
, we have![\[(1-x)^{mp^{e+1}-1}=\frac{(1-x)^{mp^{e+1}}}{1-x}=\frac{(1+(-x)^p)^{mp^e}}{1-x}=\frac{1+(-x)^p}{1-x}(1+(-x)^p)^{mp^e-1}=(1+(-x)^p)^{mp^e-1}\sum_{i=0}^{p-1}x^i.\]](http://latex.artofproblemsolving.com/6/e/2/6e24dd0428cac6181d17e04c34a47131832b56ac.png)
Thus by comparing coefficients, 
for 
, 
. Therefore, modulo ,![\[\sum_{i=0}^{mp^{e+1}-1}\binom{mp^{e+1}-1}{i}^k=\sum_{q=0}^{mp^e-1}\sum_{r=0}^{p-1}\binom{mp^e-1}{q}=p\sum_{q=0}^{mp^e-1}\binom{mp^e-1}{q}.\]](http://latex.artofproblemsolving.com/4/1/6/416976281de08bc64838ff9bd3e1a6f892b1a9f0.png)
By the inductive hypothesis, the last sum is a multiple of , hence the first sum is a multiple of .
, then 
for any 
.
. Define 
and 
where 
and is maximal. Then 
.
, where 
. By maximality of , 
. Obviously 
, and we must have 
. Thus 
, all 
, and the desired follows by applying the Lemma. 
is odd is easy, so we assume is even and show the desired conclusion. ones lined up in a row. Then on step , multiply the central 
terms by 
. Obviously, we eventually construct the sequence of all binomial coefficients, and after step , the sequence will be
be the sum of the th powers of these terms after step . As a result, 
. We claim that is invariant throughout the process.
. Now define and where and is maximal. Further, let 
. By the Corollary, . Thus, we may set 
. Now
where division by was allowed because 
. Further, it is obvious that 
, so in conclusion, 
. 
is even as gives 
. Now, we show that all even work. Let .
is a prime power such that 
, then
th slot" as the fraction 
. Considering just the slots that are multiples of ,
, then the th slot is
so if the exponent is even, the slots that are not multiples of do not affect the residue mod at all, which shows the claim.
. Then, if , then by the above claim,
![$$\equiv p \left [ {\lfloor n/p \rfloor \choose 0}^{2m}+{\lfloor n/p \rfloor \choose 1}^{2m}+\dots+{\lfloor n/p \rfloor \choose \lfloor n/p \rfloor}^{2m} \right ] \pmod{p^r}$$](http://latex.artofproblemsolving.com/e/0/e/e0e5151a5440ee3e485bf33a2fa92fd2a2253d84.png)
's in the base representation of to show that implies 
. If there is one trailing , then clearly the above implies 
. Then, if has trailing 's, then 
has 
trailing 's. Thus, if 
, then , as desired.
implies , we are done.
if is a power of and all even otherwise.
, and let 
. Notice that by definition we have 
. Since , we have 
if and 
otherwise, so for each term, either both the numerator are divisible by , or neither are. Let 
be the number of terms in the denominator that are not divisible by ., we have 
, so 
. For each term such that , we can divide out a from both the numerator and the denominator. Notice that what's left is simply 
. Thus, we conclude that ![\[\boxed{\binom ni \equiv (-1)^M \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}}.\]](http://latex.artofproblemsolving.com/e/0/f/e0f2a107e53c8631fd3cf1210ade103d8fd64009.png)
even works for all : For 
, we clearly have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv p \equiv 0 \pmod p.\]](http://latex.artofproblemsolving.com/4/d/f/4df990e36b11b2a0f285995c194ed186b12ad2d6.png)
where 
, and suppose that 
satisfies the induction hypothesis for the prime . Clearly 
. Then we have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \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/5/9/4/594fb854a4626f0577e795c410495c3bd69db64b.png)
By the induction hypothesis, 
divides the inner binomial sum, so since we are multiplying it by , 
must divide 
. odd fails for 
: For , we clearly have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv 1 \pmod p.\]](http://latex.artofproblemsolving.com/2/8/0/280473e428505c0c672beb4b3b11e6a6bd0b5af0.png)
where , and suppose that satisfies the induction hypothesis for the prime . Since 
is even, there exists one more 
than 
for each block of such that 
remains constant. Then we have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv \sum_{i=0}^d \binom di^k \pmod {p^a}.\]](http://latex.artofproblemsolving.com/a/1/7/a178742010900bf910f7d1745ee31203de2ddfda.png)
By the induction hypothesis, does not divide this sum, so does not divide it either. odd works for a power of : Let 
. For 
, clearly odd work as 
. Now suppose odd works for 
. If we let 
, then we have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \pmod{2^{d+1}}.\]](http://latex.artofproblemsolving.com/0/f/f/0fff79199fa08d23fdd0637082ce55d76826612e.png)
such that remains constant, there is exactly one odd and one even . Thus, the sum simply vanishes 
. work for all primes , it follows by CRT that all even work. For not a power of , there exists an odd prime such that , which can be easily used to show that all odd fail.
We want to find all such that 
for all positive integers 
. Clearly, letting 
, we have![\[3\mid F_k(n,i)=1^k+2^k+1^k\]](http://latex.artofproblemsolving.com/8/d/f/8dfd2f126b81d6d01b3d76c271424f11deea5584.png)
which forces to be even. is even, . Let 
. First, we prove a claim.
for all 
.
is constant given that 
is constant. Therefore,![\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\pmod {p^a}\]](http://latex.artofproblemsolving.com/b/3/a/b3a0d05cd82fa8c799929ed4c859a749601e2e1f.png)
We now continue to our second claim.
for all 
.
. Note that if 
this simply says 
which is trivially true. Now assume![\[f_k(n/p,i)\equiv f_k(n,ip)\equiv f_k(n,ip+p-1)\pmod {p^{a-1}}\]](http://latex.artofproblemsolving.com/6/6/f/66fd05865092ffade91f1d4eb3205daea1935a3e.png)
and we have
Which completes the induction step.
![\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\equiv pF_k(n/p)\pmod {p^a}\]](http://latex.artofproblemsolving.com/2/6/8/26831e9aa39a05983a55035269e08c68ac9027d4.png)
so if 
then 
. By induction we are done.
is odd then fails, now if is even then from CRT all we need is to prove that 
.
) and some positive integer 
such that 
that:![\[ \binom{m \cdot p^{\ell}-1}{xp+y}=\left( \frac{(m \cdot p^{\ell}-1) \cdots (m \cdot p^{\ell}-p+1)(m \cdot p^{\ell}-p-1) \cdots )}{1 \cdots (p-1)(p+1) \cdots} \right) \cdot \frac{(mp^{\ell-1}-1) \cdots (mp^{\ell-1}-x)}{1 \cdots x} \equiv \pm \binom{m \cdot p^{\ell-1}-1}{x} \pmod{p^{\ell}} \]](http://latex.artofproblemsolving.com/7/8/5/7851252f0cde588fbcee11b8d01e91883dbb213d.png)
So now using this notice that we have 
so we can induct down and throw CRT until we get a degenerate case of the divisibility prompt in which case it is a trivial result thus we are done 
.
.
. To show that evens work, we will induct by taking mod 
, then CRT finishes.
.
. When 
it's obvious.
individually. Note that 
. Therefore, if 
, then both the numerator and denominator of 
are relatively prime, therefore it's 
. But since is even 
and it does nothing. So just ignore all with .
to 
we see that we multiply by 
, and this fraction is when and are relatively prime. So that eliminates all odd cases in general no matter which u picked as long as is prime (i just said n=2 because it takes less explanation). Because if it's odd then 
and it breaks but we need . and aren't relatively prime? from to make it easier because CRT duh that we picked and then it's easy to see we can use induction after shrink the binomial coefficient by on the top and bottom and aren't relatively prime, im simple minded lmao
for any arbitrary 
and didn't mention CRT? (I defined p-adic notation)
is a counterexample.
is a counterexample