AoPS Academy
grid consisting of 2025 unit squares. Within each unit square is a car, facing either up, down, left, or right. If the square in front of a car in the direction it is facing is empty, it can choose to move forward. Each car wishes to exit the grid.
cars from the grid in such a way that it becomes possible for all the remaining cars to eventually exit the grid. that guarantees that Kritesh's job is possible?
. Let 
and 
be the feet of the altitudes from 
to 
and from 
to 
respectively.
and 
as the reflections of across lines 
and , respectively. Let 
be the circumcircle of 
. Denote by 
the second intersection of line 
with , and by 
the intersection of ray 
with .
is the circumcenter of , prove that , , and are collinear if and only if quadrilateral 
can be inscribed within a circle.
?
be defined by![\[
a_1 = 1, \quad a_{n+1} = a_n + \frac{1}{\sqrt[2024]{a_n}} \quad \text{for } n \geq 1, \, n \in \mathbb{N}
\]](http://latex.artofproblemsolving.com/8/8/f/88f423d87c08b20dc552703fcf30f2a8e9585902.png)
Prove that![\[
a_n^{2025} >n^{2024}
\]](http://latex.artofproblemsolving.com/a/6/8/a6806c817edb7ce29a399981137c1a3e93f63c63.png)
for all positive integers 
.
be the set of positive real numbers. Determine all functions 
such that for all positive real numbers 
and 
![\[f(x+f(xy))+y=f(x)f(y)+1\]](http://latex.artofproblemsolving.com/c/6/a/c6a968a17f6fd5fd637c1ee5d855bdff11e5423a.png)
which obviously works. We now show that it is the only solution.
is injective
Suppose 
and put 
and 
in 
we have
Hence 
as desired. 
is increasing.
and 
. Let 
and 
, where 
, let 
, then
Hence
and so 
from injectivity, which implies , contradiction. 
in we have
Claim. 
for all 
, put 
in ,
so 
, contradiction., 
so
hence
Meanwhile, 
by putting 
in 
. If 
for some 
, define a sequence 
by
then 
, however, it is not hard to see 
is bounded since
hence by recursion
contradiction. 
Proof.
such that 
, then the assertion clearly follows from the increasing property of the function.
in 
, then
Hence there exists sufficiently large 
such that 
. Suppose on the contrary that for every positive real 
, 
for some 
, then sub. 
in ,
contradiction. 
in and let 
, then
Therefore, letting 
in we have
hence 
as desired.
it can be done as follows it follows that, for any 
there exists 
and 
Fix some 
is linear. Further part of solution is quite easy.
of 
when approaches 
, and the lim 
of , when approaches . Use this to prove linearity (consider what happens when you let approach in the FE)
of when approaches , and the lim of , when approaches . Use this to prove linearity (consider what happens when you let approach in the FE)
the assertion of the given F.E. is injective
be positive reals such that . Then by 
Claim 2: is strictly increasing
such that 
and 
then:
We used Claim 1 to show that is strictly increasing becuase its increasing+injective. is lineal. is strictly increasing it makes sence the replace 
where 
. Thus now replacing 
on the original F.E.
Claim 4: for every positive real 
where 
are positive real numbers, then replacing:
Thus we are done 
is bounded sincehence by recursion
be the set of positive real numbers. Determine all functions 
such that for all positive real numbers and 
. Since I love this problem, I will try to give some motivations.
denote the assertion of the given functional equation. 
gives us that 
is injective. Now, we know that if is strictly increasing, then we can let 
, because is increasing and 
. So we have ![\[g(g(0))+y=g(0)f(y)+1\]](http://latex.artofproblemsolving.com/8/9/7/897dd5c9751e5501b93ad0539f227517c77c06ae.png)
implying that is linear. Now we should show that is strictly increasing. One idea we could try to use is that if 
and 
, we should try to get 
through some trick. Now, looking at the functional equation, substituting 
or 
as 
will definitely not yield anything useful. So we now move to the next possibility, that is letting 
to be or 
. We take the assertions 
and 
. These assertions yield us ![\[f(x+f(m))+\frac{m}{x}=f(x)f\left(\frac{m}{x}\right)+1\]](http://latex.artofproblemsolving.com/1/a/c/1acdbe0e1c91758bed7ea8074f3e04c00367cef2.png)
and ![\[f(y+f(n))+\frac{n}{y}=f(y)f\left(\frac{n}{y}\right)+1\]](http://latex.artofproblemsolving.com/5/a/c/5acb87411340af4a08c71f004f92ce7915612a86.png)
Now, if we let 
, then comparing the equations we got, the 
and 
terms cancel off and the 
term is common. Now, if we also assume that 
, we get that 
and so 
by injectivity! Now we should solve the system of equations![\[\begin{cases}
\frac{m}{x}=\frac{n}{y} \\
x+f(m)=y+f(n)
\end{cases}\]](http://latex.artofproblemsolving.com/c/1/0/c108c83a6c82c12288f455ef6dec5b797c9ccea2.png)
to get 
and 
are both positive too, so we can put them in the assertion. So, we have that 
so , a contradiction, thus is strictly increasing. Now that is strictly increasing, from the first paragraphs, we see that is linear. Checking the original assertion yields that 
for all positive reals , and we are done.
denote the condition in the question. is injective.. Comparing 
with 
forces , as needed. is increasing., move 
then this becomes 
.
but 
we can have 
.
where 
.
.
. Then let 
. 
yields 
. Denote this assertion 
. By induction, we can show if 
, then 
. This implies is greater than exponential growth. to get 
for some 
and large enough. Now, we repeat this argument for to get arbitarily large bounds on size of ). In particular, if we fix 
for any 
we can get a contradiction after a couple of "recursions". We can also increase 
by setting 
.
. Note 
yields 
so 
. However, 
is also exponential, so is near linear at , contradiction.
then . Using 
we can get similar arbitrarily large bounds for f.
., 
gives 
gives 
, so 
.
is injective.
., then do to get . is strictly increasing
and 
with and 
(since is injective, showing that this is not possible proves our claim).
is positive.
.![\[\frac{a}{c}+f(a)=\frac{af(b)-af(a)+af(a)-bf(a)}{a-b}=\frac{af(b)-bf(a)}{a-b}.\]](http://latex.artofproblemsolving.com/6/c/5/6c57c4f87e0c9c3f3b3f339a61c4153407f0f602.png)
We also have ![\[\frac{b}{c}+f(b)=\frac{bf(b)-bf(a)+af(b)-bf(b)}{a-b}=\frac{af(b)-bf(a)}{a-b}=\frac{a}{c}+f(a)\]](http://latex.artofproblemsolving.com/d/9/1/d914c33ea07d39bafac28c5114626a3fcb92f974.png)
So doing 
gives 
, so . is linear be the limit when approaches and be the limit when approaches from above. We will show that 
, which implies is linear. arbitrarily close to . Then we get 
. 
Now we get 
. Multiplying by 
gives 
. So 
. Since is real, 
and the only solution is 
, which works.
and I think this defines the difficulty of the whole problem, well at least in my case. Nevertheless thank you Ukraine for the problem.
is a non-decreasing monotonic function.
do not necessarily imply 
What if 
and 
for example? Generally speaking, if 
and 
we do not necessarily have 
being non-decreasing, we cannot have 
so we also cannot have 
or 
You also have to make sure that 
and only then can you say that 
I am unsure what you meant by 
, as is a constant.
, as is a constant.
means 
which is false. I realize "for all" is absurd here.
is a non-decreasing monotonic function. do not necessarily imply What if and for example? Generally speaking, if and we do not necessarily have
is linear be the limit when approaches and be the limit when approaches from above. We will show that , which implies is linear. arbitrarily close to . Then we get . Now we get . Multiplying by gives . So . Since is real, and the only solution is , which works.
is linear be the limit when approaches and be the limit when approaches from above. We will show that , which implies is linear. arbitrarily close to . Then we get . Now we get . Multiplying by gives . So . Since is real, and the only solution is , which works.
is strictly increasing part in his quote.
for all 
, which clearly works. I now prove that this is the only one.
and solve the functional equation over the positive rationals. Then, I prove injectivity and strict monotonicity to finally extend my result to 
and conclude.
.
. I claim the following
Pf:
. If not, then by definition of 
we find
but by our assumption 
and we must have
which contradicts the fact that is the infimum.
, which proves that 
. Consider the sequence 
defined by
which has limit 
. Notice that Equation (1) implies that
and thus we must also have
In particular, by definition of infimum, we must have , as desired. 
Since we have seen that , applying this result to the above yields
which is a contradiction unless we have exactly 
.
, proven in Step~1. is strictly monotone increasing (and injective).
. Since is injective, we must have
for a fixed 
, by looking at the LHS of 
and 
. In particular, this means that we can never have
implying that 
and 
have the same sign, as desired. for all 
. we have 
. Then we can find some rational such that
But since is monotone increasing we must have
a contradiction to 
. is the only function that satisfies the problem statement over 
denote the assertion. We have 
implies 
, so is injective. Next, consider 
which gives![\[f\left(\frac{x}{a}+f(x)\right)+a=f\left(\frac{x}{a}\right)+1\]](http://latex.artofproblemsolving.com/8/d/1/8d18203f00f9be415c7188594baabdcee6bddc1a.png)
Thus, if 
then . Suppose 
then 
for any . If 
then must exist to make that equation come true, so 
, implying that is increasing.
be a number that approaches from the positive side. In particular, 
. Note that 
, so 
gives 
which implies that is linear. Let 
where 
then 
for all positive and which clearly implies . From our derivation of is is clear that works.
.
. Clearly this function works, now we'll prove that only this function satisfies. Let denote the assertion. All variables mentioned should be in 
unless specified.
is injective, then and implies that . As desired.
. First, from 
we have
. While from 
we have
. Plug 
to and get 
plug 
to again to get 
, do this one more time and get
.Next, plug 
to and get 
and plug 
to and get 
. Now from 
, we have
On the other hand, if we plug 
to we will get
. By injectivity we get
. Hence 
. As desired.
is strictly increasing
, assume 
. Note that 
shows
. Where the LHS is symmetric in so swapping them and using injectivity gives . A contradiction. Hence we must have 
since 
.
and to inductively prove 
for all 
. Then from 
we have
. Setting to 
gives 
. If for some then plug that to and get 
. Contradiction. As desired.
we know 
. And also since ,
. Assume 
, then 
for some constant 
and all 
. From 
, we have
. On the other hand from 
we have
. So 
for some arbitrarily large . Set 
to the inequality and set 
to get a contradiction.
implies 
, so 
, lastly set 
at and get
. And we are finished.
be the set of positive real numbers. Determine all functions 
such that for all positive real numbers and : is strictly increasing is injective, then we show that it's nondecreasing. Injectivity is obvious setting in the original equation, we get 
. Now suppose FTSOC that there exist some with . Let 
and 
and 
, then we have 
. So:
Comparing, we have 
, so 
(injectivity), so , contradiction.
for some constants 
, so is linear. Testing, we have that .
is the only possible solution. This clearly works.
,
is injective. Setting 
and 
,
for all positive 
.
.
exists for all 
.
is decreasing, and it converges to 
to 
.
with 
,
.
can be expanded in two ways in the given FE, so we have ![\[f(x+f(y))f\left( \frac z{x+f(y)} \right)-\frac z{x+f(y)}=f(x+f(z))f\left( \frac y{x+f(z)} \right)-\frac y{x+f(z)}.\]](http://latex.artofproblemsolving.com/e/b/7/eb7202df7f60b9f092e9178db0246059786e6e5e.png)
Now suppose 
.![\[\frac{zf(z)-yf(y)}{y-z}>0,\]](http://latex.artofproblemsolving.com/2/9/3/293510a7b29e6a6836d24723266646fb9d337a52.png)
so setting 
gives ![\[\frac y{x+f(z)}=\frac z{x+f(y)}\implies f(x+f(y))=f(x+f(z))\implies f(y)=f(z)\implies y=z,\]](http://latex.artofproblemsolving.com/1/9/6/196f9a59b1f8f030d44fc5a823db844f2efd2180.png)
contradiction. 
.
means that 
for all ![$x\in[a,b]$](http://latex.artofproblemsolving.com/4/9/4/49432e6cff349a39878727bec9bfcb0efc9fbb7c.png)
.![\[f(x+f(xy))+y=f(x)f(y)+1=f(y+f(xy))+x\implies f(x+f(xy))=f(y+f(xy))+x-y,\]](http://latex.artofproblemsolving.com/8/c/8/8c849e32a6a85ae459eb02abe77490ae6c6c5ad9.png)
and fixing 
while varying ![\[f(x+f(1))=f\left( \frac1x+f(t) \right)+x-\frac1x.\]](http://latex.artofproblemsolving.com/d/a/e/dae68698c02d81e21b77830f8a95cab8abab7d99.png)
and 
.
,
.
such that 
.![\[C>f(x+f(1))=f(z)+x-z+f(1)>f(z)-z\implies f(z)<z+C\]](http://latex.artofproblemsolving.com/3/c/f/3cf2a380757f04670a5aa69caf2ebafe990eaae2.png)
and ![\[0<f(x+f(1))=f(z)+x-z+f(1)<f(z)-z+C\implies f(z)>z-C,\]](http://latex.artofproblemsolving.com/1/d/c/1dcfbc91c6077d877c18b094f8496dd71c44707d.png)
as desired. 
.
is also sufficiently large, then 
is also bounded above by 
for all sufficiently large ![\[f(x+f(xy))-x-xy=f(x)f(y)-xy-x-y+1\]](http://latex.artofproblemsolving.com/7/1/7/717e843006cf7e2a33b0308d9b04358196e53559.png)
and ![\[(f(x)-x-1)y-Cf(x)-x+1<f(x)f(y)-xy-x-y+1<(f(x)-x-1)y+Cf(x)-x+1,\]](http://latex.artofproblemsolving.com/b/7/3/b73dd7e2c9096ba95deaa169a661f97e087e9f83.png)
which implies that 
,
such that 
, let 
and 
leads to 
, which makes a contradiction due to injectivity
in 
Clearly 
, so 
is the only solution
?
So for any 
Q.E.D 
now from injectivity it follows,
Setting 
and 
But this means RHS is always non-positive, fulfilling our claim. 
Set 
and 
For any 
So we have 
Moreover, due to 
which works.
