wu :: forums « wu :: forums - Elevator Paths » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 1:32pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: SMQ, william wu, Grimbal, Icarus, ThudnBlunder, towr, Eigenray)    Elevator Paths « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Elevator Paths  (Read 12975 times)
william wu

Gender:
Posts: 1291
 Elevator Paths   « on: Jan 26th, 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 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
 « Last Edit: Jan 27th, 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 26th, 2003, 3:03pm » Quote Modify

(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)

Reasoning:

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

I hope it's somewhat understandable. It’s 1AM here, and I'm off to bed. Good night.
 IP Logged

BNC
Uberpuzzler

Gender:
Posts: 1732
 Re: Elevator Paths   « Reply #2 on: Jan 26th, 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 (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

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

redPEPPER
Full Member

Posts: 160
 Re: Elevator Paths   « Reply #3 on: Jan 27th, 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 = 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...

 « Last Edit: Jan 27th, 2003, 1:56am by redPEPPER » IP Logged
william wu

Gender:
Posts: 1291
 Re: Elevator Paths   « Reply #4 on: Jan 27th, 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 27th, 2003, 3:38am » Quote Modify

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

redPEPPER
Full Member

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

If this is the case, the problem becomes much easier indeed.

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)!)
 IP Logged
william wu

Gender:
Posts: 1291
 Re: Elevator Paths   « Reply #7 on: Jan 27th, 2003, 11:46am » Quote Modify

on Jan 27th, 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 28th, 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 (1-2)(2-1) infinitely.  Providing that you have enough food and stuff in there to keep you going.
 IP Logged
william wu

Gender:
Posts: 1291
 Re: Elevator Paths   « Reply #9 on: Jan 28th, 2003, 2:34am » Quote Modify

But, trip lengths are restricted to k moves (k is a parameter stated in the riddle)
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Garzahd
Junior Member

Gender:
Posts: 130
 Re: Elevator Paths   « Reply #10 on: Jan 28th, 2003, 11:27am » Quote Modify

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?
 IP Logged
SWF
Uberpuzzler

Posts: 879
 Re: Elevator Paths   « Reply #11 on: Feb 4th, 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,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):

Note, that n in the numerator does not have a factorial.

 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »