10276 - Hanoi Tower Troubles Again!

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10276 - Hanoi Tower Troubles Again!

Post by yatsen »

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

Post by shamim »

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

Post by yatsen »

f = f[i-1] + ((i-1)/2+1)*2

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

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

Post by Sedefcho »

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
proof you should just follow your inductive way of
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

Post by CDiMa »

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

Post by hamedv »

what's wrong with my code??? :cry:

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

Post by hamedv »

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!

Post by poixp »

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10276 - Hanoi Tower Troubles Again!

Post by Shafaet_du »

input:

Code: Select all

5
1
2
3
40
30
output:

Code: Select all

1
3
7
839
479
happy programming :)

Post Reply

Return to “Volume 102 (10200-10299)”