

Title: Elevator Paths Post by william wu on Jan 26^{th}, 2003, 12:09pm Elevator operator Willywutang starts on the first floor of an infinitely high hotel. Bored out of his mind, he wants to count the number of ways he can get to the nth floor in k moves, where a move is defined as a onefloor long transition either up or down. How many ways are there? (becomes easier if you make a certain observation) Note: To make sure we understand the counting measure, here are some examples. Moving from the 1st floor straight to the 5th floor counts as 4 moves, because you change the floor number you are on four times. Moving from 1 to 2, 2 to 1, 1 to 2, 2 to 3, 3 to 4, and 4 to 5 counts as 6 moves. // 2:23 AM 1/27/2003 edited by admin such that the hotel is infinitely high 

Title: Re: Elevator Paths Post by BNC on Jan 26^{th}, 2003, 3:03pm Here's my answer: [hide] (a) For k<n1: 0 ways (b) For k=n1: 1 way (c) For k=n+2m, m=0,1,2..: 0 ways (d) For k=n1+2m, m=1,2...: m(n2) [/hide] Reasoning: [hide] (a): trivial (b): trivial (c): Here comes the observation: Willy would need at least n1 moves (going straight up). Adding an odd number of moves would prevent him from getting to the top  you need two moves  down+up to return to your previous location. It doesn't matter if you do, for example, downdownupup  you still need the same number of "downs" and "ups", so an even number of moved must be added to n1. (d): OK, now that we have added an even number of moves to (n1), we may distribute them freely on the floors, with two limitations: (1) we can't get down from the 1st floor, and (2) we can't get down from the top floor (cause then we're already there). So, for each dualmove we get, we have (n2) options to use. Again, it doesn't have to be consecutive downup move. Once you went down from floor f to f1, you'll have to go up from f1 o f eventually, if you'll to get to the top – so count THAT as the dualmove. [/hide] I hope it's somewhat understandable. It’s 1AM here, and I'm off to bed. Good night. 

Title: Re: Elevator Paths Post by BNC on Jan 26^{th}, 2003, 10:47pm OK, morning again  scratch (d) in my previous post  it's wrong. Need some more work. Some pointer, though (hidden): [hide] (a), (b), and (c) are (i think) correct. I think that (b) and (d) should converge. As for (d): For n=3, the answer is 1 for any value of m For m=1, the answer is (n2) for any n>1. Brute force results (penandpaper, no PC  maybe wrong): n=4, m=2 ==> 4 n=5, m=2 ==> 9 [/hide] And one final note for now: If my memory serves me, the process seems very similar to [hide]random walk[/hide]. So the answer should be known in the literature. But what's the fun about that....? 

Title: Re: Elevator Paths Post by redPEPPER on Jan 27^{th}, 2003, 1:54am Hehee, I saw your previous answer wasn't correct yesterday but I decided to let the night pass and let you check it first. Besides, I could only point it's wrong, I couldn't offer anything better... Okay, (a), (b) and (c) are obvious. I wasn't even going to demonstrate (c), as I was thinking it's obvious enough. You added an additional constraint that's not obvious to me: you can't go down from the nth floor. I was initially thinking that, even though you can't go higher than the nth floor, you can very well go to it then down then back up. The important point was to end on the nth floor, which didn't mean you can't pass through it before you use the k moves. Maybe William can tell which way it is? Anyway, here's what I got so far. [hide]Assuming k = n1 + 2*m. There's a basic path from floor 1 to floor n, using the n1 moves. if m>=1 we can add a downup move to this basic path, anywhere between two moves, providing we don't go below floor 1. This builds a path of length n+1, in which, if m>=2, we can add another downup move between two moves, including before, after or in the middle of the previous downup. The problems I have is that we have to remove the cases where the elevator goes below floor 1, and also that we have a lot of duplicate cases. There's gotta be a better way. Still searching... [/hide] 

Title: Re: Elevator Paths Post by william wu on Jan 27^{th}, 2003, 2:22am Yes the important thing is just to end on the nth floor, that's all the problem stipulates. You guys aren't going to like this, but I goofed something in the problem statement (sorry!). The hotel has an infinite number of floors, and your goal is to end at the nth floor. So at a trip's highest point you might be on the n+5 th floor, but eventually get back down to the nth floor. The reasons for this modification are to make this problem identical to another problem on the site that seemed to be mostly ignored. 

Title: Re: Elevator Paths Post by BNC on Jan 27^{th}, 2003, 3:38am WWU: 1 more question: May we assume infinite number of floor below ground (under 1st floor)? 

Title: Re: Elevator Paths Post by redPEPPER on Jan 27^{th}, 2003, 4:33am If this is the case, the problem becomes much easier indeed. [hide] Assuming k = n1 + 2*m, we know that we're going to do k moves. Among these moves, m will be going down. So the problem comes down to calculating the number of arrangements of m items in k positions regardless of order. A combination. C(k,m) = k! / (m! * (km)!) [/hide] 

Title: Re: Elevator Paths Post by william wu on Jan 27^{th}, 2003, 11:46am on 01/27/03 at 03:38:56, BNC wrote:
No. However, you might see something helpful if you pretend negative floors exist. 

Title: Re: Elevator Paths Post by mistysakura on Jan 28^{th}, 2003, 2:25am If n=2, no. of ways =1 if n=3 or more, no. of ways = infinite, because you can do (12)(21) infinitely. Providing that you have enough food and stuff in there to keep you going. ;D 

Title: Re: Elevator Paths Post by william wu on Jan 28^{th}, 2003, 2:34am But, trip lengths are restricted to k moves (k is a parameter stated in the riddle) 

Title: Re: Elevator Paths Post by Garzahd on Jan 28^{th}, 2003, 11:27am So in a trip of k moves from 1 to n, you'll move up (n1) times on the main run, and have (k(n1)) moves to putter around randomly. If (k(n1)) is not even, we're hosed, so let's assume it is. So we're moving up (n1)+(k(n1))/2 = (n+k1)/2 times and moving down (kn+1)/2 times. Assuming unlimited basements, we're just distributing one direction of moves somewhere among all the moves, so the answer would be C(k,(kn+1)/2) = C(k,(n+k1)/2). Now how to remove any paths that take us underground? 

Title: Re: Elevator Paths Post by SWF on Feb 4^{th}, 2003, 7:51pm Let N(n,k) be number of ways of going to floor n with k moves. A few rules can be found quickly: N(n,n1)=1: the only way to reach floor n with n1 moves is go up every move. N(n,k)=N(n+1,k1)+N(n1,k1) if n>1, because if you reach floor n in k moves you must be on either the floor above it or below it in k1 moves. N(1,2M)=N(2,2M1) where M is a positive integer. Because you need an even number of moves to get back to the first floor, and last move needs to be going down from 2nd floor since there are no negative floor numbers. Others have already described the rule that kn=2m1 or else N(n,k) is zero. Using those rules makes it easy to generate a table. After inspection of the table and deriving the pattern in the first few nonzero diagonals, I am going to jump to the conclusion (which I am confident of, but haven't proved) that for kn=2m1 (m>=0): http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?md5=4f42295b272b136226965aff93d3d565 Note, that n in the numerator does not have a factorial. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 