## 10276 - Hanoi Tower Troubles Again!

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

### 10276 - Hanoi Tower Troubles Again!

I can find the fomula between f(x) and f(x-1) by observation.
And it really work!
But I can't prove it in math.
Can anyone prove the formula ?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Re: 10276 Hanoi Tower Troubles Again! need math proof

yatsen wrote:I can find the fomula between f(x) and f(x-1) by observation.
And it really work!
But I can't prove it in math.
Can anyone prove the formula ?
I was wondering, what is the formula.

I got Ac using simulation.

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
f = f[i-1] + ((i-1)/2+1)*2

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
yatsen wrote:f = f[i-1] + ((i-1)/2+1)*2

You can rewrite this as f=f[i-1]+i+1 but I don't think it really works...

Ciao!!!

Claudio

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
You can not rewrite the formula in that way, Claudio.
That's because the division Yatsen gives in his formula
is an integer division ( 50/2 = 25, 51/2 = 25 ).

This means that if K = (i-1)/2
then 2*K is not always equal to (i-1).

Yatsen, it is interesting to know how you derived that
formula. I guess by some inductive way of thinking.
Then most probably if you want a clear mathematical
thinking which has helped you to derive the formula.

Seems an interesting math task though to prove
your formula ( if it is always correct of course ).
There's still some minor chance that it works for i = 1,2,...,50
but it does not always work.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Sedefcho wrote:You can not rewrite the formula in that way, Claudio.
That's because the division Yatsen gives in his formula
is an integer division.
You're right, too careless of me...

Ciao!!!

Claudio

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
what's wrong with my code???

Code: Select all

``````ACed
``````
Last edited by hamedv on Tue Jul 24, 2007 8:05 pm, edited 1 time in total.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
Finally i got ac;
for n = 2 my optput was wrong

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

### Re: 10276 - Hanoi Tower Troubles Again!

I have a little misunderstood. We need to put ball with number x and there are couple of pegs where it possible, should we simulate all possible placing or can we prove that any will do?
First I use simulation of all possibilities but it takes too long, than I tried to place ball on first possible place and get Ac. But, why I can do so?

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10276 - Hanoi Tower Troubles Again!

input:

Code: Select all

``````5
1
2
3
40
30
``````
output:

Code: Select all

``````1
3
7
839
479
``````
happy programming