Finite number of steps (own)

For college and university level advanced Mathematics
User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Finite number of steps (own)

Unread post by nayel » Wed Jan 05, 2011 8:35 pm

Start with any real number other than $0$ and $1$. At each step, replace the number $x$ by either $1/x$ or $1-x$. Prove that, if we can get from $a$ to $b$ in a finite number of steps, the maximum number of steps required is two.

Example:
$3\xrightarrow{1/x} 1/3\xrightarrow{1-x} 2/3\xrightarrow{1/x} 3/2\xrightarrow{1-x} -1/2$, number of steps $=4$.
But $3\xrightarrow{1-x} -2\xrightarrow{1/x} -1/2$, number of steps $=2$.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

User avatar
Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

Re: Finite number of steps (own)

Unread post by Avik Roy » Wed Jan 05, 2011 9:37 pm

This problem is an interesting one. Though I think the maximum number of steps needed is 3.
It is trivial to show that any of the steps, if repeated in succesive terms, leaves us with the original state. The following reversible sequence shows us the rest:

$ a \xrightarrow{1-x} 1-a \xrightarrow{1/x} 1/(1-a) \xrightarrow{1-x} a/(a-1) \xrightarrow{1/x} (a-1)/a \xrightarrow{1-x} 1/a \xrightarrow{1/x} a$
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

anumoshsad
Posts: 3
Joined: Tue Dec 07, 2010 8:07 pm
Location: Tokyo, Japan

Re: Finite number of steps (own)

Unread post by anumoshsad » Wed Jan 05, 2011 10:51 pm

Nice problem and nice solution.
I also think the number of steps needed is 3.
Let $f(x)=\dfrac{1}{x}$ and $g(x)=1-x$.So $g\circ f= 1- \dfrac{1}{x},f\circ g=\dfrac{1}{1-x},f\circ g\circ f=g\circ f\circ g=\dfrac{x}{x-1}$.
And the fact that the set $\{id,f,g,g\circ f, f\circ g,f\circ g\circ f\}$ is closed under the composition of functions proves it all.
"An equation for me has no meaning, unless it represents a thought of God."- Srinivasa Iyengar Ramanujan

User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: Finite number of steps (own)

Unread post by nayel » Wed Jan 05, 2011 11:50 pm

Yes, I'm sorry, the number of steps required should be 3. Nice solutions! :)

Try this slightly modified version I just posted: viewtopic.php?f=23&t=285
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

abir91
Posts: 52
Joined: Sun Dec 19, 2010 11:48 am

Re: Finite number of steps (own)

Unread post by abir91 » Fri Jan 07, 2011 6:59 pm

সুন্দর সমস্যা এবং সমাধান। কিন্তু maximum এর জায়গায় minimum হবে মনে হইতেছে। :|
Abir

Have you read the Forum Rules and Guidelines?

Post Reply