symmetric 2 variable function

Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following: $$f(i,j) + f(j,i) = 0 \forall i,j \in S$$ Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$. Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.

From a friend

From a friend

If $f(x) = \sec(x^{333})$ then find $f^{666}(x)$ Where $f^n(x)$ represents the $n$-th derivative of a function.

Solution

At first this looks crazy but we quickly notice that a lot of terms in the 666-th derivative will evaluate to zero at $x=0$. More precisely, the first derivative contains factors $\sec(x^{333}), \tan(x^{333}),$ and $x^{332}$.

The tangent and the $x^n$ factors evaluate to zero, but the secant factor evaluates to 1. So all we need to figure out is, at each derivative step, which terms will affect the final derivatives.

To make it clearer, let's generalize into: $f(x) = \sec(x^n)$. $$f^1(x) = nx^{n-1} \sec(x^n) \tan(x^n)$$ $$f^2((x) = n^2x^{2n-2} \sec(x^n) \tan^2(x^n) + n(n-1)x^{n-2} \sec(x^n) \tan(x^n) + n^2 x^{2n-2} \sec^3(x^n)$$ The first term will continue to have higher derivatives with higher powers of $x$ and $\tan(x^n)$. Ditto for the second term. What we need to worry about is only the third term.

Integer solutions

Let $f(t) = t(t-1)$. Find all positive integers $x,y$ such that $$f(x) + f(y) = f(x+y) / 2$$ First Solution Expanding and canceling, we have: $$x^2+y^2-2xy = x+y$$ It's easy to see that there's no solution for $x=y$. The above equation is now equivalent to: $$16x^2+16y^2+1-8x-8y+32xy = 64xy+8x+8y+1$$ $$(4x+4y-1)^2 = (8x+1)(8y+1)$$ Because both quantities are positive, we have: $$4x+4y-1 = \sqrt{8x+1} \sqrt{8y+1}$$ Once again rearranging, $$(8x+1) - 2\sqrt{8x+1} \sqrt{8y+1} + (8y+1) = 4$$ $$(\sqrt{8x+1} - \sqrt{8y+1})^2 = 4$$ If $x=y$, then there is no solution WLOG, we may assume that $x > y$, so that $$\frac{\sqrt{8x+1}}{2} - \frac{\sqrt{8y+1}}{2} = 1$$ Note that $g(t) = \frac{1+\sqrt{8t+1}}{2}$ is the reverse triangular number function. Thus, any two consecutive triangular numbers (for example 3 and 6, 6 and 10, and so on) are a solution.

Now we show that there's no other solution. The equation is equivalent to $g(x) - g(y) = 1$. In order for $g(x)$, to be an integer, we must have $8x + 1 = k^2$ for some $k$. But $k$ is odd, so $8x+1 = 4m^2 + 4m + 1$ which means $x = m(m+1)/2$ is a triangular number

Now suppose $g(x)$ is not an integer, then it will be irrational, and so will $g(y)$. They both have form of $a+\sqrt{b}$ with $a,b$ rational, but with different $b$s, because $x \neq y$. The difference can't be rational, a contradiction.

Thus, the only solutions are two consecutive triangular numbers. Second Solution Let $d = \gcd(x,y)$, and $x = dm, y = dn$ with $m,n$ coprime. Upon substitution and rearranging, we have: $$d(m-n)^2 = m+n$$ Clearly $m=n$ is not a solution. Now wlog let $m < n$ and $n = m + k$ $$dk^2 = 2m+k$$ Because $k$ divides $dk^2$ and $2m$ then $k$ divides $2m$. Because $m$ and $n$ are coprime, then $k$ and $m$ are coprime. Thus we have $k=1$ or $k=2$.

For $k=1$, $d = 2m+1, n=m+1$, so $x = (2m+1)m,y=(2m+1)(m+1)$.

For $k=2$, $d = (m+1)/2, n=m+2$, and obviously we can only use odd values of $m$. Suppose $m = 2l+1$, then $d = l+1, n=2l+3$, so $x=(l+1)(2l+1), y =(l+1)(2l+3)$. Interestingly, this form is the same as the case for $k=1$, except we substitute $m = l + 1/2$

