mersenneforum.org Two problems
 User Name Remember Me? Password
 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 22·3·17·31 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 1F716 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

1001010000012 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 503 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

23×103 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 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
2007-02-02, 06:49   #11
wblipp

"William"
May 2003
New Haven

236910 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 17:17.

Mon Jan 17 17:17:03 UTC 2022 up 178 days, 11:46, 0 users, load averages: 1.17, 1.16, 1.19

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