AoPS Academy
+1 w
be the set of positive integers. A function 
satisfies the equation ![\[\underbrace{f(f(\ldots f}_{f(n)\text{ times}}(n)\ldots))=\frac{n^2}{f(f(n))}\]](http://latex.artofproblemsolving.com/2/e/7/2e73ff2f75b103e9d6a4004a42e4ed7f4ee64a67.png)
for all positive integers 
. Given this information, determine all possible values of 
.
be an integer. Rowan and Colin play a game on an 
grid of squares, where each square is colored either red or blue. Rowan is allowed to permute the rows of the grid and Colin is allowed to permute the columns. A grid coloring is orderly if: [list] [*]no matter how Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and [*]no matter how Colin permutes the columns of the coloring, Rowan can then permute the rows to restore the original grid coloring. [/list] In terms of , how many orderly colorings are there?
is selected inside acute 
so that 
and 
. Point 
is chosen on ray 
so that 
. Let 
be the midpoint of 
.
is tangent to the circumcircle of triangle 
.
that satisfy![\[
f(x^2-y)+2yf(x)=f(f(x))+f(y)
\]](http://latex.artofproblemsolving.com/f/b/b/fbb693770cd90d8a144026608074122e54da5802.png)
for all 
.
and 
be positive integers. The cells of an 
grid are colored amber and bronze such that there are at least 
amber cells and at least 
bronze cells. Prove that it is possible to choose amber cells and bronze cells such that no two of the 
chosen cells lie in the same row or column.
and 
are erected outside an acute triangle 
Suppose that ![\[\angle BC_1C+\angle CA_1A+\angle AB_1B=180^{\circ}.\]](http://latex.artofproblemsolving.com/3/3/7/3378f0c4409d14bc0afddf2616992c13f624be3b.png)
Prove that lines 
and 
are concurrent.
-by- grid. He colors 
of the unit squares silver and the remaining squares gold. Kei then folds the grid in half vertically, forming pairs of overlapping unit squares. Let 
and equal equal the least and greatest possible number of gold-on-gold pairs, respectively. What is the value of 
?
-by- board of unit squares for some odd positive integer . We say that a collection 
of identical dominoes is a maximal grid-aligned configuration on the board if consists of 
dominoes where each domino covers exactly two neighboring squares and the dominoes don't overlap: then covers all but one square on the board. We are allowed to slide (but not rotate) a domino on the board to cover the uncovered square, resulting in a new maximal grid-aligned configuration with another square uncovered. Let 
be the number of distinct maximal grid-aligned configurations obtainable from by repeatedly sliding dominoes. Find the maximum value of as a function of .
, 
, and 
. It is easy to check that these work.
be the given assertion. 
gives us 
. We have
so 
. Now
so 
. It follows that 
.
then 
.
satisfy . Then![\[
P(a,b^2)\implies f(a^2-b^2)+2b^2f(a)=a^2f(a)+b^2f(b)\implies f(a^2-b^2)=f(a)(a^2-b^2)
\]](http://latex.artofproblemsolving.com/a/e/8/ae842d79d88987073fe6a3e9f50dd5e2e09aab3d.png)
so![\[
f(a)(a^2-b^2)=f(a^2-b^2)=f(b^2-a^2)=f(a)(b^2-a^2).
\]](http://latex.artofproblemsolving.com/7/3/5/735299558feb7afde3dbbb6ec85c4a879de90bcd.png)
It follows that 
, as desired. Thus 
. 
such that 
and 
.
so 
, a contradiction. such that and 
.
so , a contradiction. such that 
and .
so , a contradiction. 
and 
satisfy the given equation. Now, we will prove that these are the only solutions. Let 
denote the given assertion.
Then, we can rewrite as![\[f(x^2 - y) = (x^2 - 2y) f(x) + f(y).\]](http://latex.artofproblemsolving.com/f/e/2/fe2029f465d1261e9205f8e4904307c1f3a17e78.png)
Replacing 
by 
gives![\[f(x^2 + y^2) = x^2 f(x) + y^2 f(y) + 2y^2 f(x).\]](http://latex.artofproblemsolving.com/e/4/5/e458032883ac5073db21bfedce72695cb7637d03.png)
By symmetry, we get 
. Setting 
, we have 
for some constant 
. Since 
, it follows that 
or 
.
, 
and 
.
.
from 
.
gives us 
, so our FE is equivalent toLet 
denote the above assertion.
, then for all 
.
. Subtracting 
from 
gives us![\[f(r^2 - x) = f(-x),\]](http://latex.artofproblemsolving.com/5/0/9/50919a9f03417224310f90367e91c8c57e6a2b5c.png)
so is periodic with period 
. Now, subtracting 
from 
gives us 
for all , so is identically 
. is the only root of . Taking 
where 
gives us 
, implying "quasi-injectivity": that if 
, then 
. Now, taking gives us , so 
for each . for all or for all . is a solution to our rewritten FE, then 
is also a solution. So, assume WLOG that 
. Now, let and be nonzero reals with such that 
:
and 
, taking gives us 
, which is a contradiction. and 
, taking gives us![\[x^2(x^2 - 2y) = 0 \implies y = x^2 - y = 1 \implies x = \sqrt{2}.\]](http://latex.artofproblemsolving.com/5/d/3/5d323c8c42d143f5e17ce51ef3626510392ebae8.png)
But now, taking 
gives us 
, contradiction. and , taking gives us 
, contradiction. or .
, 
, and 
, which work. Let denote the assertion in the problem statement. gives .
gives .
gives . gives 
.
gives![\[f(x^2-y^2)+2y^2f(x)=f(f(x))+f(y^2)=f(x^2)+f(y^2).\]](http://latex.artofproblemsolving.com/3/4/6/346b72cd5da018be850c8f06e87c75bf671af7a0.png)
Swapping and gives![\[f(x^2-y^2)+2y^2f(x)=f(y^2-x^2)+2x^2f(y)=f(x^2-y^2)+2x^2f(y),\]](http://latex.artofproblemsolving.com/6/b/e/6beafc6621faf65fa8c1fd1c05e1dece1f4311ce.png)
so 
. Plugging in 
gives 
., we have![\[f(1)(f(1)x^2)^2=f(1)x^4 \implies f(1)^3=f(1),\]](http://latex.artofproblemsolving.com/f/e/9/fe99b7b2961a5d0f379db7927d4af9db63a3df27.png)
so 
, as desired. 
, 
, and 
. It is easy to verify that these work. It remains to show that they the only solutions.
. Therefore:
. is even.
, then 
.
., then we have
.
which can easily be verified to work. Let denote the given assertion.
gives 
.
and and equating gives 
. 
so 
or for nonzero and thus for all . Therefore is even. Call this statement .
immediately gives us 
so , coupled with the fact that . Now let , so 
, and we have the chain: 
which is of tremendous use. Let 
in the latter inequality to get 
so 
as mentioned before for an individual . and for 
, then consider 
and 
. This readily shows 
. This contradicts . and for then consider and yet again. This shows that 
again which contradicts . and then 
and 
give us another contradiction.
. denote the given equation. From 
, we obtain![\[f(x^2) = f(f(x)) + f(0)\]](http://latex.artofproblemsolving.com/0/3/a/03ac6e3db0fb40e9505413e3b56b538ff7080f74.png)
. From 
, we obtain![\[c = f(c) + c \implies f(c) = 0 \implies f(f(c)) = c\]](http://latex.artofproblemsolving.com/5/4/6/5465812e749937fb2b3d5a3749c36939ee2a552d.png)
, we obtain![\[f(c^2) = f(f(c)) + c \implies f(c^2) = 2c\]](http://latex.artofproblemsolving.com/8/6/2/862f6fbbed9482c36ad6c1443003b7c680f2786b.png)
, we know that![\[f(0) + 2c^2f(c) = f(f(c)) + f(c^2)\]](http://latex.artofproblemsolving.com/4/1/b/41b6f1f0462da1b790df7ce78f024f83c2bbdb5e.png)
![\[c = c + f(c^2) \implies f(c^2) = 0\]](http://latex.artofproblemsolving.com/e/9/3/e935f51373fbc14553038656a96f8d8c06828e74.png)
![\[f(c^2) = 2c = 0 \implies c = 0\]](http://latex.artofproblemsolving.com/6/b/a/6bad87ad061debaee93163316bfb389be700710b.png)
., we have![\[f(x^2) = f(f(x)) + f(0) \implies f(x^2) = f(f(x))\]](http://latex.artofproblemsolving.com/8/6/5/865d7e5de9a004ebc96b1e2d2f0135468a3b1f95.png)
, we have![\[f(x^2 - x^2) + 2x^2f(x) = f(f(x)) + f(x^2)\]](http://latex.artofproblemsolving.com/9/b/5/9b5a2f7d698e4d60a9c7d2ac079fd53729578147.png)
![\[2x^2f(x) = 2f(x^2) \implies x^2f(x) = f(x^2)\]](http://latex.artofproblemsolving.com/0/2/a/02abdb9022a49e2f565726ae8438cdba0586b775.png)
is even.
, we have![\[P(0 - y) + 2yf(0) = f(f(0)) + f(y)\]](http://latex.artofproblemsolving.com/7/4/9/749e217e45ec1d5ee8dc0d69d63cbabd645248fe.png)
![\[f(-y) = f(y)\]](http://latex.artofproblemsolving.com/3/d/4/3d48f52846d536addf2ec6dffa0384bbf6b8340d.png)
and 
, we will prove that . After we finish doing so, we will show these are the only solutions by avoiding the pointwise trap.![\[f(f(f(x))) = f(f(x^2)) = x^4f(x^2) = x^6f(x)\]](http://latex.artofproblemsolving.com/9/3/b/93b2eb017b1aade79eb663fbe47f182815fc4d6d.png)
![\[f(f(f(x))) = (f(x))^2f(f(x)) = x^2(f(x))^3\]](http://latex.artofproblemsolving.com/7/d/5/7d5f3c242fa38a7f157965a28b104c092a995549.png)
![\[x^6f(x) = x^2\left(f(x)\right)^3\]](http://latex.artofproblemsolving.com/5/d/2/5d2c33c5233a49c4ce8798197558c97fa5d246a8.png)
![\[x^2f(x)\left(f(x)^2 - x^4\right) = 0\]](http://latex.artofproblemsolving.com/8/d/1/8d1788c6748c840895ece3ca1dda06debee958ff.png)
![\[x^2f(x)\left(f(x) + x^2\right)\left(f(x) - x^2\right) = 0\]](http://latex.artofproblemsolving.com/4/8/1/4817341d1f81f070922135f2c225ded3e0244ee1.png)
is if 
.
, 
, and 
. Because these take a while to type out, I will edit this solution later to include them. The basic idea is to have non-zero variables and such that 
and 
(for case 1; same logic applies for cases 2 and 3) and show that this leads to a contradiction with the given. Claim 3 ( is even) will prove useful for this.
to get 
to get 
Thus 
In particular, 
and 
we see 
Thus 
so for 
we have and thus is even.
to get 
This simplifies to 
so 
From 
we get 
Taking 
gives 
Then 
gives 
so 
so either is identically zero or 
From 
we have 
so and 
From we get 
for all 
gives 
This is symmetric, so 
so 
Taking 
in the above, we get 
but clearly this only holds when either 
or 
and we may easily check that these work.
denote the given assertion. We claim that the only solutions are 
, 
and, 
which clearly work. yields 
, so it suffices to prove that . Observe that by , we get 
but after cancelling out terms and substituting 
for 
, we get 
which directly implies the result. we can now easily prove that is even, as gives 
. The key claim is as follows.
implies 
or 
states 
and 
states 
but using both that and that is even, this is equivalent to 
so either or 
for some positive real , than 
gives 
but note that 
so we in fact have 
. However, by Claim 1.5 either 
or 
, the latter being only true when 
. Thus, we have for all 
. But one can now easily find 
taking any 
satisfying 
, as then gives 
.
for any greater than . Recall that so we can apply Claim 1.5 to get 
, which yields . can't change of sign, thus leaving us with only the initially stated solutions. Assume for the sake of contradiction that changes in sign. By Pigeonhole principle, one of these must repeat an infinite number of times, WLOG say it is , as the other is completely symmetric. Now choose a sufficiently large such that and a small 
in comparison which satisfies . Now notice that 
gives 
where we used 
, which is a consequence of 
. We can rewrite this as 
but we also know 
. So we can now distinguish two cases.
we get 
so 
. But we supposed , so this case leads to a contradiction.
is positive for sufficiently large , however 
is always negative, so we can immediately discard this case.
to get 
, substitute in the original equation to get 
*.
to get 
. Substitute into * to get 
**.
to get 
.
to get 
. Subtract ** from this to get 
. Substitute 
to get 
.
(because is even), so 
.
. Plug in 
to get 
. Therefore, for some constant .
, and 
. Equating these, we have 
for all real ; solving 
, we get 
., , and . 
. It can be easily verified that these work. We will now prove that these are the only solutions.
yields![\[f(\frac{x^2}{2})+ x^2f(x) = f(f(x)) + f(\frac{x^2}{2}) \implies f(f(x)) = x^2f(x)\]](http://latex.artofproblemsolving.com/e/5/3/e538dbe95820f3be8cb9357f73598055b023f3bb.png)
Now, 
gives![\[f(x^2 - x) + 2xf(x) = x^2f(x) + f(x)\]](http://latex.artofproblemsolving.com/9/0/c/90cb6c18b1da7a5fa037fe0addb4ef39ee900176.png)
![\[f(x^2 - x) = (x - 1)^2f(x)\]](http://latex.artofproblemsolving.com/f/0/8/f08f0c60ff1e716d1b3bf0ec937148ee72bfd631.png)
Plugging in 
gives . Now, 
gives us![\[f(x^2) = f(f(x)) = x^2f(x)\]](http://latex.artofproblemsolving.com/2/8/c/28ceb78283e3fa6bb15e5431cf351579f0f2d3c2.png)
so the claim is proven. is even., we have that![\[f(x^2) = x^2f(x)\]](http://latex.artofproblemsolving.com/1/a/9/1a95e1004d22be9c434ecff081fb3afc51647345.png)
and that![\[f((-x)^2) = x^2f(-x)\]](http://latex.artofproblemsolving.com/4/c/c/4ccb85b5b42724dc4f4bf69b986194c0f383d3a9.png)
This implies that 
. If , we get 
. Otherwise, if , it is trivial that 
. Thus, is even.
yields![\[f(x^2 - t^2) + 2t^2f(x) = f(f(x)) + f(t^2) = f(f(x)) + f(f(t))\]](http://latex.artofproblemsolving.com/6/7/1/6719b4dae34f07f07e30e2dfd45cf55318e3a44e.png)
Swapping and 
gives![\[f(t^2 - x^2) + 2x^2f(t) = f(f(t)) + f(x^2) = f(f(x)) + f(f(t))\]](http://latex.artofproblemsolving.com/d/5/e/d5ec7637a30cda35358e15e21409e08d9f80b51c.png)
However, since is even, the first term of both equations are equal, so we may subtract to get![\[2x^2f(t) = 2t^2f(x)\]](http://latex.artofproblemsolving.com/4/9/1/491261479bc1d4f04a10b846e8fddf9d5e676417.png)
Assume 
are nonzero, then this means that 
is equal to a constant for all nonzero values of . This means , and upon substituting, we find 
. Clearly, also satisfies this, so we find 
and we are done.
gives . Setting 
, and gives 
. Setting 
gives 
. Subtracting the previous equations we have made gives . Therefore setting gives . Setting now gives 
. Now I claim that 
is a valid solution to the functional equation iff 
is a valid solution. This follows because :
Therefore we may assume that 
. Notice that setting and 
implies that 
, and setting 
, and gives 
subtracting equations gives . We also have from previosly derived properties 
. Therefore 
.
be our assertion. We start by plugging in a lot of values. implies that 
and implies that 
and thus 
. implies that 
Thus, we also have that 
which tells us that 
gives us that 
, but 
gives us that 
Thus, 
we have that 
Thus, 
We also know that 
and hence 
Thus, 
but then we also have that 
by 
and hence 
which is a contradiction. Thus, 
tells us that is even. Now, tells us that 
However, by swapping the variables, we get that 
By subtracting these two, we get that 
Thus, 
By plugging it in our equation, we see that 
Thus, 
.. Note that gives![\[f(x^2) = f(f(x))+f(0), \quad \bigstar\]](http://latex.artofproblemsolving.com/f/4/2/f42d2c25fbc572bc8b39ece524a11346965c4218.png)
gives 
. We plug this into the original equation to get a new assertion:![\[Q(x,y): \ f(x^2-y) + 2yf(x) = x^2f(x)+f(y).\]](http://latex.artofproblemsolving.com/e/c/1/ec18a45d6abc5017b27cdc3515e451ccf6a080a5.png)
gives![\[f(x^2-y) + 2yf(-x) = x^2f(-x) + f(y).\]](http://latex.artofproblemsolving.com/e/b/e/ebe6345cfe5ec8dea026382e4b7b5c2f83f17af1.png)
gives![\[(x^2-2y)(f(x)-f(-x)) = 0,\]](http://latex.artofproblemsolving.com/b/2/3/b232ccfb88d3ec2ccbcd8e65d5cd612354d0b322.png)
, we have for all ; in other words, is even. Then, 
gives![\[2yf(x) = 0,\]](http://latex.artofproblemsolving.com/4/3/b/43b8d5b720ba5403c4e706f73e018be5052d6288.png)
. Plugging this into 
yields 
. Comparing 
and 
gives![\[f(x^2-y^2) + 2y^2f(x) = x^2f(x) + f(y^2) = f(x^2)+f(y^2),\]](http://latex.artofproblemsolving.com/8/3/f/83fe4edb612870b4944640f057033d8d576e50ac.png)
![\[f(y^2-x^2) + 2x^2f(y) = y^2f(y)+f(x^2) = f(y^2)+f(x^2).\]](http://latex.artofproblemsolving.com/d/1/c/d1c97949508988e926503b95ee58ff9a031511a3.png)
, we have 
, or that 
. Setting this equal to a constant yields for some value of and all values of . Then,![\[cx^4 = f(x^2) = f(f(x)) = c^3x^4 \implies c \in \{-1,0,1\}.\]](http://latex.artofproblemsolving.com/f/3/b/f3bfb784ac160a51d768b66c0f45386863e3e8aa.png)
.
.
we get 
Then, substituting 
yields
Subtracting the two equations, we have
so taking 
gives 
,
such that 
for all 
for any constant 
,
for positive 
Similarly, 
yields
Since 
,
,
so by taking nonzero 
,
and said this means 
and did pointwise trap on these ( i forgot about 
)
work.
,
.
for 
gives 
therefore 
.
y 
we get 
.
)
we get 
.
,
we get 
,
,
which cannot happen, therefore 
.
and 
These can all be sought out to satisfy our functional equation.
gives![\[
f(f(x)) = x^2 f(x).
\]](http://latex.artofproblemsolving.com/e/c/b/ecb23d880e8a38e36d39c95f28042f68e20cf98a.png)
![\[
f(x^2) = f(f(x)) + f(0).
\]](http://latex.artofproblemsolving.com/2/3/3/23342964fd5ab28be6965dc4a324e162b87f975b.png)
On the other hand, ![\[
f(x^2) = f(f(-x)) + f(0).
\]](http://latex.artofproblemsolving.com/2/5/0/2508e1ced50542866df79d558b1ada52f3d492e8.png)
Combining these two gives![\[
f(f(-x)) = f(f(x)).
\]](http://latex.artofproblemsolving.com/6/6/d/66d276c7036e8fa69859df4e57036c09ddf115e6.png)
Using ![\[
x^2 f(x) = x^2 f(-x) \rightarrow \boxed{f(x) = f(-x) \text{ for all } x}.
\]](http://latex.artofproblemsolving.com/3/4/e/34e9e875babfd6473189ca77baae75d50b941374.png)
Then ![\[
f(-x) + 2x f(0) = f(f(0)) + f(x).
\]](http://latex.artofproblemsolving.com/7/0/b/70bcbbe957200056821105ee0050b2cf83404f77.png)
Since 
and 
we get 
so 
thus yields![\[
\boxed{f(f(x)) = f(x^2) = x^2 f(x)}.
\]](http://latex.artofproblemsolving.com/e/f/1/ef1259fc642139efaa4b789e1b8aba33ae22d0fb.png)
We now find the value of 
in two different ways. The first is to use the above identity on ![\[
f(f(f(x)) = f(x)^2 f(f(x)) = f(x)^2 \cdot x^2 \cdot f(x) = f(x)^3 \cdot x^2.
\]](http://latex.artofproblemsolving.com/7/9/8/798b8cea5904f5a8db8ba921985cf059b5af408e.png)
The second way is to find 
and stick it into 
We get![\[
f(f(f(x)) = f(f(x^2)) = (x^2)^2 f(x^2) = x^4 \cdot x^2 \cdot f(x) = x^6 \cdot f(x).
\]](http://latex.artofproblemsolving.com/9/5/0/95016044a6e8fd820261800deca2565c79fc154f.png)
Therefore,![\[
x^6 \cdot f(x) = x^2 \cdot f(x)^3.
\]](http://latex.artofproblemsolving.com/9/d/6/9d6aa5c28cbf3695bc1874e9cb3e3370ce8f243e.png)
This implies that 
and 
for nonzero 
Then 
yields![\[
f(b^2 - a) + 2a f(b) = f(f(b)) + f(a) \rightarrow f(b^2 - a) = f(0) + a^2 = a^2,
\]](http://latex.artofproblemsolving.com/d/f/2/df28e3b515fc8cd0b56c9e2102aa872c8ba41e16.png)
while 
yields![\[
f(b^2+a) - 2a f(b) = f(f(b)) + f(-a) \rightarrow f(b^2 + a) = 0 + f(a) = a^2.
\]](http://latex.artofproblemsolving.com/e/1/d/e1d48606701bc342a5ee4a867d8df4dae6a11eac.png)
Since 
we require that 
and 
Thus 
which simplifies down to 
This is impossible since 
and ![\[
f(b^2 - a) + 2a f(b) = f(f(b)) + f(a) \rightarrow f(b^2 - a) = f(0) - a^2 = -a^2,
\]](http://latex.artofproblemsolving.com/3/e/8/3e881045024228bfed4f1e989504e88adf46fd00.png)
while ![\[
f(b^2+a) - 2a f(b) = f(f(b)) + f(-a) \rightarrow f(b^2 + a) = 0 + f(a) = -a^2.
\]](http://latex.artofproblemsolving.com/a/6/f/a6f33d553769ad988fd7f3f43e8a0964b429045a.png)
Since 
we require that 
and 
Thus 
for nonzero ![\[
f(a^2 - b) + 2b f(a) = f(f(a)) + f(b) \rightarrow f(a^2-b) = f(a^2) - 2ba^2 - b^2 = a^2 f(a) - 2ba^2 - b^2 = a^4 - 2ba^2 - b^2
\]](http://latex.artofproblemsolving.com/0/3/c/03ce3908fe28ca13c72bb6f90789d861fd17c122.png)
while 
yields![\[
f(a^2 + b) - 2b f(a) = f(f(a)) + f(-b) \rightarrow f(a^2+b) = f(a^2) + 2ba^2 - b^2 = a^4 + 2ba^2 - b^2.
\]](http://latex.artofproblemsolving.com/d/4/6/d4624b2a13d00fc7dad4fdddc53382577b4af25d.png)
If both of these are equal to 
this clearly implies that 
which is impossible. Thus there are 
subcases from here:
This simplifies to 
impossible.
This also yields 
This simplifies to 
so 
Plugging into ![\[
f(3b) = (2b)^2 + 2b(2b) - b^2 = 7b^2 \ne 0, 9b^2, -9b^2,
\]](http://latex.artofproblemsolving.com/c/5/0/c50badc0d36c369361fe643a1cbbdb351988eff8.png)
which is a contradiction.
This yields 
so 
Plugging into ![\[
f(-3b) = (-2b)^2 - 2b(-2b) - b^2 = 7b^2 \ne 0, 9b^2, -9b^2,
\]](http://latex.artofproblemsolving.com/8/2/0/820b96bd1cd110d1a53af0310f10b39db8d6d98a.png)
which is impossible.
,
to get,
to eventually get 
for all 
.
to get 
pretty straight-forward pointwise trap.
,
