mersenneforum.org Two problems
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-24, 23:08 #1 gribozavr     Mar 2005 Internet; Ukraine, Kiev 11×37 Posts Two problems Here are two problems from the Ukrainian Mathematics Olympiad 2006/2007. 1. Let's look at a sequence of letters (symbols?) ${x_i}$ 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 $x_j = x_l$, $x_k = x_m$. For example, for n=5 sequence ABACADE is valid, but ABCADAEC is not, because $x_1 = x_4 = A$ and $x_3 = x_8 = C$. 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: $f(x^2 - f^2(y)) = xf(x) - y^2$
 2007-01-25, 10:29 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 23×5×7×23 Posts Is that the entire question statement? I think you left out some vital information about why ABAB etc. is invalid.
 2007-01-25, 12:03 #3 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts See the "there is no j < k < l < m for which x_j = x_l, x_k = x_m." condition. Alex
 2007-01-25, 18:36 #4 grandpascorpion     Jan 2005 Transdniestr 503 Posts 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
 2007-01-27, 19:23 #5 gribozavr     Mar 2005 Internet; Ukraine, Kiev 11·37 Posts 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. $f(-f^2(x)) = -y^2$ (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? Last fiddled with by gribozavr on 2007-01-27 at 19:24
2007-01-31, 06:12   #6
wblipp

"William"
May 2003
New Haven

45038 Posts

Quote:
 Originally Posted by gribozavr 2. Find all functions f: R -> R that the following is true for all real x, y: $f(x^2 - f^2(y)) = xf(x) - y^2$
Should we interpret $f^2(y)$ as $f(f(y))$ or as $(f(y))^2$?

 2007-01-31, 15:27 #7 grandpascorpion     Jan 2005 Transdniestr 50310 Posts I picked the latter.
 2007-01-31, 18:40 #8 gribozavr     Mar 2005 Internet; Ukraine, Kiev 11×37 Posts $f^2(y) = (f(y))^2$
2007-01-31, 20:09   #9
wblipp

"William"
May 2003
New Haven

2,371 Posts

Quote:
 Originally Posted by gribozavr $f^2(y) = (f(y))^2$
That makes it easier. Where I was taught, that would have been written as $f(y)^2$.

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

 2007-01-31, 23:27 #10 grandpascorpion     Jan 2005 Transdniestr 7678 Posts 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
2007-02-02, 06:49   #11
wblipp

"William"
May 2003
New Haven

2,371 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post MrAskew Information & Answers 1 2010-09-24 13:48 Nimras Information & Answers 6 2009-12-15 21:24 CRGreathouse Software 11 2009-07-07 05:18 Laserjet Hardware 1 2007-10-13 10:59 mfgoode Puzzles 7 2006-03-29 16:34

All times are UTC. The time now is 05:54.

Mon May 16 05:54:21 UTC 2022 up 32 days, 3:55, 0 users, load averages: 1.64, 1.37, 1.31