Maths Olympiad 2008 question...

[ken_cck_kid]

hey i sat for the maths olympiad exam last week n i cant solve this.. can anyone help out???

1)

given
f(2)=7
f(x+2) << f(x) +2
f(x+7)>>(x)+7

find f(2008 )

___________________________________________________________---


2) given S= (2+1)(2^2+1)(2^4+1)(2^8+1)....(2^1024+1) + 1

FIND S^(1/512)
_____________________________________________________________

btw no calculator is allowed as that was wat the examiner told me. haha... pls help to solve.. thanks..

[youngyew]

The second question is a simple induction exercise; haven't had time to figure out how to do it without induction.

[bluez_aspic]

There seems to be several typos in the first question. I believe the actual formulation should be as thus:

"Given a function f(x) which satisfies the following relationships:

f(2)=7
f(x+2) <= f(x) +2
f(x+7) => f(x)+7

Find f ( 2008 )."

Playing around with the equations a bit would give you a hunch that the proper expression for f should be f(x)= x+5. You would then need to cobble out a proper proof - using induction, and fiddling with the equations - to show that this is indeed the case. So the answer is f( 2008 )=2013.


For the second question, the answer is 2^4. As youngyew pointed out, this could be done via an induction proof to show that:

2^(2^(n+1)) = (2+1)(2^2+1)(2^(2^2)+1)... (2^(2^n)+1)+2

