Author |
Topic: Elevator Paths (Read 12979 times) |
|
william wu
wu::riddles Administrator
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
|
Here's my answer:
(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 |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
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 |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
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
wu::riddles Administrator
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 |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
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
wu::riddles Administrator
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 |
|
|
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print