Author 
Topic: Elevator Paths (Read 13005 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Elevator Paths
« on: Jan 26^{th}, 2003, 12:09pm » 
Quote Modify

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

« Last Edit: Jan 27^{th}, 2003, 2:24am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: Elevator Paths
« Reply #1 on: Jan 26^{th}, 2003, 3:03pm » 
Quote Modify

Here's my answer: (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) Reasoning: (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. I hope it's somewhat understandable. It’s 1AM here, and I'm off to bed. Good night.


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: Elevator Paths
« Reply #2 on: Jan 26^{th}, 2003, 10:47pm » 
Quote Modify

OK, morning again  scratch (d) in my previous post  it's wrong. Need some more work. Some pointer, though (hidden): (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 And one final note for now: If my memory serves me, the process seems very similar to random walk. So the answer should be known in the literature. But what's the fun about that....?


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



redPEPPER
Full Member
Posts: 160


Re: Elevator Paths
« Reply #3 on: Jan 27^{th}, 2003, 1:54am » 
Quote Modify

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. 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...

« Last Edit: Jan 27^{th}, 2003, 1:56am by redPEPPER » 
IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Elevator Paths
« Reply #4 on: Jan 27^{th}, 2003, 2:22am » 
Quote Modify

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.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: Elevator Paths
« Reply #5 on: Jan 27^{th}, 2003, 3:38am » 
Quote Modify

WWU: 1 more question: May we assume infinite number of floor below ground (under 1st floor)?


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



redPEPPER
Full Member
Posts: 160


Re: Elevator Paths
« Reply #6 on: Jan 27^{th}, 2003, 4:33am » 
Quote Modify

If this is the case, the problem becomes much easier indeed. 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)!)


IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Elevator Paths
« Reply #7 on: Jan 27^{th}, 2003, 11:46am » 
Quote Modify

on Jan 27^{th}, 2003, 3:38am, BNC wrote:WWU: 1 more question: May we assume infinite number of floor below ground (under 1st floor)? 
 No. However, you might see something helpful if you pretend negative floors exist.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



mistysakura
Junior Member
Gender:
Posts: 121


Re: Elevator Paths
« Reply #8 on: Jan 28^{th}, 2003, 2:25am » 
Quote Modify

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.


IP Logged 



Garzahd
Junior Member
Gender:
Posts: 130


Re: Elevator Paths
« Reply #10 on: Jan 28^{th}, 2003, 11:27am » 
Quote Modify

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?


IP Logged 



SWF
Uberpuzzler
Posts: 879


Re: Elevator Paths
« Reply #11 on: Feb 4^{th}, 2003, 7:51pm » 
Quote Modify

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): Note, that n in the numerator does not have a factorial.


IP Logged 