Combining the two cases, we can conclude that the solution must have form of $m(2m+1),(m+1)(2m+1)$ for $m$ multiples of 1/2, or equivalently, $k(k+1)/2, (k+1)(k+2)/2$ for $k$ any integers. In other words, they must be two consecutive triangular numbers.

Function Composition

Are there real-valued continuous functions $f,g$ defined on real numbers such that
$$f(g(x)) = x^{2011}$$
and
$$g(f(x)) = 2011x$$

for all $x$?

Solution

Applying $g$ to both sides, we have:
$$g(f(g(x))) = g(x^{2011})$$
$$2011g(x) = g(x^{2011})$$

Let $x = 1$, we have $g(1) = 0$

Let $P(y) = g(e^y)$ defined on all $y$ real numbers.
So $P(2011y) = g(e^{2011y}) = g((e^y)^{2011}) = 2011g(e^y) = 2011P(y)$
We conjecture that $P(y) = ay$ for some $a$. Setting $x = e^y$, we have:
$$g(x) = g(e^y) = P(y) = ay = a \log x$$

Now plugging back in, our second equation becomes:
$$a \log f(x) = 2011 x$$
$$f(x) = e^{2011x / a}$$

Testing for compatibility with first equation:

$$f(g(x)) = e^{2011 a \log x / a} = e^{2011 \log x} = x^{2011}$$

Symmetric Function in 3 Variables

A function $f$ is defined from a triplet of positive reals to a positive real number $f:R_+^3 \to R_+$ and satisfies the following:

1. $f$ is symmetric in all 3 variables. That is $f(a,b,c) = f(b,a,c) = f(a,c,b) = ...$
2. For any positive real $t$, $f(ta,tb,tc) = tf(a,b,c)$
3. $f(1/a, 1/b, 1/c) = 2011^2/f(a,b,c)$
4. $f(a,b,c) = f(\sqrt{ab}, \sqrt{ab}, c)$

Determine how many triplet of positive integers $(x,y,z)$ are there such that $f(1/x,1/y,1/z) = 1$

Solution

From rule 3, we have $f(1,1,1) = 2011^2/f(1,1,1)$, so $f(1,1,1) = 2011$.