(it's actually a well-known property of what is known as Fermat primes)

Another way of doing it would be to observe that:

(2^(2^n)+1)-2 = (2^(2^(n-1))-1)(2^(2^(n-1))+1)

You can then do recursion using this relationship to get the same equation as in the induction proof (so both methods are actually equivalent).


(sorry but too tired to write out a full-length proof tonight - if anyone is interested I can talk about the motivation and the reasoning process behind the solutions)

[nigelsim]

de ans to de 2nd one is 2^4 not 4... u can expand partly n see de pattern

[bluez_aspic]

de ans to de 2nd one is 2^4 not 4... u can expand partly n see de pattern
Ouch, thanks for pointing out the mistake. Original post edited.

[ken_cck_kid]

i still dun really understand the answer to the first ques.. it has to agree with the two condition given.. moreover it is a structure question, so by writing f(x)= x +5 doesnt really agrees with the two condition given...:wink

[bluez_aspic]

Oh, if you're interested I can scan the relevant section from Terence Tao's 'Solving Mathematical Problems' on this variety of questions. A charming and lucid book (written when he was 15!) - but damn expensive (only bought it at a whim).

It is easy to see that "f(x+2) <= f(x)+2" implies "f(x) <= f(2)+(x-2)". Now substitute x=2008 - this would yield f( 2008 )<=2013. Likewise, you can play around with the third equation "f(x+7) => f(x)+7" to get a lower bound on f( 2008 ). So we now have: f(6)+2002 <= f( 2008 ) <= 2013.

It would be nice if the inequalities were turned into equalities i.e. f(6)+2002 = f( 2008 ) = 2013. In which case, f(x)=x+5 fits snugly! Of course, this is only a hunch - you would then need to PROVE that this is indeed the case. This usually involves proof by induction and some manipulation of the constraints (i.e. equations 2 and 3).

[youngyew]

Oh, if you're interested I can scan the relevant section from Terence Tao's 'Solving Mathematical Problems' on this variety of questions. A charming and lucid book (written when he was 15!) - but damn expensive (only bought it at a whim).
And you never told me you had it! :nod But don't really think I have much time left for it anyway. :(

[bluez_aspic]

And you never told me you had it! :nod But don't really think I have much time left for it anyway. :(
You don't need it :P It's a good book though for those starting out on Mathematical Olympiad preparation - he talks in great detail his line of reasoning, how he developed his solutions and the motivation/inspiration behind his ideas. Actually he does that in most of his papers too - extremely generous (unlike most academics).

Olympiad style questions are not that fun anyway - I like the Australian Mathematics Competition ones :D Used to have a compilation of them too but gave them away last year.

[chiunlin]

@<hidden>, what is obvious to you may not be obvious to a high school student.

The first question should go something like this:
You have to find a way to relate what is given, f(2) with what you want to find, f(2008 ). First play around with the first inequality. If you plug in x = 2006, you get
"f(2008 ) <= f(2006) + 2."Observe that the argument in the function has decreased by 2 and since you want to relate it to f(2), it should be straightforward to see that you should keep applying the first inequality. Then you get
"f(2008 ) <= f(2006) + 2 <= f(2004) + 4 <= ... <= f(2) + 2006 = 2013"

Next do the same with the second inequality and you get
"f(2008 ) >= f(2001) + 7 >= f(1994) + 14 >= ...>= f(6) + 2002"

If you stare at those two long list of inequalities hard enough, you see, from the first inequality,
"f(2008 ) <= f(1994) + 14" and from the second inequality
"f(2008 ) >= f(1994) + 14"
When "a >= b" and "b >= a" are both true(or "a<= b <= a"), it implies( by sandwiching) a = b so
f(2008 ) = f(1994) + 14.

Then generalize to get f(2008 ) = f(1994) + 14 = f(1980) + 14 = ... = f(20)+ 1988 = f(6) + 2002.

Too bad f(2) is not among the list, but we're not quite done applying what we know yet.
From the first long list of inequality we also have
"f(20) + 1988 <= f(18 ) + 1990 <= ... <= f(6) +2002"
Again since the upper and lower bound are equal, we have
f(20) + 1988 = f(18 ) + 1990 = ... = f(6) + 2002.

We still don't have f(2) yet, but we have f(16). And applying the first two inequalities, we have from first inequality
"f(16) <= f(2) + 14"
From second inequality
"f(16) >= f(2) + 14"
So we conclude f(16) = f(2) + 14.
Putting everything together, we have f(2008 ) = f(16) + 1992 = f(2) + 14 + 1992 = 7 + 2006 = 2013.
q.e.d.

I don't think you need to prove that f(x) = x + 5. And this question would have been easier without the restriction that f has to be a positive integer function.

[bluez_aspic]

I don't think you need to prove that f(x) = x + 5. And this question would have been easier without the restriction that f has to be a positive integer function.

Hmm, now that you pointed it out - yeah, the restriction is unnecessary (so I've edited my original post to reflect that). What I had in mind when I chucked in the restriction was for the function f to take on only integer values (the 'positive' was just stupid), but turns out it wasn't necessary in this case (had the problem involved '<' instead of '<=' then the restriction could have been necessary).

I finally sat down and worked the problem out proper :P Turns out that to establish the base case for strong induction was complicated (because of the damn f(x+7), but not impossible), but I came up with this which is a bit similar to yours:

We have:
(i) f(x+2) <= f(x)+2
(ii) f(x)+7 <= f(x+7)

Now, f(x+2) <= f(x)+2 <= f(x+7)-5. f(x+2) <= f(x+7)-5 can be rewritten as f(x) <= f(x+5)-5. We can continue likewise: f(x+2) <= f(x)+2 <= f(x+5)-3, which is equivalent to f(x) <= f(x+3)-3. Again, f(x+2) <= f(x)+2 <= f(x+3)-1 which implies f(x) <= f(x+1)-1.

Using the inequality f(x) <= f(x+1)-1, we deduce that f(x) <= f(x+1)-1 <= f(x+2)-2 which is the same as f(x)+2 <= f(x+2). Comparing this with the first inequality (i), we establish that f(x+2) = f(x)+2. f( 2008 ) can then be easily computed. Done!

From here it is not difficult to establish the stronger result that f(x) = x+5 via (strong) induction, because we can legitimately replace 'f(x)+7 <= f(x+7)' with 'f(x)+1 <= f(x+1)'.

[chiunlin]

It's kinda amusing to note how our training affects the way we approach the problem and how we write up the solution.

You work entirely with f(x) and the two inequalities and only substitute in a value for x at the end to get the answer while I get my hands dirty and play with different values of x from the start till the end.

[ken_cck_kid]

@<hidden>, what is obvious to you may not be obvious to a high school student.

The first question should go something like this:
You have to find a way to relate what is given, f(2) with what you want to find, f(2008 ). First play around with the first inequality. If you plug in x = 2006, you get
"f(2008 ) <= f(2006) + 2."Observe that the argument in the function has decreased by 2 and since you want to relate it to f(2), it should be straightforward to see that you should keep applying the first inequality. Then you get
"f(2008 ) <= f(2006) + 2 <= f(2004) + 4 <= ... <= f(2) + 2006 = 2013"

Next do the same with the second inequality and you get
"f(2008 ) >= f(2001) + 7 >= f(1994) + 14 >= ...>= f(6) + 2002"

If you stare at those two long list of inequalities hard enough, you see, from the first inequality,
"f(2008 ) <= f(1994) + 14" and from the second inequality
"f(2008 ) >= f(1994) + 14"
When "a >= b" and "b >= a" are both true(or "a<= b <= a"), it implies( by sandwiching) a = b so
f(2008 ) = f(1994) + 14.

Then generalize to get f(2008 ) = f(1994) + 14 = f(1980) + 14 = ... = f(20)+ 1988 = f(6) + 2002.

Too bad f(2) is not among the list, but we're not quite done applying what we know yet.
From the first long list of inequality we also have
"f(20) + 1988 <= f(18 ) + 1990 <= ... <= f(6) +2002"
Again since the upper and lower bound are equal, we have
f(20) + 1988 = f(18 ) + 1990 = ... = f(6) + 2002.

We still don't have f(2) yet, but we have f(16). And applying the first two inequalities, we have from first inequality
"f(16) <= f(2) + 14"
From second inequality
"f(16) >= f(2) + 14"
So we conclude f(16) = f(2) + 14.
Putting everything together, we have f(2008 ) = f(16) + 1992 = f(2) + 14 + 1992 = 7 + 2006 = 2013.
q.e.d.

I don't think you need to prove that f(x) = x + 5. And this question would have been easier without the restriction that f has to be a positive integer function.


i prefer n understand ur method..thanks...

[leinad]

btw. did those who went out early because they finished early or they gave up??
fyi, why all the previous solutions in this thread seem to be so complex.??

f(2) =7
f(x+2)<f(x)+2
f(x+7)>f(x)+7

i lazy to find the bigger/smaller and equal to symbol so pandai pandai la.

my ans would be

sub x = 2
hence
f(x+2)<f(x)+2
f(2+2)<f(2)+2
f(4)<7+2
f(4)<9

and
f(x+7)>f(x)+7
f(2+7)>f(2)+7
f(9)>7+7
f(9)>14

we can then go on to see that f(x) > x+5 and f(x)< x+5
(i don't know how to prove this part but i know my hunch says this)


i was an idiot and put since 9 is odd number ( f(x)> x+5)
and 4 is an even number (f(x)<x+5)
therefore 2008 being even
will be
f(2008 )<2008+5,
f(2008 )<2013
----------end of ans---------

that was my answer ...

but i think there's a way to prove f(2008 ) = 2013.
as in
to satisfy
x+5<f(x)
and f(x)<x+5
therefore f(x)=x+5 (remember the equal or smaller/bigger symbol)
( which i didn't do)


can someone post a full work answer for the S^1/152 question???
i didn't do that one as well..

[chiunlin]

Just curious, are these the questions for form-6 math olympiad participants or form 4/5?

[youngyew]

Should be sulung (form 5 and 6), if my impression serves me well.

[francisfu]

f(2) = 7
f(x+2) << f(x) + 2
f(x+7) >> f(x) + 7
______________________________________________________________________

f(2008) << f(2006) + 2 << f(2004) + 4 << ... << f(6) + 2002 << f(4) + 2004 << f(2) + 2006

f(2008) >> f(2001) + 7 >> f(1994) + 14 >> ... >> f(6) + 2002 ----> [ becoz 285(7)+ 6 = 2001 ]

So, observed that from 1st line f(2008) << f(6) + 2002
and from 2nd line f(2008) >> f(6) + 2002

which means f(6) + 2002 >> f(2008) >> f(6) + 2002 (which makes no sense.)


For the equation to be correct, it only can be
f(6) + 2002 = f(2008) = f(6) + 2002

So, back to line 1,
f(2008) << f(2006) + 2 << ... << f(6) + 2002 << f(4) + 2004 << f(2) + 2006

equip f(2008) = f(6) +2002, the equation becomes
f(6) + 2002 << f(2006) + 2 << ... << f(6) + 2002 << f(4) + 2004 << f(2) + 2006

[Again, make no sense, how can f(6) + 2002 << f(6) + 2002 ? So the inequality has to hold. ]

Therefore, f(6) + 2002 = f(2006) + 2 = ... = f(6) + 2002 = f(4) + 2004 = f(2) +2006

f(2008) = f(2) + 2006
= 7 + 2006
= 2013 #

[markwongsk]

f(2) = 7 ........... (1)
f(x+2) <= f(x) + 2........... (2)
f(x+7) >= f(x) + 7........... (3)

(2):

x = 2 therefore f(4) <= f(2) + 2
f(4) <= 9
x = 4 therefore f(6) <= f(4) + 2
f(6) <= 11

f(2) = 7
f(4) <= 9
f(6) <= 11
.
.
.
f(x) >= (x+5) which is established by proof of induction

(3):

x = 2 therefore f(9) >= f(2) + 7
f(9) >= 14
x = 9 therefore f(16) >= f(9) + 7
f(16) >= 21

f(2) = 7
f(9) >= 14
f(16) >= 21
.
.
.
f(x) <= (x+5) which is established by proof of induction

This implies f(x) = (x+5) for both inequalities to hold.
f(2008) = 2013

2) given S= (2+1)(2^2+1)(2^4+1)(2^8+1)....(2^1024+1) + 1

FIND S^(1/512)

Let's consider a separate series...

S1 = (2+1) = 3
S2 = (2+1)(2^2+1) = 15
S3 = (2+1)(2^2+1)(2^4+1) = 255
S4 = (2+1)(2^2+1)(2^4+1)(2^8+1) = 65535
.
.
.
If you noticed...
S1 = 2^2 - 1
S2 = 2^4 - 1
S3 = 2^8 - 1
S4 = 2^16 - 1
.
.
.
Sn = 2^(2^n) - 1

Therefore, S = (2+1)(2^2+1)(2^4+1)(2^8+1)....(2^1024+1) + 1
= 2^(2048) - 1 + 1
= 2^(2048)

S^1/512 = 2^(2048/512)
= 2^4
= 16