20070124, 23:08  #1 
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?) 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: 
20070125, 10:29  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}·3·17·31 Posts 
Is that the entire question statement? I think you left out some vital information about why ABAB etc. is invalid.

20070125, 12:03  #3 
"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 
20070125, 18:36  #4 
Jan 2005
Transdniestr
1F7_{16} Posts 
1) 2n1 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^2f(y)^2) = f(x^2 y^2) = x^2y^2 = x*f(x)y^2 
20070127, 19:23  #5 
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. (I'm unsure in this step) From that follows that f(x) is a firstdegree 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 20070127 at 19:24 
20070131, 06:12  #6 
"William"
May 2003
New Haven
100101000001_{2} Posts 

20070131, 15:27  #7 
Jan 2005
Transdniestr
503 Posts 
I picked the latter.

20070131, 18:40  #8 
Mar 2005
Internet; Ukraine, Kiev
11·37 Posts 

20070131, 20:09  #9 
"William"
May 2003
New Haven
23×103 Posts 
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 
20070131, 23:27  #10 
Jan 2005
Transdniestr
503 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 
20070202, 06:49  #11 
"William"
May 2003
New Haven
2369_{10} Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What problems are detected  MrAskew  Information & Answers  1  20100924 13:48 
PC problems  Nimras  Information & Answers  6  20091215 21:24 
Readline problems  CRGreathouse  Software  11  20090707 05:18 
Need help with few problems  Laserjet  Hardware  1  20071013 10:59 
Number problems.  mfgoode  Puzzles  7  20060329 16:34 