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
is an involution, 
can be 
or .
yields that 
for some 
and 
for some 
. is even then has to be even, and vice versa. If is odd then 
. So our solution is 
even and 
odd. This works upon checking.
the assertion of the following F.E., i claim that 
works for all integers where either 
are odd or 
are both even.
Also 
gives 
so infact is an involution (i.e. 
).
, now set 
then by 
we get that 
for all even .
we get 
for all integers so 
for all odd , now if 
is odd then notice that 
for all odd . so odd, if is even, but 
odd then 
for all even so which cant happen so is also even in this case. Hence our claim is true and we are done 
.
such that for all integers and 
, ![\[ f(2x+f(y))+f(f(2x))=y. \]](http://latex.artofproblemsolving.com/b/0/d/b0d16e87a8b30ebec5997ed12254094cdc3125d5.png)
and 
and 
as per our claim.
or 
are odd that 
for even and 
for odd where either 
are both even or 
These solutions clearly work.
, we get that . Letting only 
, we have 
so 
Thus, is an involution.
(and ).
Letting 
gives 
Since involutions are both injective and surjective, we can de-nest this into 
Thus, for all even , we have 
, we have that 
Applying to both sides and using the fact that is an involution, 
Thus, by induction, if 
, then 
for all odd integers 
.
If is even, then this equation is clearly true since 
is even. Then, if is even, then we have that all even inputs lead to even outputs. Hence, if 
is odd, then odd also maps to even, contradicting surjectivity. Thus, if is even, then must also be even. Otherwise, if is odd, then we must have 
Thus we are done.
![\[ f(x) = \begin{cases} a - x & x \equiv 0 \pmod 2 \\ b - x & x \equiv 1 \pmod 2 \end{cases} \]](http://latex.artofproblemsolving.com/e/a/e/eae545d48ed07867af7cc41795addd69bed920e6.png)
where and are either both even, or 
. It can be checked that all of these work, so we prove they're the only solutions. be the given assertion.
.
.
.
implies takes the above form for some and , so we'd be done if we could show the parity condition. If is odd, then plug in to deduce ; if is odd, plug in to deduce 
. This finishes the problem.
from 
and 
from 
. Then our condition can be rewritten as![\[y=f(2x+f(y))+2x.\]](http://latex.artofproblemsolving.com/c/e/7/ce76b9222ff3afaf771c95071e5060b3c0f2e981.png)
based on parity:
and with our involution 
. We get the following solution, which can be easily tested:![\[\boxed{f(x) = \begin{cases} -x+c & \text{for even } x \\ -x+d & \text{for odd } x \end{cases} \quad \text{where }a,b \text{ both even or } a=b.}\]](http://latex.artofproblemsolving.com/d/0/9/d09d5876e59d532e5fe1b962b0786afd6ac667ae.png)
for odd and 
for even where 
are integers such that either 
or 
. With some effort, we can verify that these all work.
. From 
we have 
. Then from 
, we have 
, which implies that is bijective. This also lets us rewrite the original equation as 
.
, we have 
, which implies that there exists integers such that when is odd and when is even. From , we see that:
is even, then must also be even, as if is odd then 
, a contradiction. Any pair 
with and both even will work, as mentioned above. is odd, then 
, so , which also works.
then 
to get 
Thus, is an involution. The original equation is now
Then we can separate into cases even and odd like this :
If is even, must also be even, as if is odd then 
contradiction. is odd, then 
because 
which works. Thus, our answer is
for even and 
for odd where 
or and are both even. It is easy enough to do cases and check that these solutions work. denote the assertion. gives us , so by , we get ![\[f(f(y))+f(f(0))=f(f(y))=y,\]](http://latex.artofproblemsolving.com/f/f/9/ff9c87585b1956edb167a10a89e886f008d42b18.png)
meaning is an involution, and is therefore bijective. Now, We have ![\[f(2x+f(y))+f(f(2x))=f(2x+f(y))+2x=y,\]](http://latex.artofproblemsolving.com/4/a/a/4aa0f07711a1dbea416bba54f4339f89065d715a.png)
giving 
. Thus, for even , we have 
. We also have 
, giving 
for odd . Let 
and 
, so we can write for even and for odd . is even in our original equation. Then, we have ![\[f(2x+f(y))+f(f(2x))=f(2x-y+c)+2x=y,\]](http://latex.artofproblemsolving.com/0/0/4/0042bafb3e8a539f524ab0399da223496c2336db.png)
so if is even, then this works. Otherwise, if is odd, then we must have . is odd in our original case. Then, we have ![\[f(2x+f(y))+f(f(2x))=f(2x-y+d)+2x=y,\]](http://latex.artofproblemsolving.com/2/2/d/22ddd8cdc51bb54652839bf9e8b5589508bbdf97.png)
so if is even then this works. Otherwise, we must have ., or and are both even, as desired.
to get 
. Putting 
gives 
. This implies is bijective. be such that 
. Putting 
gives us that 
since 
giving us that 
. be such that 
. Putting 
gives us that 
. is even and is odd or 
in order to satisfy the given equation.
where 
satisfy the above conditions.
is the assertion then 
. Then 
. We also have 
which when gives us 
. Thus our solutions are determined by 
and 
, say write it as 
when is odd and 
when is even. Now tells us that 
. Therefore, can be even or . A similar analysis on 
tells us that is even or . Thus, we have 
when is odd and when is even for some 
such that they are both even or equal.
denote the assertion. Then 
Hence 
so 
is bijective. Thus the assertion becomes 
Thus 
If is odd, we have that 
This holds also when is odd. Hence, the solutions are 
where either are both even or 
if is some odd integer, or 
if is even and 
if is odd, and 
are even integers. denote our assertion. From 
we see that 
From 
we get that 
using the fact that By rearranging our given equation, and taking on both sides, we see that 
Let 
Note that by plugging in 
, 
Now we consider two seperate cases.
we plug it back into our original equation to see that 
and thus we have that 
Thus, 
and hence 
Thus, we can write 
clearly we can't say anything, and both solutions are valid.
with 
for some fixed positive integer 
for constants 
and 
for some constant 
.
for these two classes of functions. For 
,
For the other function, note that if 
and if 
So we have shown that these two classes of functions work.
denote the assertion. 
Thus, 
Therefore, we have that the original functional equation can be rewritten as 
so 
Since 
Now, note that from plugging in 
into this, 
and plugging in 
into this, 
Therefore, it follows that there exists a constant 
for all even 
.
but 
but 
.
.
or 
where either 
or if 
then both of them are even. It is easy to check that all such solutions indeed work, so it remains to show that the given functional equation implies that 
and 
Hence, we have 
so we can plug this into 
Now, applying 
Then, let us fix 
and let 
for some 
Then, we get
Therefore, as we vary 
(so that 
for some constant 
This implies the existence of two constants 
such that
Now, we use the fact that 
If 
we get
and it is easy to see that 
being odd implies the same thing. On the other hand, if 
so no conclusion can be found about 
and the same thing holds for