wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Elevator Paths
        
(Message started by: william wu on Jan 26^th, 2003, 12:09pm)

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 one-floor 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<n-1: 0 ways
(b) For k=n-1: 1 way
(c) For k=n+2m, m=0,1,2..: 0 ways
(d) For k=n-1+2m, m=1,2...: m(n-2)
[/hide]
Reasoning:
[hide]
(a): trivial
(b): trivial
(c): Here comes the observation: Willy would need at least n-1 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, down-down-up-up -- you still need the same number of "downs" and "ups", so an even number of moved must be added to n-1.
(d): OK, now that we have added an even number of moves to (n-1), 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 dual-move we get, we have (n-2) options to use. Again, it doesn't have to be consecutive down-up move. Once you went down from floor f to f-1, you'll have to go up from f-1 o f eventually, if you'll to get to the top – so count THAT as the dual-move.
[/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 (n-2) for any n>1.

Brute force results (pen-and-paper, 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 = n-1 + 2*m.
There's a basic path from floor 1 to floor n, using the n-1 moves. if m>=1 we can add a down-up 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 down-up move between two moves, including before, after or in the middle of the previous down-up.

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 = n-1 + 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! * (k-m)!)
[/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:

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.

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 (1-2)(2-1) 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 (n-1) times on the main run, and have (k-(n-1)) moves to putter around randomly. If (k-(n-1)) is not even, we're hosed, so let's assume it is.

So we're moving up (n-1)+(k-(n-1))/2 = (n+k-1)/2 times and moving down (k-n+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,(k-n+1)/2) = C(k,(n+k-1)/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,n-1)=1: the only way to reach floor n with n-1 moves is go up every move.

N(n,k)=N(n+1,k-1)+N(n-1,k-1) 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 k-1 moves.

N(1,2M)=N(2,2M-1) 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 k-n=2m-1 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 non-zero diagonals, I am going to jump to the conclusion (which I am confident of, but haven't proved) that for k-n=2m-1 (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.