mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-01-24, 23:08   #1
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11×37 Posts
Default 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
gribozavr is offline   Reply With Quote
Old 2007-01-25, 10:29   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·3·17·31 Posts
Default

Is that the entire question statement? I think you left out some vital information about why ABAB etc. is invalid.
retina is offline   Reply With Quote
Old 2007-01-25, 12:03   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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

Alex
akruppa is offline   Reply With Quote
Old 2007-01-25, 18:36   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1F716 Posts
Default



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

grandpascorpion is offline   Reply With Quote
Old 2007-01-27, 19:23   #5
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11·37 Posts
Default

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
gribozavr is offline   Reply With Quote
Old 2007-01-31, 06:12   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001010000012 Posts
Default

Quote:
Originally Posted by gribozavr View Post
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?
wblipp is offline   Reply With Quote
Old 2007-01-31, 15:27   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

I picked the latter.
grandpascorpion is offline   Reply With Quote
Old 2007-01-31, 18:40   #8
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11·37 Posts
Default

f^2(y) = (f(y))^2
gribozavr is offline   Reply With Quote
Old 2007-01-31, 20:09   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Default

Quote:
Originally Posted by gribozavr View Post
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
wblipp is offline   Reply With Quote
Old 2007-01-31, 23:27   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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

grandpascorpion is offline   Reply With Quote
Old 2007-02-02, 06:49   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236910 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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.
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What problems are detected MrAskew Information & Answers 1 2010-09-24 13:48
PC problems Nimras Information & Answers 6 2009-12-15 21:24
Readline problems CRGreathouse Software 11 2009-07-07 05:18
Need help with few problems Laserjet Hardware 1 2007-10-13 10:59
Number problems. 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

Powered by vBulletin® Version 3.8.11
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.

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