Two problems

[gribozavr]

Here are two problems from the Ukrainian Mathematics Olympiad 2006/2007.

1. Let's look at a sequence of letters (symbols?) that satisfies the following conditions:
a. there are at most n unique letters;
b. there are no two same sequential letters (sequence AA is not valid);
c. there isn't any sequence like ABAB, that is, there are no j < k < l < m for which , .

For example, for n=5 sequence ABACADE is valid, but ABCADAEC is not, because and .

Question: what is the longest sequence for a given n?


2. Find all functions f: R -> R that the following is true for all real x, y:

[retina]

Is that the entire question statement? I think you left out some vital information about why ABAB etc. is invalid.

[akruppa]

See the "there is no j < k < l < m for which x_j = x_l, x_k = x_m." condition.

Alex

[grandpascorpion]

1) 2n-1

I don't think you can improve on either of these solutions
nested (i.e. ABCBA) or alternating (i.e. ABACA )


2) One solution is f(x)=x
f(x^2-f(y)^2) = f(x^2 -y^2) = x^2-y^2 = x*f(x)-y^2

[gribozavr]

1. Right.

2. My "proof" that f(x) = x is the only one such function.
(I considered only functions defined by formula)
Let's find all functions which satisfy the conditions for x = 0, and then keep only that satisfy for x E R.


(I'm unsure in this step) From that follows that f(x) is a first-degree polynomial. That is, f(x) = kx+b.

I'll stop here and ask: does last sentence make any sense?

[wblipp]

Originally Posted by gribozavr

2. Find all functions f: R -> R that the following is true for all real x, y:

Should we interpret as or as ?

[grandpascorpion]

I picked the latter.

[gribozavr]

[wblipp]

Originally Posted by gribozavr

That makes it easier. Where I was taught, that would have been written as .

My proof that grandscorpion's "one solution" is the only solution follows. I think it's more complete than gribozavr attempt to show the same thing

1. Let y=0 and x=f(0). From this we see that
f(f(0)[sup]2[/sup]-f(0)[sup]2[/sup]) = f(0)[sup]2[/sup] - 0[sup]2[/sup]
f(0) = f(0)[sup]2[/sup]

Thus f(0) is zero or one.

Suppose f(0)=1
Let x=0 and y=0. Then
f(0[sup]2[/sup]-f(0)[sup]2[/sup])=0f(0)-0[sup]2[/sup]
f(-1) = 0

Then let x=-1 and y=0.
f((-1)[sup]2[/sup]-f(0)[sup]2[/sup]) = -f(-1) - 0[sup]2[/sup]
f(0) = 0, a contradiction. Hence f(0) must be zero.

Now let x=f(y)
f(f(y)[sup]2[/sup]-f(y)[sup]2[/sup]) = f(y)[sup]2[/sup]-y[sup]2[/sup]
f(0) = f(y)[sup]2[/sup]-y[sup]2[/sup]
0 = f(y)[sup]2[/sup]-y[sup]2[/sup]

Hence f(y)=y or f(y)=-y.

Suppose f(y)=-y for all real values of y - this quickly leads to a contradiction,

f(x[sup]2[/sup]-f(y)[sup]2[/sup]) = xf(x)-y[sup]2[/sup]
-x[sup]2[/sup]+f(y)[sup]2[/sup] = x(-x)-y[sup]2[/sup]
-x[sup]2[/sup]+(-y)[sup]2[/sup] = -x[sup]2[/sup]-y[sup]2[/sup]
y[sup]2[/sup]=-y[sup]2[/sup], which is true for only y=0, not for all y.

Leaving grandscorpion's solution as the only possible solution

[grandpascorpion]

William,

One small thing:

In the first step, if x=f(0) and y=0,
the right side of the equation isn't : f(0)^2 -0^2

It's : f(0)*f(f(0)) - 0^2

So, f(0) = f(0)*f(f(0))

f(0) = 0 => f(f(0))= 0
f(0) !=0 => f(f(0))=1
So, f(f(0)) = 1 unless f(0)=0

[wblipp]

Originally Posted by grandpascorpion

One small thing:

It's hardly a small thing. I made the same error again later in my argument, which completely invalidates my argument and I haven't been able to fix it up.

I can prove that zero is the only root of f(x). I can prove that f(x) is an odd function. I can prove that if f(x) has a Maclaurin series (Taylor series about zero) then your solution is the only solution. But I don't see a complete proof that your solution is the only solution.