AoPS Academy
is written on the board. A move consists of adding either , 
or 
to the number written on the board, but only if the chosen number is coprime with the current number (for example, if the current number is 
, then in a move a player can't choose the number , but he can choose either or ). The player who first writes a perfect square on the board loses. Prove that one of the players has a winning strategy and determine who wins in the game.
of positive integers is called central if for every positive integer 
, the arithmetic mean of the first 
terms of the sequence is equal to .
of positive integers such that for every central sequence 
there are infinitely many positive integers with 
.
be a triangle. Let 
be a circle passing through 
intersecting 
at 
and 
at 
. Let 
be the intersection of 
and . Further, let 
and 
be the intersections of 
and 
with the tangent to 
at 
. Now, let 
be the second intersection of 
and . Then, prove that , , , 
and are concyclic.
+1 w
with real coefficients such that for all reals 
such that 
we have the following relations![\[ f(a-b) + f(b-c) + f(c-a) = 2f(a+b+c). \]](http://latex.artofproblemsolving.com/4/4/9/4491a53f9c6f96c18e42eb984b8e83566140bfdb.png)
is in the image of f (I mean, for any such a,b,c there exists a number 
such that that number equals f(g(a,b,c))).
, with constant real k and l. But in order to prove that 
works, one needs some rather messy calculations 
whenever 
. Equivalently, 
divides 
.
and 
if so 
are linearly independent, so each coefficient 
must be zero.
or divides 
, 
, 
. Then 
. This gives
.
,
for all even 
.
for all 
. Therefore, all of 's exponents have even degree. Then making the substitutions 
(so that 
), the given condition becomes 
. Therefore, the original problem is completely equivalent to finding all even polynomials with 
satisfying the functional equation
for all 
.
. Equating terms of degree 
, we find that
or letting 
, 
.
. Then the root 
appears with multiplicity at least on the 
, and hence on the 
as well.
, 
, a contradiction.
so that 
(since 
) for 
are the only possibly solutions. A quick check shows that these solutions are indeed valid.
:
.
,
denote the assertion. Clearly 
gives 
.
we see 
implying 
is even. Thus 
for some polynomial 
.
fails. To see this we consider the leading coefficients of the polynomial. Note that we want the following to fail,
This is equivalent to showing that the leading coefficients of the following fail,
Setting 
and 
we see we need,
However it is easy to see the LHS is much greater than the RHS for 
gives 
so then we can plug in 
to get that 
.
gives 
.
.
we find that 
we find that 
,
,
and 
.![\[ P(5k) + P(3k) + P(8k) = 2P(7k) \]](http://latex.artofproblemsolving.com/0/1/d/01dbee029b82151f3a309cf5af8f0b93de642a67.png)
Now, suppose that 
has degree ![\[ 5^n + 3^n + 8^n = 2\cdot 7^n \]](http://latex.artofproblemsolving.com/4/8/9/48968f6a13dbd3e538b437453c2935ede8599de3.png)
From Bernoulli we see that 
.
.
.
,
for some reals 
and 
.![\[ (a-b)^4 + (b-c)^4 + (c-a)^4 - 2(a+b+c)^4 = -6(ab+bc+ca)(ab+bc+ca+a^2+b^2+c^2) \]](http://latex.artofproblemsolving.com/5/5/b/55b5bb18d2789e2c80dfec95e4cb4c6687ef1716.png)
and 
works as![\[ (a-b)^2 + (b-c)^2 + (c-a)^2 - 2(a+b+c)^2 = -6(ab+bc+ca) \]](http://latex.artofproblemsolving.com/2/7/b/27bcd8e83e3c3a7fa6d78263a92599eef5beff71.png)
so indeed all polynomials of that form work. 
.
on the left in the expression, where say 
behaves: 
behaves: 
is not always 
,
.
behaves: 
further, but I'm so lazy, a lot of numbers appear with it, and something tells me that equality does not always happen, I thought. Then, it would be worthwhile to come up with some universal values for 
would be satisfied at the same time, and so that the coefficients could be conveniently estimated.
looks like this: 
It is very inconvenient to disclose this whole thing with large values of 
,
Then, let's look at 
,
and the value would be identical to 
,
:
We get two roots, I see that the first one is more convenient and I take it. Let's look at our coefficient 
Let's say 
With 
and odd, the two sides will have different signs, and with 
and 
,
we have checked. Check 
,
,
and make sure that the equality is identical.
and 
works where 
,
.
denote the assertion 
.
.
.
.
.![\[ P\left(\frac{5c}{6}\right) + P\left(\frac{c}{2}\right) + P\left(\frac{4c}{3}\right) = 2P\left(\frac{7c}{6}\right). \]](http://latex.artofproblemsolving.com/f/f/a/ffac9e9e5f2e7743e7b1af924d8b9e8edbff4800.png)
term, we get that,![\[ a_i\left(\frac{5}{6}\right)^{2i} + a_i\left(\frac{1}{2}\right)^{2i} + a_i\left(\frac{4}{3}\right)^{2i} = 2\left(\frac{7}{6}\right)^{2i}. \]](http://latex.artofproblemsolving.com/a/3/5/a35651a4e49833d4c916728421f9a0c3d564e0a0.png)
.
,
.
for all 
.
.
and 
,
.
for real numbers 
works and we want to prove its uniqueness.
are solutions, 
is a solution for all real numbers 
so it's enough to find all solutions of the form 
.
gives us that 
,
,
,
,
,
,
which is a contradiction.
,
contradiction.
for any real number 
,
,
,
implies 
Plugging 
gives us that 
However, we also have 
We will only use 
which when plugged into 
we get 
We will equate coefficients of 
on both sides, noting that 
in 
,
Thus, or each nonnegative integer 
or 
This is only true for 
and 
for 
Thus, only the 
,
This is very nice because this means that the 
that I used, one can prevent the input of the polynomial from having a constant shift. In fact, 
is really the only substitution you need to solve this problem.
for real numbers 
,
is not the only basis for real polynomials, and there are plenty of other choices, so closure under addition like this does not imply that only checking these suffices
where 
.
for all 
.
where 
.
into the equation and after clearing the denominator we get 
for all 
We can check that 
for all 
.
we can prove via the multinomial theorem that 
.
,
and let 
.
,
in 
is some nonzero number times 
,
be the set of solutions. We prove that 
so 
-
both work.
to get 
Hence, if a polynomial works, then we require 
where 
However, simply note that 
for 
.
works, thus 
works.
works, thus 
and 
is even
,![\[f(a) + f(0) + f(-a) = 2f(a) \Longrightarrow f(a) = f(-a) + f(0)\]](http://latex.artofproblemsolving.com/2/b/a/2ba188c9c1c48089b129b1a84eda8de0300f436a.png)
Since the constant terms of both sides of the equation have to be equal, it follows that ![\[f(a-b) + f(b-c) + f(c-a) = 2f(a+b+c)\]](http://latex.artofproblemsolving.com/9/0/9/909c138a61d0d1f6859d7822fb7893b8db2f62ac.png)
if 
works, then 
,
,
,
fails for 
.
fails
to get rid of the algebraic condition, thus our equation becomes![\[{(a-b)}^{2k} + {\left(b + \frac{ab}{a+b}\right)}^{2k} + {\left(\frac{-ab}{a+b} - a\right)}^{2k} = 2{\left(a+b-\frac{ab}{a+b}\right)}^{2k}\]](http://latex.artofproblemsolving.com/c/a/a/caa05030c62f1aba4337d3d4ac6f2a777652f548.png)
We can multiply both sides by 
to obtain![\[{(a^2-b^2)}^{2k} + {(b^2 + 2ab)}^{2k} + {(a^2 + 2ab)}^{2k} = 2{(a^2 + ab + b^2)}^{2k}\]](http://latex.artofproblemsolving.com/7/3/4/73441f6405e2b94cce970f61398dd199daf37a79.png)
Now we can substitute 
and 
which gives![\[3^{2k} + 5^{2k} + 8^{2k} = 2 \cdot 7^{2k} \Longrightarrow {\left(\frac{3}{7}\right)}^{2k} + {\left(\frac{5}{7}\right)}^{2k} + {\left(\frac{8}{7}\right)}^{2k} = 2\]](http://latex.artofproblemsolving.com/1/2/2/1228a1e5cf8f1bf0aa746fa9e853e48f0dcb71cf.png)
Since 
by the binomial theorem, we are done. 
with 
however there exists some 
such that 
,
fails.
denote the largest value such that 
works, but 
fails.
then 
works, thus we can just get rid of these terms and only look at the function
,
denote some triple of values such that 
and for which![\[{(p-q)}^{k} + {(q-r)}^{k} + {(r-q)}^{k} \neq 2{(p+q+r)}^{k}\]](http://latex.artofproblemsolving.com/3/8/0/380f8e875791accd07888e501e00e269fe98bde3.png)
such a triple clearly exists since we assumed that 
,
works, it follows that![\[g(p-q) + g(q-r) + g(r-p) = 2g(p+q+r)\]](http://latex.artofproblemsolving.com/6/4/0/640cd8076426eaf2a8a94c65cd989b08b4a34aaf.png)
Thus![\[a_{k} \cdot \delta = 2h(p+q+r) - h(p-q) - h(q-r) - h(r-p)\]](http://latex.artofproblemsolving.com/2/5/e/25e8535ee9a5d52bc6cbb7c5dbf1805712c18067.png)
Notice that if the functional equation holds for some 
where 
is an arbitrary constant. Thus by scaling the variables by ![\[a_{k} \cdot \delta \cdot c^{k} = 2h(cp+cq+cr) - h(cp-cq) - h(cq-cr) - h(cr-cp)\]](http://latex.artofproblemsolving.com/4/b/7/4b73951e14e1aca190bda2fe72897b2dde744943.png)
Since 
is a degree 
polynomial at best, it follows that the right hand side grows by at most 
,
.
.
,
,
.
.
.
for any real 
,
gives 
.
gives![\[f(2a-1)+f(a^2-2a)+f(a^2-1)=2f(a^2-a+1).\]](http://latex.artofproblemsolving.com/e/e/f/eef54fefa664c737db4d625d07c54bd9f11227c4.png)
Suppose that the leading term of 
,
.
on both sides, we get![\[4k(2k-1)-2k=2(2k+k(2k-1))\]](http://latex.artofproblemsolving.com/a/3/0/a3032d39fbad69cd86d0b8bd6c3ddec149f7929e.png)
which eventually reduces to 
,