Now, for any $u,v > 0$,
$f(u,v,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
and
$f(uv,1,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
So
$f(u,v,1/(uv)) = f(uv,1,1/(uv)) = f(uv, 1/(uv), 1) = f(1,1,1) = 2011$

Now, for any $t,u,v$, let $k = \sqrt[3]{tuv}$, then $t = k^3/uv$
$f(t,u,v) = f(k^3/uv, u, v) = kf(k^2/uv, u/k, v/k) = kf(u/k, v/k, 1/((u/k)(v/k))) = 2011k = 2011\sqrt[3]{tuv}$

Thus $f(t,u,v) = 2011\sqrt[3]{tuv}$ for all $t,u,v$.

Now we need to determine the number of positive integer triples $(x,y,z)$ such that
$$f(1/x,1/y,1/z) = \frac{2011}{\sqrt[3]{xyz}} = 1$$
$$xyz = 2011^3$$
Since 2011 is a prime, there are only the following possibilities:
1. $(1,1,2011^3)$ and all its permutations, there are three triplets.
2. $(1,2011, 2011^2)$ and all its permutations, there are six triplets.
3. $(2011,2011,2011)$, there is one triplet.

So in total, there are ten triplets that satisfy the condition.

The above conditions could be tailored to fit any symmetric functions. For example, for $f = a^2 + b^2 + c^2 + k$ one can have the following conditions:

1. $f$ is symmetric
2. $f(\sqrt{a^2+t},b,c) = f(a,b,c) + t$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(\sqrt{(a^2+b^2)/2},\sqrt{(a^2+b^2)/2},c)$

Likewise, for $f = ab+bc+ca$ one can have the following conditions (really hard):
1. $f$ is symmetric
2. $f(a+t,b,c) = f(a,b,c) + t(b+c)$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(k,k,c)$ where $k = \sqrt{(a+c)(b+c)}-c$

Largest k for arbitrary function

Find the largest number $k$ that satisfies the following property:

For every real-valued function $f$ defined over $[0,1]$, there exist $a,b,c \in [0,1]$ such that:
$$|f(ab) + f(bc) + f(ca) - abc | \geq k$$

Solution

First we show that $k = 1/6$ satisfies the condition of the problem.

For $k=1/6$, suppose to the contrary that for all $a,b,c$ chosen in the interval $[0,1]$ we have:
$$|f(ab) + f(bc) + f(ca) - abc | < \frac{1}{6}$$

Let $y = f(0),y=f(1)$.
Plugging in $a=b=c=0$ we have $|3x| < 1/6 \iff |x| < 1/18$
Plugging in $a=b=c=1$ we have $|3y-1| < 1/6$
Plugging in $a=b=1, c=0$ we have $2x+y| < 1/6$

That means $y = (2x+y) - 2x < 1/6 + 2/18 = 5/18$
But also $3y-1 > -1/6 \iff y > 5/18$, a contradiction.

Thus $k= \frac{1}{6}$ satisfies the condition of the problem.

Now we show that it is the largest such constant. We choose a function $f(x) = \frac{6x^\frac{3}{2} - 1}{18}$ and prove that
$$ -\frac{1}{6} \leq f(ab)+f(bc)+f(ca) - abc \leq \frac{1}{6}$$
for all $a,b,c \in [0,1]$

Indeed, the first inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} \geq 3abc$$ which is true by AM-GM.

The second inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} - 3abc \leq 1$$

Now consider the LHS, and try to find its maximum value over $a,b,c \in [0,1]$
First, we try a substitution $x = \sqrt{ab}, y = \sqrt{ac}, z = \sqrt{bc}, x,y,z \in [0,1]$ and WLOG, we may assume that $x \geq y \geq z$ (which corresponds to $a \geq b \geq c$)
So now our objective function becomes $x^3 + y^3 + z^3 - 3xyz$.

Let $g(x) = x^3 + y^3 + z^3 - 3xyz$, and fix $y,z$.
$$g(1) - g(x) = (1-x^3) - 3yx(1-x) = (1-x)(1 + x + x^2 - 3yz)$$
Because $x \leq 1$, then $1-x \geq 0$
$1+x+x^2-3yz \geq 1 + 2x^2-3yz = (1-yz) + 2(x^2 - yz) \geq 0$
So $g(1) \geq g(x)$.

So the maximum happens when the largest of 3 variables equals to 1. But this means that $ab = 1$ which implies $a=b=1$. Then $y = z = \sqrt{c}$. Our objective function now becomes:
$$x^3 + y^3 + z^3 - 3xyz = 2y^3 - 3y^2 +1$$
Let $h(y) = 2y^3 - 3y^2 + 1$, then $h(y) - h(0) = y^2(2y-3) < 0$ because $y \geq 1$. So the maximum happens when $y = 0$

In conclusion, our maximum happens when $x = 1, y=z=0$ and that's when $a=b=1, c= 0$. At this point, the maximum value is 1, thus proving our assertion.

Another way to determine the maximum value of the function above is by observing that it is a convex function on each of its variable, and all three variables are freely chosen from the interval $[0,1]$. Thus, the maximum must happen when all of its variables are zero or one. Plugging in all permutations of $(0,0,0), (0,0,1), (0,1,1), (1,1,1)$, we find that the maximum is indeed 1.

3 arbitrary functions

Suppose $f,g,h$ are functions that are defined in the closed interval $0 \leq x \leq 1$. Show that we can always find $a,b,c \in [0,1]$ such that:

$$|f(a)+g(b)+h(c) - (1-a)(1-b)(1-c)| \geq \frac{1}{3}$$

Also show that the constant $\frac{1}{3}$ cannot be replaced by a larger constant.