Author |
Topic: A Reciprocal And maximum Value Puzzle (Read 497 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
A Reciprocal And maximum Value Puzzle
« on: Jun 21st, 2007, 8:32am » |
 Quote  Modify
|
Determine the maximum value of y0 such that there exists a sequence y0, y1, ... , y1995 of positive reals with y0 = y1995 satisfying:
yi-1 + 2/yi-1 = 2yi + 1/yi; for i = 1, ... , 1995
|
| « Last Edit: Jun 21st, 2007, 9:05am by K Sengupta » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: A Reciprocal And maximum Value Puzzle
« Reply #1 on: Jun 21st, 2007, 1:07pm » |
Quote Modify
|
Solving the quadratic in yi we see that
either
yi = yi-1/2
or
yi = 1/yi-1
If 1995 were even, we could always get back y0 no matter what 
Since 1995 is odd, it seems the best we can do is
21994/y0 = y0
i.e the max value of y0 is 2997
(this is just an observation, though i think the proof should not be too difficult)
|
| « Last Edit: Jun 21st, 2007, 1:08pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: A Reciprocal And maximum Value Puzzle
« Reply #2 on: Jun 21st, 2007, 11:44pm » |
Quote Modify
|
Right, suppose we start at y, and apply a0 iterations of f(x)=x/2, then g(x)=1/x, then a1 more f, then g, etc., applying g a total of k times, and ending with ak applications of f (allowing ai=0).
If k is even, we end up with F(y) = y*2-a0 + a1 - a2 + . . . - ak. But k +  ai = 1995, and since k is even, ai is odd, and so therefore (-1)i ai  0. Since y > 0, this means F(y) can't be y.
So we must have k odd, and F(y) = 2a0 - a1 + a2 - ... - ak/y. To maximize y with F(y)=y, we must maximize (-1)iai. But since k + ai = 1995, and k is odd, it's clear that this is maximized with k=1 and a0=1994, giving F(y) = 21994/y.
|
|
IP Logged |
|
|
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
Re: A Reciprocal And maximum Value Puzzle
« Reply #3 on: Jun 22nd, 2007, 2:10am » |
Quote Modify
|
on Jun 21st, 2007, 11:44pm, Eigenray wrote:Right, suppose we start at y, and apply a0 iterations of f(x)=x/2, then g(x)=1/x, then a1 more f, then g, etc., applying g a total of k times, and ending with ak applications of f (allowing ai=0).
If k is even, we end up with F(y) = y*2-a0 + a1 - a2 + . . . - ak. But k + ai = 1995, and since k is even, ai is odd, and so therefore (-1)i ai 0. Since y > 0, this means F(y) can't be y.
So we must have k odd, and F(y) = 2a0 - a1 + a2 - ... - ak/y. To maximize y with F(y)=y, we must maximize (-1)iai. But since k + ai = 1995, and k is odd, it's clear that this is maximized with k=1 and a0=1994, giving F(y) = 21994/y. |
|
My approach to the problem is basically the same as Eigenray's and the solution is furnished hereunder as follows:
The relation given is a quadratic in xi, so it has two solutions, and by inspection these are yi = 1/yi-1 and yi-1/2.
For an even number of moves we can start with an arbitrary y0 and get back to it. Using n-1 halvings, and taking the inverse, yields:
2n-1/y_0 after n moves.
Repeating the proceedure retuns one to to y_0 after 2n moves.
However, it is observed that 1995 is odd.
The sequence given above brings one back to y_0 after n moves, provided that y_0 = 2(n-1)/2.
We show that this is the largest possible y_0.
Suppose we have a halvings followed by an inverse followed by b halvings followed by an inverse.
Then if the number of inverses is odd we end up with 2a-b+c- .../y_0, and if it is even we end up with y0/2a-b+c-...
In the first case, since the final number is y_0 we must have y_0 = 2(a-b+-...)/2.
All the a, b, ... are non-negative and sum to the number of moves less the number of inverses, so we clearly maximise y_0 by taking a single inverse and a = n-1.
In the second case, we must have 2a-b+c- ... = 1 and hence a - b + c - ... = 0.
But that implies that a + b + c + ... is even and hence the total number of moves is even, which it is not.
So we must have an odd number of inverses and the maximum value of y_0 is :
2(n-1)/2.
Finally, substituting n= 1995 , it is trivial to observe that the maximum value of y_0 is 2997
|
| « Last Edit: Jun 22nd, 2007, 2:29am by K Sengupta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print